程序员子悠 · 好记性不如烂笔头

常用算法笔记

@(公众号)[技术点]

快排

package com.silence.arts.leetcode.second;

public class QuickSort {

    public static void main(String[] args) {
        int[] array = new int[]{10, 5, 3, 1, 7, 2, 8, 0};
        quickSort2(array, 0, array.length - 1);
        for (int element : array) {
            System.out.print(element + " ");
        }
    }

    public static void quickSort2(int[] arr, int left, int right) {
        if (left < right) {
            int position = position(arr, left, right);
            quickSort2(arr, left, position - 1);
            quickSort2(arr, position + 1, right);
        }
    }

    public static int position(int[] array, int left, int right) {
        int base = array[left];
        while (left < right) {
            while (right > left && array[right] >= base) {
                right--;
            }
            array[left] = array[right];

            while (left < right && array[left] <= base) {
                left++;
            }
            array[right] = array[left];

        }
        //此时 left == right
        array[left] = base;
        return left;
    }
}

二分查找变形

查找第一个值等于给定值的元素下标

package com.silence.arts.leetcode.binary;

/**
 * <br>
 * <b>Function：</b><br>
 * <b>Author：</b>@author Silence<br>
 * <b>Date：</b>2018-10-29 22:53<br>
 * <b>Desc：</b>二分查找变形题目<br>
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] a = {1, 3, 4, 5, 6, 8, 8, 8, 11, 18};
        System.out.println(bsearch4(a, a.length, 12));
    }

    /**
     * 变形一：二分查找变形题，查找第一个值等于给定值的元素下标
     * int[] a = {1, 3, 4, 5, 6, 8, 8, 8, 11, 18};
     * 如查找8，应该返回5
     *
     * @param array
     * @param n
     * @param value
     * @return
     */
    private static int bsearch1(int[] array, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (array[mid] > value) {
                high = mid - 1;
            } else if (array[mid] < value) {
                low = mid + 1;
            } else {
                if (mid == 0 || array[mid - 1] != value) {
                    return mid;
                } else {
                    high = mid - 1;
                }
            }
        }
        return -1;
    }

查找最后一个值等于给定值的元素

    /**
     * 变形二：查找最后一个值等于给定值的元素
     *
     * @param array
     * @param n
     * @param value
     * @return
     */
    private static int bsearch2(int[] array, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (array[mid] > value) {
                high = mid - 1;
            } else if (array[mid] < value) {
                low = mid + 1;
            } else {
                if (mid == n - 1 || array[mid + 1] != value) {
                    return mid;
                } else {
                    low = mid + 1;
                }
            }
        }
        return -1;
    }

查找第一个大于等于给定值的元素

    /**
     * 变形三：查找第一个大于等于给定值的元素
     *
     * @param array
     * @param n
     * @param value
     * @return
     */
    private static int bsearch3(int[] array, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (array[mid] >= value) {
                if ((mid == 0) || (array[mid - 1] < value)) {
                    return mid;
                } else {
                    high = mid - 1;
                }
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

查找最后一个小于等于给定值的元素

    /**
     * 变形四：查找最后一个小于等于给定值的元素
     * int[] a = {1, 3, 4, 5, 6, 8, 8, 8, 11, 18};
     * 如value = 12，则应该返回11的下标8
     * System.out.println(bsearch4(a, a.length, 12));
     *
     * @param array
     * @param n
     * @param value
     * @return
     */
    private static int bsearch4(int[] array, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (array[mid] > value) {
                high = mid - 1;
            } else {
                if (mid == n - 1 || array[mid + 1] > value) {
                    return mid;
                } else {
                    low = mid + 1;
                }
            }
        }
        return -1;
    }
}

链表反转

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        cur, prev = head, None
        while cur:
            cur.next, prev, cur = prev, cur, cur.next
        return prev

One more thing

• Personal Medium Home Page: https://medium.com/@zhuxiang134
• Personal Website: https://zxsilence.cn/