Skip to content

Latest commit

 

History

History
604 lines (528 loc) · 20.4 KB

九章基础班.md

File metadata and controls

604 lines (528 loc) · 20.4 KB
Raw

九章算法初级班

Leetcode to lintcode mapping: https://www.1point3acres.com/bbs/thread-453640-1-1.html

  • 面经
    • glassdoor, careercup
    • 一亩三分地, mitbbs

Lecture 1 - strStr & Coding Style

Questions

LINT13 strStr - 常见误区

  • Point 1: 知识体系: 不要浪费时间准备KMP, 考点就是双重循环
  • Point 2: 代码风格: 注意命名,缩进,空格等代码风格
  • Point 3: 编程习惯: 注意边界条件,测试

Subsets

  • 在刷题时, 总结归类相似题目
  • 找出适合同一类题目的模板程序 - 节约面试时间
private void subsetsHelper(ArrayList<ArrayList<Integer>> result,
                ArrayList<Integer> list,
                int[] nums,
                int pos) {
    result.add(new ArrayList<Integer>(list)); //NOTE: must have new
    for (int i = pos; i < nums.length; i++) {
        list.add(i);
        subsetsHelper(result, list, nums, i+1);
        list.remove(list.size() - 1);
    }
}

Subsets II - 数字有重复,Subsets不能重复

特变:

  1. Arrays.sort(nums);
  2. 每个数字只有一个有效

递归模板 - 排列组合模板

  • 分为两类 - 排列 和 组合
  • 实用范围
    • 几乎所有搜索
  • 根据具体题目要求进行改动
    • 什么时候输出
    • 哪些情况需要跳过
  • 适用该模板的题目
    • Permutations
    • Unique Permutations
    • Combination Sum
    • Letter Combination of a Phone Number
    • Palindrome Partitioning
    • Restore IP Address
    • Palindrome Partitioning
    • N-Queens
    • Combination Sum II
    • Subsets II
    • Word Break II
    • Word Ladder II
    • Word Squares II

Lecture 2 - Binary Search & Sorted Array

Problems

  • Binary Search
  • Rotated Sorted Array - 重要
  • Find median
  • Reverse

Summary

  • Binary Search Template (4 key points)
  • Rotated Sorted Array
    • Find min
    • Find target
    • Why O(N) with duplicates?
  • Find Median in Two Sorted Array
    • Find kth
  • Reverse in 3 steps
    • 45123 => 12345 in O(1) space
    • Reverse left 45=>54
    • Reverse right 123 =>321
    • Reerse all => 12345

小公司的前途分析网站

  • techcrunch
  • 36kr
  • pingwest

二分模板 - 去想要找第一个还是最后一个

Four keypoints:

  • start + 1 < end
  • start + (end - start)/2
  • A[mid]==, <, >
  • A[start], A[end]?target
//Find FIRST occurence of target
//Q: How to find the last occurence of target?
int binarySearch(int[] A, int target) {
    if (A.size() == 0) {
        return -1;
    }

    int start = 0;
    int end = A.size() - 1;
    int mid;

    while(start + 1 < end) {
        mid = start + (end - start)/2;
        if (A[mid] == target) {
            end = mid;
        } else if(A[mid] < target) {
            start = mid;
        } else if (A[mid] > target) {
            end = mid;
        }
    }

    if (A[start] == target) {
        return start;
    }

    if (A[end] == target) {
        return end;
    }

    return -1;
}

Find First and Last Position of Element in Sorted Array

  • 套用模板

Search Insertion

  • 套用模板

Search a 2D Matrix

  • 套用模板

Search a 2D Matrix II

  • 特殊的递增矩阵
  • 只能利用左下角和右上角
  • 从左下角开始走向右上,每次删除行或列

LC4 Median of Two Sorted Arrays

Find Kth in two sorted arrays

LINT39 Recover Rotated Sorted Array

LC796 Rotate String

LC151 Reverse Words in a String

Lecture 3 - Binary Tree & Divide Conquer

Problem

DFS Template

https://www.jiuzhang.com/solutions/dfs-template/

// Template 1: Traverse
public class Solution {
    public void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        // do something with root
        traverse(root.left);
        // do something with root
        traverse(root.right);
        // do something with root
    }
}


//Tempate 2: Divide & Conquer
public class Solution {
    public ResultType traversal(TreeNode root) {
        // null or leaf
        if (root == null) {
            // do something and return;
        }
        
        // Divide
        ResultType left = traversal(root.left);
        ResultType right = traversal(root.right);
        
        // Conquer
        ResultType result = Merge from left and right.
        return result;

分治法

  • Traverse和Divide&Conquer的区别
    • Traverse不用return value
    • Divide&Conquer有return value
  • MergeSort和QuickSort
  • 大部分Binary Tree都可以这么解决

Binary Tree Maximum Path Sum

LC236 Lowest Common Ancestor

Template - BFS

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List result = new ArrayList();

        if (root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            ArrayList<Integer> level = new ArrayList<Integer>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode head = queue.poll();
                level.add(head.val);
                if (head.left != null) {
                    queue.offer(head.left);
                }
                if (head.right != null) {
                    queue.offer(head.right);
                }
            }
            result.add(level);
        }

        return result;
    }
}

Lecture 4 - Dynamic Programming I

Problem

  • NOT DP - all solutions
  • DP
  • Triangle
  • Minimum Path Sum
  • Unique Paths
  • Unique Paths II
  • Climbing Stairs
  • Jump Game
  • Jump Game II
  • Palindrome Partitioning II
  • Word Break

Triangle

  • Traverse void dfs(int x, int y, int sum)
  • Divide & Conquer int dfs(int x, int y)
  • Memorization - DP

动态规划

  • 标准写法
    • Topdown: 记忆化搜索 - 好写, 但无法进行空间优化
    • Bottomup: 循环写法 - 可以进行空间优化
  • DP的三种类型
    • min/max
    • count
    • true/false
  • 不是DP的类型
    • 所有具体方案
    • 输入是集合,而非序列
  • 解决方式
    • State:走什么
    • Transition Function:如何走
    • Init:起点
    • Result:终点
  • 类型
    • 坐标型
      • state: f[x][y] 表示我从起点走到坐标x,y……
      • function: 研究走到x,y这个点之前的一步
      • intialize: 起点
      • answer: 终点
    • 单序列+状态
      • f[i]: "前i"个位置/数字/字母,(以第i个为结尾的)...
      • f[i] = f[j] j是i之前的例子
      • intialize: f[0]..
      • answer: f[n-1]..
    • 双序列
    • 背包型
    • 区间型
    • 划分型

Lecture 5 - Dynamic Programming II

Problem

  • Two Sequences - 常用
  • Backpack

Two Seqeunces

  • state: f[i][j]代表了第一个sequence的前i个数字/字符 配上第二个sequence的前j个...
  • function: f[i][j] = 研究第i个和第j个的匹配关系
  • intialize: f[i][0] 和 f[0][i]
  • answer: f[s1.length()][s2.length()]

Knapsack

Lecture 6 - Linked List

Problem - Use Dummy Node

  • Dummy Node
  • Fast/Slow Node: slow = head, fast = head.next
  • List with Data Structure: Heap, Map, Tree

Lecture 7 - Graph & Search

Problems

  • Graph
    • Clond Graph
    • Topological sorting - BFS - 每次找入度为0的点
public List<GraphNode> topologicalSort(ArrayList<GraphNode> graph) {
    List<GraphNode> topOrder = new ArrayList<>();
    //Calculate indegree
    Map<GraphNode, Integer> indegree = new HashMap<>();
    for (GraphNode node: graph) {
        for (GraphNode neighbor: node.getNeighbor()) {
            inCount.put(nieghbor, inCount.getOrDefault(neighbor,0)+1);
        }
    }

    //Inqueue all nodes with indegree=0
    Queue<GraphNode> queue = new LinkedList<GraphNode>();
    for (GraphNode node: graph) {
        if (!inDegree.contains(node)) {
            queue.offer(node);
        }
    }

    while (!queue.isEmpty()) {
        GraphNode node = queue.poll();
        topOrder.add(node);
        for (GraphNode neighbor: node.getNeigbors()) {
            inDegree.put(inDegree.get(neighbor)-1);
            if (inDegree.get(neighbor) == 0) {
                queue.offer(neighbor);
            }
        }
    }
    return result;
}

Search

DFS Search

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

  • 遍历树的叶子节点才是result
  • 为什么list.contains(nums) 不优化为O(1)? 反正时间是O(N！),用了也不影响, 况且能这么跑的基本N<20
    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
            }
        }
    }

Subset - 所有节点都是subset

  • 技巧:传递start,这样前面的不会再被考虑
  • 树中的每一个节点(不仅仅是叶节点)都是一个结果
     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
        }
     }

N Queens - Permutation

Permutation类型的DFS

  • 左斜对角线: X-Y = 0, -1, .. -(N-1)
  • 右斜对角线: X+Y = 0, 1, 2, .. N-1

    BFS

Subsets II

  • 1, 2a, 2b, 2c, 3
  • 在同一层只需要一个2, 所以可以跳过
if (i != start && nums[i] != nums[i-1]) {

}

Palindrome Partitioning - Subset

Word Ladder - BFS

Word Ladder II - BFS + DFS

Lecture 8 - Data Structure

  • Linear Data Structure
    • Queue
    • Stack
    • Hash
  • Tree Data Structure
    • Heap
    • Trie

Largest Rectangle in Histogram

  • 不用动规:因为动规是用来把DFS Permutation/Subset N!和2^N优化为N^2的, 而不是N^2优化为N的
  • 单调栈: 找到nums[i]左边第一个比nums[i]小的数字：单调递增栈
pubic int largestRectangleArea(int[] height) {
    if (height == null || height.length == 0) {
        return 0;
    }

    Stack<Integer> stack = new Stack<Integer>();
    int max = 0;
    for (int i = 0; i = height.length; i++) {
        int current = (i == height.length) ? -1 : height[i];
        while (!stack.isEmpty() && current <= height[stack.peek()]) {
            int h = height[stack.pop()];
            int w = stack.isEmpty()? i : i - stack.peek() - 1;
            max = Math.max(max, h*w);
        }
        stack.push();
    }
    return max;
}

Max Tree

Hash

What's the difference between HashTable, HashSet, HashMap

  • HashTable is thread safe, but slow
  • HashSet vs HashMap

LRU

Heap

Lecture 9 - High Frequency

Trie

High Frequency

  1. Single Number I, II, III => 二进制xor,三进制xor,二次遍历
  2. Majority Number I, II, III => 2个抵消, 3个抵消, k个抵消
  3. Best Time to Buy and Sale Stock I, II, III => DP
  4. Subarray I, II, III, IV
  5. 2-Sum, 3-Sum, 4-Sum, k-Sum, 3-Sum Closest
  6. Quick Questions
  7. Partition Array