Skip to content

Latest commit

 

History

History
656 lines (533 loc) · 20.7 KB

coding_index.md

File metadata and controls

656 lines (533 loc) · 20.7 KB

Coding Summary by Keywords and Type

###Permutation & Combination Type

  • Permutations
  • Permutations II
  • Permutation Sequence
  • Next Permutation
  • Combinations
  • Combination Sum
  • Combination Sum II
  • Letter Combination of a Phone Number
  • 找零钱 I == Combination Sum I
  • 找零钱 II 求ways最好就不要用dfs了，最好方法是O(m*n)
  • Subset
  • Subset II

####总结 Permutations II, Combinations, Combinations Sum II 和Subset II都是DFS， 区别在于:

  1. 将res放入ret的条件不一样

    • Permu - len(res) = len(S)
    • Combin - len(res) == k
    • Combin Sum - target == 0
    • Subsets - 只要生成新的res就要存一次
      前三种题存过结果只后程序应该return

  2. 循环内call recursion时的输入变量不一样

    • Permu - permu_helper(num[:i] + num[i+i:], res, ret)(除了S[i])
    • Combin - comb_helper(i+1, n, k, res, ret)(S[i+1:])
    • Combin Sum - comb_sum_helper(num[i:], target - n, res, ret)(S[i:])
    • Subsets - sub_helper(S[i+1:], res, ret)(S[i+1:])
      S[i+1:]``决定了res内是不会有重复项的(除非S本身就有重复), S[i:]```让当前元素可以重复使用

#####Note

  • II类去重题相比较I类题唯一的差别就是在循环的第一行需要checkif i > 0 and S[i] == S[i-1]: continue
  • 注意II类题都需要先sort, 因为去重是判断前项相等否
  • 普通题目看情况如果要求输入时res内的元素有序那也需要sort
  • Comb Sum题有一点点特殊在于在循环内需要判断target - num < 0: continue
  • Comb Sum II和I比题目有点点变化在于，数字不能无限重取，只能有限重取,
    所以是comb_sum_II_helper(num[i+1:], target - n, res, ret)
  • 记得尽量用enumerate

#####复杂度O(n)

  • Permutation： T(n) = n * T(n-1) + O(1)所以是O(n!)

  • Combination and Subsets
    运用递归公式

    T(n) = T(n-1) + T(n-2) + T(n-3) + ... + T(1) + O(1)
     = 2T(n-2) + 2T(n-3) + ... + 2T(1) + 2O(1)
     = 4T(n-3) +4T(n-4) + 4(T1) + 4O(1)
     = 2^(3-1)T(n-3) + ... + 2^(3-1)O(1)
     = 2^(n-1-1) * T(n-n+1) + ... + 2^(n-1-1)O(1)
     = 1/4 * 2^n * T(1) + 1/4 * 2^n * O(1)
     = O(2^n)
  • Gray Code
  • Generate Parentheses
  • Valid Parentheses
  • Longest Valid Parentheses
  • Palindrome Number
  • Valid Palindrome
  • Palindrome Partitioning
  • Palindrome Partitioning II

###Tree Traversal

  • Binary Tree Inorder Traversal
  • Binary Tree Preorder Traversal
  • Binary Tree Postorder Traversal
  • Binary Tree Level Order Traversal
  • Binary Tree Level Order Traversal II
  • Binary Tree Zigzag Level Order Traversal
  • Construct Binary Tree from Preorder and Inorder Traversal
  • Construct Binary Tree from Inorder and Postorder Traversal
  • Same Tree
  • Balanced Binary Tree
  • Symmetric Tree
  • Maximum Depth of Binary Tree
  • Minimum Depth of Binary Tree

###Binary Search Tree

  • Convert Sorted Array to Binary Search Tree
  • Unique Binary Search Trees
  • Unique Binary Search Trees II
  • Validate Binary Search Tree
  • Recover Binary Search Tree

###类Tree(以tree作为Data Structure的题目)

  • Path Sum
  • Path Sum II
  • Populating Next Right Pointers in Each Node
  • Populating Next Right Pointers in Each Node II
  • Sum Root to Leaf Numbers
  • Flatten Binary Tree to Linked List
  • Binary Tree Maximum Path Sum

###Array(意义不大)

  • Maximum Subarray
  • Convert Sorted Array to Binary Search Tree
  • Merge Sorted Array
  • Remove Duplicates from Sorted Array
  • Remove Duplicates from Sorted Array II
  • Search in Rotated Sorted Array
  • Search in Rotated Sorted Array II
  • Median of Two Sorted Arrays
  • Remove Element

###List(意义不大)

  • Linked List Cycle
  • Linked List Cycle II
  • Remove Duplicates from Sorted List
  • Remove Duplicates from Sorted List II
  • Merge Two Sorted Lists
  • Remove Nth Node From End of List
  • Partition List
  • Reverse Linked List II (Why only II??)
  • Insertion Sort List (Insertion Sort)
  • Copy List with Random Pointer
  • Merge k Sorted Lists
  • Rotate List
  • Sort List (Merge Sort)
  • Reorder List
  • Reverse Nodes in k-Group

######Dup with tree

  • Flatten Binary Tree to Linked List
  • Convert Sorted List to Binary Search Tree

###Matrix

  • Search a 2D Matrix
  • Spiral Matrix
  • Spiral Matrix II
  • Set Matrix Zeroes
  • Valid Sudoku
  • Sudoku Solver

###Play With Math

  • Reverse Integer
  • Roman to Integer
  • Intger to Roman
  • Pascal's Triangle
  • Pascal's Triangle II

###Dynamic Programming

  • Unique Paths
  • Unique Paths II
  • Minimum Path Sum
  • Triangle
  • Climbing Stairs
  • Jump Game
  • Jump Game II
  • Palindrome Partitioning II
  • Word Break
  • Decode Ways
  • Maximum Subarray(勉强)
  • LIS
  • Longest Palindrome Substring(上课题没用)
  • LCS * 2
  • Edit Distance
  • Distinct Subsequences
  • Interleaving String
  • Container With Most Water
  • Unique Binary Search Trees
  • Unique Binary Search Trees II
  • Best Time to Buy and Sell Stock III
  • Maximal Rectangle (DP isn't the best way)
  • Scramble String (别用)

##From NC DP Class

###模板

  • 状态 state: 灵感, 创造力, 储存小规模问题的结果
  • 转移方程 transfer function: 状态之间的联系, 怎么通过小的状态来算大的状态
  • 初始化 initialization: 最极限的小状态是什么
  • 答案 answer: 最大的那个状态是什么

###Clues

  1. Cannot sort, or swap
  2. Satisfy:
  • Find a maximum/minimum result
  • Decide whether something is possible or not
  • Count all possible solutions(Doesn't care about solution details, only care about the count or possibility)

###Types of DP

####1. Matrix DP 20% (Triangle, Unique Path, ...)

  • state: dp[x][y]表示从起点走到坐标 (x,y) 的xxx
  • function: 研究下一步怎么走
  • initialize: 起点
  • answer: 终点
  • 复杂度一般为O(n^2)

#####Triangle

  • status: dp[x][y]表示从bottom走到top每个坐标的最短路径
  • function: dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j]
  • initialize: dp[-1][j] = triangle[-1][j]
  • answer: dp[0][0] (比较奇怪，因为是由下至上)

#####Unique Path | Unique Path II

  • state: dp[x][y]表示从起点走到 (x,y) 的path数
  • function: dp[x][y] = dp[x-1][y] + dp[x][y-1] | if 障碍, dp[x][y] = 0
  • initialize: dp[0][y] = 1, dp[x][0] = 1
  • answer: dp[M-1][N-1]

#####Minimum Path Sum

  • state: dp[x][y]表示从起点走到x,y的minimum path sum
  • function: dp[x][y] = min(dp[x-1][y], dp[x][y-1]) + grid[x][y]
  • initialize: dp[0][0] = grid[0][0], dp[x][0] = dp[x-1][0] + grid[x][0], dp[0][y] = dp[0][y-1] + grid[0][y]
  • answer: dp[M-1][N-1]

####2. One Sequence DP 40%

  • state: dp[i]表示前i个位置/数字/字母，以第i个为...
  • function: dp[i] = dp[j] ...j 是i之前的一个位置
  • initialize: dp[0] = ...
  • answer: dp[N-1]
  • 复杂度一般为O(n^2)

######Climbing Stairs

  • state: dp[i]表示爬到前i个台阶时的方法数
  • function: dp[i] = dp[i-1] + dp[i-2]
  • initialize: dp[0] = 1, dp[1] = 2
  • answer: dp[N-1]

######Jump Game | Jump Game II

  • state: dp[i]表示能否跳到第i个位置O(n^2) (还有一种O(n)的dp, 见方法2) | dp[i]表示跳到这个位置最少需要多少步.
  • function: dp[i] = for j in (i-1 ... 0) if dp[j] and j能跳到i) | min(dp[j] + 1, j < i and j能跳到i)
  • initialize: dp[0] = True | dp[0] = 0
  • answer: dp[N-1]

######Palindrome Partitioning II

  • state: dp[i]表示前i-1个字符组成的字符串需要最少几次cut
  • function: dp[i] = min( dp[j]+1, j<i and j+1 ~ i 这一段是一个palindrome) (这里需要用另外一个数组来储存是否是palindrome))
  • initialize: dp[0] = N-1最少N-1次cut就行了
  • answer: dp[N]-1(这里有些不一样，主要原因是)

######Word Break

  • state: dp[i]表示前i-1个字符能否被完美切分

  • function： dp[i] = for j in (i-1 ... 0) if dp[j] and j ~ i是一个字典中的单词)

  • initialize: dp[0] = True

  • answer: dp[N] (这里也是比较特殊，因为是i-1个字符，不能从0算起)

    注意j的枚举 -> 枚举单词长度 O(NL) N: 字符串长度 L:最长单词的长度

######Longest Increasing Subsequence 最长上升子序列 (Not in Leetcode)

  • state: dp[i]表示前i个数字中最长的LIS长度(错误) dp[i]表示第i个数字结尾的LIS长度(正确)
  • function: dp[i] = max(dp[j]+1, j<i and a[j] <= a[i])
  • initialize: dp[0..n-1] = 1
  • answer: max(dp[0..n-1]) 任何一个位置都可能为开始, 所以所有都要初始化为1, 因为最少LIS是1

######Decode Ways

  • state: dp[i]表示前i-1个数字的DW

  • function:

    dp[i]   = 0        # if A[i] == 0 and A[i-1] not in [1,2]
       += dp[i-1]  # if A[i] != 0
       += dp[i-2]  # if 10 <= int(A[i-2:i]) <= 26

  • initialize: dp[0] = 1

  • answer: dp[N] (这里比较特殊，因为是前i-1个数字，且dp[0]只是作为一个起始数字来的)

####3. Two Sequences DP 40%

  • state: dp[i][j]代表了第一个sequence的前i个数字/字符配上第二个的sequence的前j个...
  • function: dp[i][j] = 研究第i-1个和第j-1个的匹配关系
  • initialize: dp[i][0], dp[0][j]
  • answer: dp[len(s1)][len(s2)]
  • 复杂度一般为O(m*n)

######Longest Common Subsequence (Not in Leetcode)

  • state: dp[i][j]表示前i个字符配上前j个字符的LCS的长度

  • function:

    dp[i][j] = dp[i-1][j-1] + 1           # if a[i-1] == b[j-1]
         = max(dp[i][j-1],dp[i-1][j]) # if a[i-1] != b[j-1]

  • initialize: dp[i][0] = 0, dp[0][j] = 0

  • answer: dp[M][N]

######Longest Common Substring (Not in Leetcode)

  • state: dp[i][j]表示前i个字符配上前j个字符的LCS的长度(一定以第i个和第j个结尾的LCS)

  • function:

    dp[i][j] = dp[i-1][j-1] + 1 # if a[i-1] == b[j-1]
         = 0                # if a[i-1] != b[j-1]

  • initialize: dp[i][j] = 0, dp[0][j] = 0

  • answer: max(dp[0...len(a)][0...len(b)])

######Edit Distance

  • state: dp[i][j] a的前i个字符配上b的前j个字符最少要用几次编辑使得他们相等

  • function:

    dp[i][j] = dp[i-1][j-1]                                    # if a[i] == b[j]
         = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])) + 1  # if a[i] != b[j]

  • initialize: dp[i][0] = i, dp[0][j] = j

  • answer: dp[M][N]

######Distinct Subsequence(需要再领会一下)

  • state: dp[i][j]表示T的前i个字符和S的前j个字符的DS个数

  • function:

    dp[i][j] = dp[i][j-1] + dp[i-1][j-1] # if T[i-1] == S[j-1]
         = dp[i][j-1]                # if T[i-1] != S[j-1]

  • initialize: dp[i][0] = 0, dp[0][j] = 1

  • answer: dp[M][N]

    大概意思就是， 因为算的是S的子串和T匹配的方法， 所以一旦S[:j-1]和T[:i]有x种匹配方法时
    S[:j]必定也至少和T[:i]有x种匹配方法，但尤其当S[j-1]==T[i-1]的时候，需要再加上S[:j-1]和T[:i-1]的匹配方法数
    注意分清M,i和N,j对应T和S，这个很特殊因为必须是S的子串和T相同

######Interleaving String

  • state: dp[i][j]表示s1的前i个字符配上s2的前j个字符在s3的前i+j个字符是不是IS

  • function:

    dp[i][j] = True  # if dp[i-1][j] and s1[i-1] == s3[i-1+j]
         = True  # if dp[i][j-1] and s2[j-1] == s3[i+j-1]
         = False # else

  • initialize: dp[0][0] = True

  • answer: dp[M][N]

####4. Interval DP

  • state: dp[i][j] 代表从i到j这一段区间...
  • function: dp[i][j] = max/min/sum(dp[i][k], dp[k+1][j])
  • initialize: dp[i][i] = ?
  • answer: dp[1][n]

######Merge Stone 石子归并

####5. Tree DP ######Binary Tree Maximum Path Sum

####6. States Compressing DP(不需要知道) ####7. Knapsack

###总结

####复杂度 直接看循环嵌套层数

####关于取dp[N]还是dp[N-1]还有dp[N]-1

  1. 首先先分析dp维度，Matrix和Two Sequence dp都是二维，One Sequence是一维
  2. Matrix dp一般都是初始(0,0)跳到(M-1,N-1)所以取的是dp[M-1][N-1]
  3. 如果dp[i]或者dp[i][j]表示前i个什么的时候，需要以N/MN作为结尾，主要原因是这种情况下前0个字符串是没有意义的，至少从1开始，所以取dp的时候也是从dp[1]开始才有意义，所以dp[i]的含义是前i-1个东西的性质，而dp[0] or dp[0][0]需要强制赋值
  4. 至于dp[N] - 1纯粹是因为Palindrome题目比较特殊，实际我们算的cut-1才是结果

####已知dp问题然后回问满足dp条件的结果 一般这种情况就是根据已知的dp matrix和结论，从最后开始往前回溯，满足的就挑进去，不满足的就不放来解决.

Array Two Pointers

The basic template of doing 'Sums'

  • Two Sum

  • 3Sum

  • 3Sum Closest

  • 4Sum

  • Trapping Water (especially the way to think)

  • Container With Most Water

  • Stock 系列

  • Candy

####Cannot Classify(记住思路)

  • Search Insert Position
  • Container With Most Water (In Two pointers)
  • Count and Say
  • Candy

##From Class ###Binary Search

  • Find First Occurance in Sorted Array (Basic)
  • Find Last Occurance in Sorted Array
  • Search Insert Position (Same as search for kth big)
  • Search for a Range (My way is wrong, should use binary for both bounds)
  • Search in Rotated Sorted Array
  • Search in Rotated Sorted Array II
  • Search a 2D Matrix
  • Search a 2D Matrix II (prev[-1] may larger than cur[0])
  • Median of Two Sorted Arrays (Need to look back for annie's answer, she has three solutions)
  • -> Find kth in two Sorted Arrays

######From zz

  • Divide Two Integers (This is not binary search since not allowed to use multiply. Bit calculation)
  • Pow(x, n)
  • Sqrt(x)

####Three steps reverse

  • Recover Rotated Array
  • -> Recover Rotated String
  • -> Rotate String
  • -> Reverse Sentence
def binary_search(target, A):
    if len(A) == 0:
        return -1
    start = 0
    end = len(A) - 1
    while start + 1 < end:
        mid = start + (end - start) / 2    # Avoid stack overflow
        if A[mid] == target:
            end = mid
        elif A[mid] > target:
            start = mid
        else:
            end = mid
    # Check start and end
    if A[start] == target:
        return start
    if A[end] == target:
        return end
    return -1

###Divide & Conquer (Most BT Problem)

  • Merge Sort
  • Quick Sort
  • Tree Traverse
  • Maximum Depth of Binary Tree
  • Balanced Binary Tree
  • Binary Tree Maximum Path Sum

This will require extra space

把一个任务划分成几个小任务 一般来说分治是有return的，但是Recursion一般是没有的

Binary Tree Level Order Traversal 3 ways

  • 2 Queues
  • 1 Queue + dummy node
  • 1 Queue 双重循环 (Best)

Check BFS and DFS template

####Not in Leetcode

  • Print BST Keys in Give Range
  • Implement Iterator of BST
  • Insert a Node in a Binary Search Tree
  • Delete a Node in a Binary Search Tree
  • Least Common Ancestor 这个和CC150不太一样, 是从底走, NC答案是Divide an Conquer, CC150是recursion
  • (tarjan算法)

###DFS 主要想法是先搜索到不能再底层然后再往上走 #####复杂度问题

#####Word Ladder II

  1. 最短的是什么

  2. 所有最短的是啥

  3. 对所有点进行分层BFS

  4. 对DFS层进行搜索

###Graph

  • 图上的BFS需要用HashTable去重

#####Clone Graph

#####拓扑排序Topological sorting 主要是入度为零

Q.offer(....)
while (!Q.empty()) {
    Node head = Q.poll();
    for (int i = 0; i < head.neighbors.size(); i++) {
        inDegree[neighbor] --;
        if ( .. == 0) {
            Q.offer(.xxx)
        }
    }
}

###DFS vs BFS #####DFS - O(2^n), O(n!)

  1. Find all solutions
  2. Permutations / Subsets

#####BFS - O(m) O(n)

  1. Graph Traversal(每个点都遍历一次)
  2. Find shorted path in a simple graph

###Data Structure

####Stack implement

####Heap #####Median Number(应该是CC150)里的题

  • 要求插入一个数
  • 要求return median number

#####Majority Number 去想关于数据结构的题目的时候, 只需要考虑数据结构里处理的次数就行了

##Definetly Redo

  • Regular Expression Matching (Redo)

  • Wildcard Matching (Redo)

  • Max Points on a Line (Redo)

  • Word Ladder II (Redo)

  • Word Break II

  • Text Justification (Redo)

  • String to Integer (atoi) (只需要注意['+','-'] 和<-sys.maxint >sys.maxint)

  • Substring with Concatenation of All Words (Redo)

  • Minimum Window Substring (Redo)

  • Longest Substring Without Repeating Characters

  • Sum系列 (细节问题，得再写一遍)

  • Longest Valid Parentheses (值得redo)

  • Insert Interval (Redo, 思考方式分三种情况讨论的细节)

  • Merge Interval (sort and max!!!)

  • Implement strStr() (KMP因为高频再小做一两次)

  • Decode ways

  • Longest Palindrome Substring

  • First Missing Positive (Redo) (check 死循环!!!)

  • Recover Binary Search Tree (Redo)

  • Convert Sorted List to Binary Search Tree (Redo)

  • Largest Rectangle in Histogram

  • Maximal Rectangle

  • Longest Concecutive Sequence

  • Count and Say (Linkedin面经) (Trick Part是读出来的时候是insert(0))

  • Simplify Path

  • Restore IP Addresses

  • Rotate List

  • Maximum Path Sum(BT)

  • Rotate Image

  • Spiral Matrix * 2

  • LRU

  • Surrounded Regions

  • Gas Station

  • Gray Code

  • Permutation Sequence (小redo一下)

  • Next Permutation (Redo，记住思考的方式，find, swap)

  • Maximum Subarray

  • Max Product of Subarray

  • Populating Next Right Pointers in Each Node

  • Populating Next Right Pointers in Each Node II

  • Construct Binary Tree from Inorder and Postorder Traversal

  • Construct Binary Tree from Preorder and Inorder Traversal

  • BFS every traversal

  • Flatten BST to doubly linkedlist

  • Flatten BST to Linked List

  • Median of Two Sorted Arrays

  • Insertion Sort / Merge Sort Linked List

##记忆思考方式

  • Validate Binary Search Tree (需要记忆如何思考这题)
  • Trapping Water (especially the way to think)
  • Container With Most Water
  • Stock 系列
  • Candy
  • Divde two integers
  • Single Number II

##Need Understand

  • 最大子矩阵(NC wechat)
  • 最大子矩阵乘积
  • 子数组最大差(NC wechat)
  • Majority Number 好好看看
  • Find a Peak
  • Recover Rotated Sorted Array
  • Construct Max Tree (NC wechat)
  • NC DP 最小调整代价
  • BACKPACK

##New

##Some Note

  1. 一定要看清题，比如这次就被问了find all palindrome，但是理解成palindrome partitioning了，所以错了
  2. 再仔细确认下怎么算recursion的big O