Algorithm reference cheatsheet

Posted on 2017-09-04 Edited on 2021-05-30 In Tech Disqus:

Some basic ideas of classic problems/algorithms.

BinarySearch

2020更新：根据这个算法总结了一个不那么绕的二分查找

// 朴素二分查找，不保证查找结果位置
int binarySearch(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {     // 搜索范围为[left, right]闭区间
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return nums[mid];
        } else if (nums[mid] < target) {
            left = mid + 1;     // 下一步搜索区间[mid + 1, right]
        } else if (nums[mid] > target) {
            right = mid - 1;    // 下一步搜索区间[left, mid - 1]
        }
    }
    return -1;
}

// 第一个出现的位置或者插入位置
int binarySearchFirst(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    int left = 0;
    int right = nums.length;    // 左闭右开
    while (left < right) {      // 搜索范围为[left, right)
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid;    // 下一步搜索区间[left, mid)
        } else if (nums[mid] < target) {
            left = mid + 1; // 下一步搜索区间[mid + 1, right)
        } else if (nums[mid] > target) {
            right = mid;    // 下一步搜索区间[left, mid)
        }
    }
    return left;
    // return left == nums.length || nums[left] != target ? -1 : left;
}

// 最后一个出现的位置
int binarySearchLast(int[] nums, int target) {
    if (nums == null || nums.length == 0) {
        return -1;
    }
    int left = 0;
    int right = nums.length;    // 左闭右开
    while (left < right) {      // 搜索范围为[left, right)
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            left = mid + 1;    // 下一步搜索区间[mid + 1, right)
        } else if (nums[mid] < target) {
            left = mid + 1; // 下一步搜索区间[mid + 1, right)
        } else if (nums[mid] > target) {
            right = mid;    // 下一步搜索区间[left, mid)
        }
    }
    return left - 1;    // 当搜索结束时left处一定不是target了，前一位还有可能
    // return left == 0 || nums[left - 1] != target ? -1 : left - 1;
}

Deprecated

// template from http://fihopzz.blogspot.com/2013/07/enter-post-title-here-binary-search-and.html
private int binarySearchInsertionPos(int[] nums, int target) {
    int start = -1, end = nums.length;
    while (end - start > 1) {
        int mid = start + (end - start) / 2;
        // invariant relation: nums[start] < target <= nums[end]
        if (nums[mid] >= target) {
            end = mid;
        } else {
            start = mid;
        }
    }
    return end;
}
private int binarySearchSqrt(int x) {
    if (x < 1) {
        return 0;
    }
    long start = -1, end = (long)x + 1;
    while (end - start > 1) {
        long mid = start + (end - start) / 2;
        // invariant condition: start <= target*target < end
        if (mid > x / mid) {
            end = mid;
        } else {
            start = mid;
        }
    }
    return (int)start;
}
private int binarySearchFirst(int[] nums, int target) {
    int start = -1, end = nums.length;
    while (end - start > 1) {
        int mid = start + (end - start) / 2;
        // invariant relation: nums[start] < target <= nums[end]
        if (nums[mid] >= target) {
            end = mid;
        } else {
            start = mid;
        }
    } 
    return end < nums.length && nums[end] == target ? end : -1;
}
private int binarySearchLast(int[] nums, int target) {
    int start = -1, end = nums.length;
    while (end - start > 1) {
        int mid = start + (end - start) / 2;
        // invariant relation: nums[start] <= target < nums[end]
        if (nums[mid] <= target) {
            start = mid;
        } else {
            end = mid;
        }
    }
    return start >= 0 && nums[start] == target ? start : -1;
}

Sort

Selection Sort

外层循环i从头到尾、内层循环从i往后，每次找最小值所在的index，内层循环结束后和头部swap，这样每次都可以把当前最小值放到最前面。

private void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        int index = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[index]) {
                index = j;
            }
        }
        swap(arr, i, index);
    }
}

Insertion Sort

外层循环i从前往后遍历，内层循环从i往前，每次将相邻的顺序反了的元素swap。

private void insertionSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
            swap(arr, j, j - 1);
        }
    }
}

Shell Sort

插入排序的升级版，循环的interval是从大到小的。排序的本质是消除逆序对，如果增大interval，则一次swap可能会消除更多的逆序对，因此可以突破O(N^2).

private void shellSort(int[] arr) {
    int h = 1;
    while (h < arr.length / 3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        for (int i = h; i < arr.length; i++) {
            for (int j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
                swap(arr, j, j - h);
            }
        }
        h /= 3;
    }
}

Bubble Sort

外层循环从头到尾，内层循环从尾到i + 1不断把较小值放到前面。

private void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = arr.length - 1; j > i; j--) {
            if (arr[j] < arr[j - 1]) {
                swap(arr, j, j - 1);
            }
        }
    }
}

Bucket Sort

木桶排序牺牲了空间换取速度，达到了O(N)。统计每个值出现的个数，然后依次放回原数组。

private void bucketSort(int[] arr) {
    int bucket = new int [1000010];
    for (int i = 0; i < arr.length; i++) {
        bucket[arr[i]]++;
    }
    int j = 0, k = 0;
    while (j < arr.length && k < bucket.length) {
        while ((bucket[k]--) > 0) {
            arr[j++] = k;
        }
        k++;
    }
}

Radix Sort[====TODO====]

基数排序就是根据每个位数字大小，从个位数、十位数、百位数、千位数…存入bucket

private void radixSort(int[] arr, int radix, int maxLen) {
    int[] temp = new int [arr.length];
    int[] bucket = new int [radix];

    for (int i = 0, devide = 1; i < maxLen; i++) {
        Arrays.fill(bucket, 0);
        System.arraycopy(arr, 0, temp, 0, arr.length);

    }
}

Merge Sort

分治法思想，将两个序列不断拆分，拆到不能再拆后分别排序后合并。归并排序（以及插入排序）是稳定的。

public void mergeSort(int[] arr) {
    partition(arr, 0, arr.length - 1);
}
private void partition(int[] arr, int start, int end) {
    if (start >= end) {
        return;
    }
    int mid = (start + end) / 2;
    partition(arr, start, mid);
    partition(arr, mid + 1, end);
    if (arr[mid] < arr[mid + 1]) {
        return;
    }
    merge(arr, start, mid, end);
}
private void merge(int[] arr, int start, int mid, int end) {
    int left = start, right = mid + 1, index = start;
    int[] temp = new int [arr.length];

    while (left <= mid && right <= end) {
        if (arr[left] < arr[right]) {
            temp[index++] = arr[left++];
        } else {
            temp[index++] = arr[right++];
        }
    }

    while (left <= mid) {
        temp[index] = arr[left++];
    }
    while (right <= end) {
        temp[index] = arr[right++];
    }

    for (index = start; index <= end; index++) {
        arr[index] = temp[index];
    }
}

Quick Sort + Shuffle

定义一个pivot值，找到它的位置使得左边都小于等于它、右边都大于等于它，然后再递归到两边去排。最差情况出现在当已经有序的时候，退化成O(N^2)，因为每个pivot都要和后面的比较一波。

private void shuffle(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        swap(arr, i, Random.nextInt(i + 1));
    }
}
private void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}
private void quickSort(int[] arr, int start, int end) {
    if (start >= end) {
        return;
    }
    int j = partition(arr, start, end);
    quickSort(arr, start, j - 1);
    quickSort(arr, j + 1, end);
}
private int partition(int[] arr, int start, int end) {
    int left = start, right = end + 1, pivot = arr[start];
    while (true) {
        while (arr[++left] < pivot) {
            if (left == end) {
                break;
            }
        }
        while (arr[--right] > pivot) {
            if (right == start) {
                break;
            }
        }
        if (left >= right) {
            break;
        }
        swap(arr, left, right);
    }
    swap(arr, start, right); // pivot放到它应该放的位置
    return right;
}

Big Integer Calculation

// https://discuss.leetcode.com/topic/30508/easiest-java-solution-with-graph-explanation/
class Multiply {
    public String multiply(String num1, String num2) {
        if (num1 == null || num2 == null
           || num1.length() == 0 || num2.length() == 0) {
            return "";
        }
        int m = num1.length(), n = num2.length();
        int[] result = new int [m + n];
        char[] cnum1 = num1.toCharArray(), cnum2 = num2.toCharArray();
        
        // from least significant bit
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                int mult = (cnum1[i] - '0') * (cnum2[j] - '0');
                int first = i + j, second = i + j + 1;
                int sum = mult + result[second];    // add carry from prev steps
                result[first] += sum / 10;  // accumulate
                result[second] = sum % 10;  // overwrite
            }
        }
        
        StringBuilder sb = new StringBuilder();
        int i = 0;
        // find the first non-zero item
        while (i < result.length && sb.length() == 0 && result[i] == 0) {
            i++;
        }
        while (i < result.length) {
            sb.append(result[i++]);
        }
        return sb.length() == 0? "0": sb.toString();
    }
}

// https://discuss.leetcode.com/topic/5425/short-and-easy-to-understand-solution?page=1
class Power {
    public double myPow(double x, int n) {
        if (n == 0 || x == 1) {
            return 1;
        }
        if (n == Integer.MIN_VALUE) {   // 防止取负数之后越界
            return (1.0 / x) * myPow(x, n + 1);
        }
        if (n < 0) {
            n = -n;
            x = 1.0 / x;
        }
        return (n & 1) != 0 ? x * myPow(x * x, n / 2) : myPow(x * x, n / 2); 
    }
}

GCD

public int findGcd(int a, int b) {
    while (b != 0) {
        int t = a;
        a = b;
        b = t % b;
    }
    return a;
}

public int findGcd(int a, int b) {
    if (b > a) {
        return findGcd(b, a);
    }
    return b == 0 ? a : findGcd(b, a % b);
}

Union Find

并查集：在UF类中维护一个id数组，这个id表示当前索引的祖宗的索引，若id[idx] = idx说明它本身就是老大，初始时每个元素都是自己的老大。find(p)函数就是返回p的老大的索引，union(p, q)函数就是将索引p和q两伙合并起来，分别找到p和q的老大索引pRoot和qRoot，但是他们谁隶属于谁呢？rank就是在这时候起作用，将rank高的保留，rank低的老大合并到更高的老大那去，若两个老大一样，就随意了，合并后新老大的rank要加加。在UF中还有一个count变量，其实就是算有几个独立老大的，初始时每个1都是老大，而每次成功调用union时count都会减减。

class UF {
    private int[] id = null;
    private int[] rank = null;
    private int count = 0;
    public UF(char[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        id = new int [rows * cols];
        rank = new int [rows * cols];
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == '1') {
                    count++;
                }
                int temp = i * cols + j;
                id[temp] = temp;
                rank[temp] = 0;
            }
        }
    }
    public int find(int p) {
        while (id[p] != p) {
            id[p] = id[id[p]];   // 路径压缩
            p = id[p];
        }
        return p;
    }
    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        if (rank[pRoot] > rank[qRoot]) {
            id[qRoot] = pRoot;  // 并入排名更高的
        } else if (rank[qRoot] > rank[pRoot]) {
            id[pRoot] = qRoot;
        } else {
            id[pRoot] = qRoot;
            rank[qRoot]++;      // qRoot排名更高
        }
        count--;
    }
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }
    public int getCount() {
        return count;
    }
}

https://leetcode.com/problems/number-of-islands/

Backtracking

Subset(无重复元素)

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    //Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, 0);
    return list;
}

private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));
    for(int i = start; i < nums.length; i++){
        tempList.add(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}

Subset(有重复元素)

public List<List<Integer>> subsetsWithDup(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int start){
    list.add(new ArrayList<>(tempList));
    for(int i = start; i < nums.length; i++){
        if(i > start && nums[i] == nums[i - 1]) 
            continue; // skip duplicates
        tempList.add(nums[i]);
        backtrack(list, tempList, nums, i + 1);
        tempList.remove(tempList.size() - 1);
    }
}

Permutations(无重复元素全排列)

public List<List<Integer>> permute(int[] nums) {
   List<List<Integer>> list = new ArrayList<>();
   // Arrays.sort(nums); // not necessary
   backtrack(list, new ArrayList<>(), nums);
   return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
   if (tempList.size() == nums.length) {
      list.add(new ArrayList<>(tempList));
   } else {
      for (int i = 0; i < nums.length; i++) { 
         if (tempList.contains(nums[i])) continue; // element already exists, skip
         tempList.add(nums[i]);
         backtrack(list, tempList, nums);
         tempList.remove(tempList.size() - 1);
      }
   }
}

Permutations(有重复元素全排列)

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, new boolean[nums.length]);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, boolean [] used){
    if (tempList.size() == nums.length) {
        list.add(new ArrayList<>(tempList));
    } else {
        for (int i = 0; i < nums.length; i++) {
            if (used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;
            used[i] = true; 
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, used);
            used[i] = false; 
            tempList.remove(tempList.size() - 1);
        }
    }
}

Combinations

public class Solution {
    private void dfs(List<List<Integer>> ans, List<Integer> arr, int n, int k, int start) {
        if (arr.size() == k) {
            ans.add(new ArrayList(arr));
            return;
        }
        for (int i = start; i <= n; i++) {
            arr.add(i);
            dfs(ans, arr, n, k, i+1);
            arr.remove(arr.size()-1);
        }
    }
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        ArrayList<Integer> arr = new ArrayList<Integer>();
        if (n <= 0) {
            return ans;
        }
        dfs(ans, arr, n, k, 1);
        return ans;
    }
}

combination-sum（无重复元素可重复组合求和）

public List<List<Integer>> combinationSum(int[] nums, int target) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, target, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
    if (remain < 0) return;
    else if (remain == 0) list.add(new ArrayList<>(tempList));
    else { 
        for (int i = start; i < nums.length; i++){
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
            tempList.remove(tempList.size() - 1);
        }
    }
}

combination-sum（有重复元素不可复用组合求和）

public List<List<Integer>> combinationSum2(int[] nums, int target) {
    List<List<Integer>> list = new ArrayList<>();
    Arrays.sort(nums);
    backtrack(list, new ArrayList<>(), nums, target, 0);
    return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
    if (remain < 0) return;
    else if (remain == 0) list.add(new ArrayList<>(tempList));
    else {
        for (int i = start; i < nums.length; i++){
            if (i > start && nums[i] == nums[i - 1]) continue; // skip duplicates
            tempList.add(nums[i]);
            backtrack(list, tempList, nums, remain - nums[i], i + 1);
            tempList.remove(tempList.size() - 1); 
        }
    }
}

KMP算法

根据pattern构建有限状态机的DP数组，然后再取给定的一堆text中找匹配的索引。dp[j][c] = next表示，当前是状态j，遇到了字符c，应该转移到状态next. 需要一个辅助状态X，它永远比当前状态j落后一个状态，拥有和j最长的相同前缀，我们给它起了个名字叫「影子状态」.

public class KMP {
    private int[][] dp;
    private String pattern;

    public KMP(String pattern) {
        this.pattern = pattern;
        int M = this.pattern.length()
        // dp[状态][字符]表示需要转移到的下一个状态
        dp = new int[][256];
        // 最开始只有和第一个字符匹配才能让pattern转移到下一个状态
        dp[0][this.pattern.charAt(0)] = 1;

        // 影子状态，表示相同前缀的部分，当后续状态不匹配需要回滚时就需要参考影子状态的next
        int X = 0;
        for (int j = 1; j < M; j++) {
            for (int c = 0; c < 256; c++) {
                dp[j][c] = dp[X][c];    // j状态的前缀和X状态的前缀是一样的，因此状态转换可以通用
            }
            dp[j][pattern.charAt(j)] = j + 1;   // 匹配了就转移到pattern的下一位
            X = dp[X][pattern.charAt(j)];       // 遇到了j处字符，则让影子状态转移到对应字符的状态
        }
    }

    public int search(String text) {
        int M = pattern.length();
        int N = text.length();
        int j = 0;
        for (int i = 0; i < N; i++) {
            // 从0状态出发，根据出现的字符找下一个状态
            j = dp[j][text.charAt(i)];
            if (j == M) {
                // pattern在text中的起始索引
                return i - M + 1;
            }
        }
        return -1；
    }
}

此外再介绍leetcode模版。在构建pattern的dp数组时索引从1开始且单向前进，在text中搜索时索引从0开始且时单向前进。

class Solution {
    public int strStr(String haystack, String needle) {
        if (haystack == null || needle == null || needle.isEmpty()) {
            return 0;
        }
        int len = needle.length();
        int[] dp = new int[len];        // 构建needle的failure function数组
        for (int i = 1; i < len; i++) {
            int j = dp[i - 1];          // 当前最长common后缀前缀的长度
            while (j > 0 && needle.charAt(j) != needle.charAt(i)) {
                j = dp[j - 1];          // 失配则转移到上一个状态，即以char[dp[i - 1] - 1]结尾的状态
            }
            if (needle.charAt(j) == needle.charAt(i)) {
                j++;
            }
            dp[i] = j;
        }
        
        int lenFull = haystack.length();
        int j = 0;
        for (int i = 0; i < lenFull; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = dp[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == len) {
                return i - len + 1;
            }
        }
        return -1;
    }
}

Stack

Tree

https://leetcode.com/problems/boundary-of-binary-tree/

Preorder Iterative

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> output = new LinkedList<>();
    LinkedList<TreeNode> stack = new LinkedList<>();
    if (root == null) {
        return output;
    }

    stack.add(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pollLast();
        output.add(node.val);
        if (node.right != null) {
            stack.add(node.right);
        }
        if (node.left != null) {
            stack.add(node.left);
        }
    }
    return output;
}

Inorder Iterative

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    if (root == null) {
        return ans;
    }
    Deque<TreeNode> s = new ArrayDeque<>();
    TreeNode curr = root;
    while (curr != null || !s.isEmpty()) {
        while (curr != null) {
            s.push(curr);
            curr = curr.left;
        }
        curr = s.pop();
        ans.add(curr.val);
        curr = curr.right;
    }
    return ans;
}

Count Nodes in Complete BT

complete二叉树是指每一层都逐步从左到右填充节点，左右孩子高度差顶多为1. 计算有多少个节点在普通二叉树中是O(N)，而在完美二叉树中节点数就是高度的二次幂，因此O(logN)求高度即可。而在完全二叉树中直接遍历比较蠢，就得想怎么利用高度做文章。如果左右孩子的高度一样，那就直接照搬完美二叉树；如果不同就继续按照O(N)递归。时间复杂度为O(logN * logN)(每次递归的复杂度为logN，总共只需要logN次递归，因为完全二叉树其中一个子树一定为完美二叉树，并不是每一次都会触发递归)

public int countCompleteTreeNodes(TreeNode root) {
    TreeNode l = root, r = root;
    int heightLeft = 0, heightRight = 0;
    while (l != null) {
        l = l.left;
        heightLeft++;
    }
    while (r != null) {
        r = r.right;
        heightRight++;
    }
    if (heightLeft == heightRight) {
        return (int)Math.pow(2, heightLeft) - 1;
    }
    return 1 + countCompleteTreeNodes(root.left) + countCompleteTreeNodes(root.right);
}

Postorder Iterative

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> retVal = new LinkedList<>();
    if (root == null) {
        return retVal;
    }
    Deque<TreeNode> treeNodeStack = new ArrayDeque<>();
    treeNodeStack.push(root);
    while (!treeNodeStack.isEmpty()) {
        TreeNode curr = treeNodeStack.pop();
        if (curr.left != null) {
            treeNodeStack.push(curr.left);
        }
        if (curr.right != null) {
            treeNodeStack.push(curr.right);
        }
        retVal.add(curr.val);
    }
    Collections.reverse(retVal);
    return retVal;
}

Trie

String

substring palindrome: 516, 647.

https://leetcode.com/submissions/detail/121291766/
https://leetcode.com/submissions/detail/121292245/

DP State transition: dp[i][j] means taking char from i to j of original string, and check next char if it equals to the leading char of current row. If so, take the previous result dp[i + 1][j - 1] to update.
Cached DFS: https://discuss.leetcode.com/topic/78603/straight-forward-java-dp-solution