Coding Symmary

03 Dec 2015

Coding Summary by Keywords and Type

Original from posts ###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，区别在于:

将res放入ret的条件不一样
- Permu - len(res) = len(S)
- Combin - len(res) == k
- Combin Sum - target == 0
- Subsets - 只要生成新的res就要存一次
  前三种题存过结果只后程序应该return
循环内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

###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(意义不大)

######Dup with tree

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

###Matrix

###Play With Math

###Dynamic Programming

Unique Paths
Unique Paths II
Minimum Path Sum
Triangle

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

Cannot sort, or swap
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

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

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

Array Two Pointers

The basic template of doing ‘Sums’

####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 主要想法是先搜索到不能再底层然后再往上走 #####复杂度问题

组合的话就是O(n^2)
排列的话就是(n!)
Permutations 尝试把DFS的
Subsets
N Queens
Palindrome Partitioning
Combinations Sum
Word Ladder 无向图求最短路径用BFS, 用Level Order搜索法 注意, 因为是单词, 所以做搜索的时候是按字母变化来

#####Word Ladder II

最短的是什么
所有最短的是啥
对所有点进行分层BFS
对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!)

Find all solutions
Permutations / Subsets

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

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

###Data Structure

####Stack implement

Min Stack
Queue by Two Stacks
Mid Stack
Sort Stack

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

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

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

##Definetly Redo

##记忆思考方式

##Need Understand

##New

Absolute Minimum

##Some Note

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

Alibi

Coding Symmary

Coding Summary by Keywords and Type

Array Two Pointers

Related Posts

LC Container With Most Water/Trapping Rain Water/Largest Rectangle in Histogram 30 Dec 2015

LC 128 Longest Consecutive Sequence 30 Dec 2015

LintCode List Rotate List 25 Dec 2015