Skip to content

Latest commit

 

History

History
238 lines (216 loc) · 8.98 KB

必会CoreProblems.md

File metadata and controls

238 lines (216 loc) · 8.98 KB
Raw

每日手写 Cheatsheet

Advanced

递归模板 - 排列组合

二分模板 - 有序数组的第一个和最后一个

二叉树遍历 - DFS迭代遍历+BFS遍历

分治算法 - MergeSort and QuickSort and divide&conquer

二叉搜索树 - validate, insert, delete and iterator

Graph - Topological Sort

  • BFS Topological Sort Template
  • Search: Permutation DFS, Subsets DFS, BFS

Stack

Heap

  • Template: Heapfiy and implementation

Trie

  • Implementation
  • Word Search I && II

Templates

  • 什么时候Permutation模板?什么时候Subset模板？
  • DFS: Find ALL solutions
    • O(N!) - permutation
    • O(2^N) - subset
  • BFS: Find SHORTEST solution
    • O(N)

DFS Search - Permutation - O(N!) - 所有叶节点才是结果

* 遍历树的叶子节点才是result
* 为什么`list.contains(nums)` 不优化为O(1)? 反正时间是O(N！),用了也不影响, 况且能这么跑的基本N<20
* Permutation: 每一步都要考虑全部

    public List<List<Integer>> permute(ArrayList<Integer> nums) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> state = new ArrayLsit<>();
        backtrack(result, list, nums);//Traverse entire search space
    }

    private backtrack(List<List<Integer>> result, List<Integer> list, ArrayList<Integer> nums) {
        if (list.size() == nums.size()) {
            result.add(new ArrayList<>(list)); //Important: Copy current state
            return;
        }
        for (Integer num: nums) {
            if (!result.contains(num)) {
                list.add(num);
                backtrack(result, list, nums);
                list.remove(list.size()-1); //Remove last one
            }
        }
    }

DFS Search - Subset - O(2^N) - 所有节点都是subset

* 技巧:传递start,这样前面的不会再被考虑
* 树中的每一个节点(不仅仅是叶节点)都是一个结果
* Subset: 每一步都不需要考虑前面的元素
* Subset II: 有重复, 先排序, 然后在同一层上每个数只考虑一次(第一个), 但剩余的元素会顺着向叶子传下去 `if (i != start && nums[i] == nums[i-1] {continue;}`
* 如何考虑参数设计? 画Search Space图, 看要怎么去传递信息

     public List<List<Integer>> subsets(ArrayList<Integer> nums) {
         List<List<Integer>> result = new ArrayList();
         Collections.sort(nums);
         backtrack(result, new ArrayList<Integer>(), nums, 0);
     }

     public backtrack(List<List<Integer>> result, List<Integer> list, ArrayList<Integer> nums, int start){
         result.add(new ArrayList<Integer>(list));

        for (int i = start; i < nums.length; i++) {
            list.add(num);
            backtrack(result, list, nums, start+1);
            list.remove(list.size()-1); //Remove last one
        }
     }

Backtrack Template

def backtrack(candidate):
    if find_solution(candidate):
        output(candidate)
        return
    
    # iterate all possible candidates.
    for next_candidate in list_of_candidates:
        if is_valid(next_candidate):
            # try this partial candidate solution
            place(next_candidate)
            # given the candidate, explore further.
            backtrack(next_candidate)
            # backtrack
            remove(next_candidate)

Template: Sliding Window

for (i = 0; i < n; i++) {
    while (j < n) {
        if (满足条件) {
            j++;
            更新j状态
        } else (不满足条件){
            break;
        }
    }
    更新i状态
}

Template: Union Find

public class UnionFind {
    private int[] father = null;
    int find(int x) {
        if (father[x] == x) {
            return x;
        }
        //路径压缩
        return father[x] = find(father[x]);
    }

    //合并的root老大哥, 而不是小弟
    void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            father[rootA] = rootB;
        }
    }
}

Template: BinarySearch按答案二分

int start = 1, end = max;  //1. 找到可行解
while (start + 1 < end) { 
    int mid = start + (end - start)/2; //2.猜答案
    if (check(mid)) { //3. 检查答案
        start = mid; //4. 调整搜索范围
    } else {
        end = mid; //4. 调整搜索范围
    }
    //5.检查start, end
}

QuickSelect: O(N)选出第K大

public int partition(int[] nums, int l, int r) {
  //初始化左右指针和pivot
  int left = l, right = r;
  int pivot = nums[left];

  //进行partition
  while (left < right) {
    while (left < right && nums[right] >= pivot) {
      right--;
    }
    nums[left] = nums[right];
    while (left < right && nums[left] <= pivot) {
      left++;
    }
    nums[right] = nums[left];
  }

  //返回pivot到数组
  nums[left] = pivot;
  return left;
}