刷题笔记

It does not matter how slowly you go as long as you do not stop.

如何有效学习数据结构与算法？

如何精通一个领域？

Chunk it up 切碎知识点

将数据结构与算法的基本知识点分解开来，分解结果见：数据结构与算法脑图
Deliberate Practicing 刻意练习

对分解之后的知识点进行分解训练和反复练习。
- 明白一个原则：基本功是区别业余和职业选手的根本，我们的目标是成为职业选手。
- 明白一个误区：刷一道算法题，刷一遍是完全不够的，需要一遍遍刷题。
- 明白一个事实：反复练习自己薄弱的地方，扩张舒适区，会让我们成长更快。
Feedback 反馈

反馈对于学习的作用，主要是将揉碎的知识点再串联起来，形成体系结构，这样就建立了一个 知识点-> 专项反复练习-> 建立知识体系的学习闭环。
- 即时反馈
- 主动型反馈（自己去找）
  - 高手代码，例如 Github，LeetCode（题解、Discussion）
  - 第一视角直播
- 被动式反馈（高手指点）
  - Code Review
  - 教练看你打，然后给你反馈

如何精通数据结构与算法呢？

如何反复刷题呢？答案是：五步刷题法，我们称为五毒神掌。

刷题第1遍
- 5分钟时间：读题+思考
- 若5分钟思考不出来，直接看解法，要注意：对每一道题目，思考和比较这个题的多种解法，最好是全部解法
- 背诵、默写好的解法：这是积累代码能力的一个很好的办法。
刷题第2遍
- 马上自己写 -> LeetCode提交
- 多种解法进行比较、体会 -> 优化
刷题第3遍
- 一天后，再重复做题
- 针对不同解法的熟练程度 -> 对薄弱的地方进行专项练习
刷题第4遍
- 一周后，反复回来练习相同的题目
刷题第5遍
- 面试前一周进行恢复性训练。

如何刷一道题呢？答案是：切题四件套。

Clarification: 多沟通，多思考，确保正确理解问题 （面试的时候，和面试官过一遍题目）
Possible solutions: 思考关于这个题目的所有解法，比较其优劣，优化其性能
- compare(time/space)
- optimal(加强)：例如空间换时间、升维（一维到二维） （提出多种解法，给出最优解法）
Coding: 就是不停的写，多写，提高Coding能力的唯一法宝 （代码实现）
Test cases （阐述测试样例）

工具

visualgo

bigocheatsheet

代码模板

递归代码模板 Recursion

Python

def recursion(level, param1, param2, ...): 
    # recursion terminator 
    if (level > MAX_LEVEL): 
	   # process result 
	   return 

    # process logic in current level
    process(level, data...) 

    # drill down 
    self.recursion(level + 1, p1, ...) 

    # restore current level status if needed

Java

public void recursion(int level, int param) { 
  // recursion terminator 
  if (level > MAX_LEVEL) { 
    // process result 
    return; 
  } 

  // process logic in current level
  process(level, param); 

  // drill down 
  recursion( level: level + 1, newParam); 

  // restore current level status if needed 
 
}

分治代码模板 Divide and Conquer

def divide_conquer(problem, param1, param2, ...): 
  # recursion terminator 
  if problem is None: 
	print_result 
	return 

  # divide: prepare data 
  data = prepare_data(problem) 
  subproblems = split_problem(problem, data) 

  # conquer: conquer subproblems 
  subresult1 = self.divide_conquer(subproblems[0], p1, ...) 
  subresult2 = self.divide_conquer(subproblems[1], p1, ...) 
  subresult3 = self.divide_conquer(subproblems[2], p1, ...) 
  …

  # merge: process and generate the final result 
  result = process_result(subresult1, subresult2, subresult3, …)
	
  # restore current level states if needed

查找-搜索-遍历模板

查找的特点是：

找到特定元素

搜索的特点是：

每个节点都要访问一次
每个节点仅仅访问一次
每个节点访问顺序不限

二分查找（Binary Search）

left, right = 0, len(array) - 1
while left <= right:
    mid = (left + right) / 2
    if array[mid] == target:
        # find the target
        break or return result
    elif array[mid] < target:
        left = mid + 1
    else:
        right = mid - 1

深度优先搜索（DFS, Depth First Search)

# 递归写法
visited = set()

def dfs(node, visited):
    # terminator
    if node in visited:
        return           # already visited
    
    visited.add(node)
        
    # process current node here
    # ...
    
    for next_node in node.children():
        if next_node not in visited:
         	dfs(next_node, visited)
            
# 非递归写法
def DFS(self, tree):
    if tree.root is None:
        return []
    
    visited, stack = [], [tree.root]
   	
    while stack:
        node = stack.pop()
        visited.add(node)
        
        process(node)
        
        nodes = generate_realted_nodes(node)
        stack.push(nodes)
        
    # other processing work
    ...

广度优先遍历（BFS, Breadth First Search）

def BFS(graph, start, end):
	visited = set()
    queue = []
    queue.append([start])
    
    while queue:
        node = queue.pop()
        visited.add(node)
        
        process(node)
        
        nodes = generate_related_nodes(node)
        queue.push(nodes)
    
    # other processing work
    ...

A*

def AstarSearch(graph, start, end):

	pq = collections.priority_queue() # 优先级 —> 估价函数
	pq.append([start]) 
	visited.add(start)

	while pq: 
		node = pq.pop() # can we add more intelligence here ?
		visited.add(node)

		process(node) 
		nodes = generate_related_nodes(node) 
   unvisited = [node for node in nodes if node not in visited]
		pq.push(unvisited)

归并排序

Trie

定义

Trie 树，也叫“字典树”。Trie 树也是一种树形结构。它是专门用来处理字符串匹配的数据结构，用来解决一组字符串集合中快速查找某个字符串的问题。

本质

Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起，组成一颗多个字符串共用前缀的树。这种存储方式避免了重复存储一组字符串的相同前缀子串。

实现

API

void insert(char[] text) // 插入字符串
boolean search(char[] pattern) // 查找字符串
boolean startsWith(String prefix) // 查找前缀

代码

假设字符串由a~z这26个小写字母构成，数组下标为0的位置存储指向子节点a的的指针，下标为1的位置存储指向子节点b的指针，以此类推，下标为25的位置存储指向子节点z的指针。如果某个子节点不存在，则对应下边位置处存储为null。

public class TrieNode {
    public char data;
    public TrieNode[] children = new TrieNode[26];
	public boolean isEndingChar = false;
    
    public TrieNode(char data) {
        this.data = data;
    }
}

public class Triee {
    // 根节点,存储无意义字符
    private TrieNode root = new TrieNode('/'); 
	
    // 插入字符串
    public void insert(char[] text) {
        TrieNode p = root;
        for (int i = 0; i < text.length; ++i) {
            int index = text[i] - 'a';
            if (p.children[index] == null) {
                TrieNode newNode = new TrieNode(text[i]);
                p.children[index] = newNode;
            }
            p = p.children[index];
        }
        p.isEndingChar = true;
    }
    
    // 查找字符串
    public boolean search(char[] pattern) {
        TrieNode p = root;
        for (int i = 0; i < pattern.length; ++i) {
            int index = pattern[i] - 'a';
            if (p.children[index] == null) {
                return false;
            }
            p = p.children[index];
        }
        if (p.isEndingChar == false) {
            return false;   // pattern 仅仅是前缀， 无法完全匹配
        } else {
            return true;    // 完全匹配
        }
    }
}

class Trie(object):
  
	def __init__(self): 
		self.root = {} 
		self.end_of_word = "#" 
 
	def insert(self, word): 
		node = self.root 
		for char in word: 
			node = node.setdefault(char, {}) 
		node[self.end_of_word] = self.end_of_word 
 
	def search(self, word): 
		node = self.root 
		for char in word: 
			if char not in node: 
				return False 
			node = node[char] 
		return self.end_of_word in node 
 
	def startsWith(self, prefix): 
		node = self.root 
		for char in prefix: 
			if char not in node: 
				return False 
			node = node[char] 
		return True

LeetCode 208. implement-trie-prefix-tree

class Trie {

    private TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        this.root = new TrieNode('/');
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode p = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (p.children[index] == null) {
                TrieNode newNode = new TrieNode(word.charAt(i));
                p.children[index] = newNode;
            }
            p = p.children[index];
        }
        p.isEndingChar = true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode p = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (p.children[index] == null) {
                return false;
            }
            p = p.children[index];
        }
        if (p.isEndingChar) return true;
        else return false;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode p = root;
        for (int i = 0; i < prefix.length(); i++) {
            int index = prefix.charAt(i) - 'a';
            if (p.children[index] == null) {
                return false;
            }
            p = p.children[index];
        }
        return true;
    }

    class TrieNode {
        public char data;
        public TrieNode[] children = new TrieNode[26];
	    public boolean isEndingChar = false;
    
        public TrieNode(char data) {
            this.data = data;
        }
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

性能

时间复杂度

如果在一组字符串中，频繁地查询某些字符串，用 Trie 树会非常高效。

构建 Trie 树的过程，需要扫描所有的字符串，因此时间复杂度为 O(N)，其中N 为所有字符串长度之和。

构建 Trie 树的过程，时间复杂度较高，但是一旦构建成功，后续查询操作会非常高效。每次查询时，若查询的字符串长度为k,那么我们只需要对比大约 k个节点，就能完成查询操作，与原来的那组字符串长度和个数都没有关系。因此，构建 Trie 树之后，查询操作的时间复杂度为 O(k), 其中 k 表示要查找的字符串的长度。

空间复杂度

从前面的实现，可以看出，Trie 树的每个节点都需要维护一个长度为26的数组，如果字符串不仅包含小写字母，而且还包含大写字母，数字以及中文等，那需要的存储空间就更多了。Trie 树本质是为了避免重复存储相同的公共前缀，但是在重复的前缀不多的情况下，Trie 树不但不能节省内存，还有可能会浪费更多的内存。

Trie 树是一种空间换时间的实现，尽管比较耗费空间，但是查找确实高效。

Trie 树的应用

Trie 树解决了在一组字符串集合中查找字符串的问题，相同的问题，我们其实还可以通过散列表或者红黑树解决。

事实上，Trie 树在一组字符串中查找字符串的表现并不是很好，它对要处理的字符串有极其严苛的要求。

字符串中包含的字符集不能太大。字符集太大，将会浪费很多存储空间。
要求多个字符串前缀重合比较多，不然将会浪费很多存储空间。
通过指针穿起来的数据块是不连续的，而 Trie 树中用到了指针，所以对缓存不友好，性能上会打折扣。

事实上，Trie 树只是不适合精确匹配查找，而且不适合用来做动态数据的查找，这种问题更加适合用散列表或者红黑树解决。 Trie 树更加适合查找前缀匹配的字符串，例如Google时的关键词提示功能，自动补全等功能，或者是统计单词频次等问题。

UnionFind

class UnionFind {
    private int count = 0;
    private int[] parent;
    
    /* 初始化为 n 个集合*/
    public UnionFind(int n) {
        count = n;
        parent = new int[n];
    	for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    /* 确定 q 属于哪个子集合 */
    public int find(int p) {
        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }
    
    /* 合并 p 和 q 所在的集合*/
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rooP == rootQ) return;
        parent[rootP] = rootQ;
        count--;
    }
    
}

def init(p):
    p = [i for i in range(n)]
    
def union(self, p, i, j):
    p1 = self.parent(p, i)
    p2 = self.parent(p, j)
    p[p1] = p2
    
def parent(self, p, i):
    root  = i;
    while p[root] != root:
        root = p[root] 
    while p[i] != i: # 路径压缩
        x = i
        i = p[i]
        p[x] = root
    return root

八皇后问题

https://shimo.im/docs/hV9GdhcrddcDJWwv

Dynamic Programming

Simplifying a complicated problem by breaking it down into simpler sub-problems in a recursive manner

动态规划基本理论

一个模型：多阶段决策最优解模型

动态规划一般用于解决最优问题。多阶段决策最优解模型是指动态规划适合解决的问题的模型。解决问题的过程需要经历多个决策过程，每个决策过程都对应着一组状态。动态规划的目标在于寻找一组决策序列（每个决策过程的状态），通过这组决策序列产生最终期望的求解的最优值。

三个特征

最优子结构

最优子结构是指问题的最优解包含子问题的最优解。我们可以通过子问题的最优解得到问题的最优解，也就是说，后面的状态可以通过前面的状态推导出来。

无后效性

无后效性有两层含义：

在推导后面状态的时候，我们只关心前面阶段的状态值，而不关心这个状态值的求解过程；
某个阶段的状态一旦确定，就不受之后阶段的决策影响，即状态定了就定了。

重复子问题

不同的决策序列，到达某个相同的阶段的时候，可能会产生重复的状态。

复杂度

1、状态存在更多的维度（二维、三维或者更多，甚至需要压缩）

2、状态方程更加复杂

实例

问题：给定一个n * n的矩阵 w[n][n]，矩阵存储的均为正整数。棋子从矩阵的左上角出发去右下角，每次只能向右或者是向下移动1位。从左上角到右下角有很多不同的路径可以走。规定每条路径经过的数字之和就是这条路径的长度。求从左上角到右下角的最短路径。

分析：

这个问题是否满足一个模型呢？

从 (0, 0) 出发到 (n-1, n-1)，总计2*(n-1)步，对应着2*(n-1)个阶段，每个阶段都有向右或者向下2种决策，因此每个阶段都会对应一个状态集合。问题的目标在于找到一个状态序列，从而确定 (0, 0) 出发到 (n-1, n-1)的最短距离。因此整个问题是一个多阶段决策最优解问题。

这个问题是否满足三大特征呢？

对于任意一个节点(i, j)来说，从 (0, 0) 出发到 (i, j)存在多种路线，因此可能存在重复子问题。

对于任意一个节点(i, j)来说，(i, j)这个位置的状态需要通过 (i-1, j)以及 (i, j-1)两个位置的状态来确定，但是并不需要关心这2个位置的状态的求解过程。而且，由于仅仅允许向右或者向下运动，因此前面阶段的状态确定了之后，不会被后面的状态所改变，因此满足无后效性的特征。

定义状态为：min_dist(i, j)，表示从 (0, 0) 出发到 (i, j)的最短距离。那么到达(i, j)的最短路径必然经过(i-1, j)或 (i, j-1)，因此，到达(i, j)的最短路径必然包含到达这2个位置的最短路径之一。因此满足 最优子结构 的特征。

综上所述，min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))。

求解:

// 回溯算法
private int min = Integer.MAX_VALUE;
public void minDist(int i, int j, int dist, int[][] w, int n) {
    // terminator
    if (i == n && j == n) {
        if (dist < min) min = dist;
        return;
    }
    // drill down
    if (i < n) {
        minDist(i + 1, j, dist + w[i][j], w, n);
    }
    if (j < n) {
        minDist(i, j + 1, dist + w[i][j], w, n);
    }
}

// 递归+备忘录（缓存）减少重复计算
private int[][] mem = new int[n][n];
public int minDist(int i, int j, int[][] w) {
    if (i == 0 && j == 0) {
        return w[0][0];
    }
    if (mem[i][j] > 0) {
        return mem[i][j];
    }
    int minLeft = Integer.MAX_VALUE;
    if (j-1>=0 ) {
        minLeft = minDist(i, j-1);
    }
    int minUp = Integer.MAX_VALUE;
    if (i-1>= 0) {
        minUp = minDist(i-1, j);
    }
    int curMinDist = w[i][j] + Math.min(minLeft, minUp);
    mem[i][j] = curMinDist;
    return curMinDist;
}

// 动态规划
public int minDist(int[][] w, int n) {
    int[][] states = new int[n][n];
    int sum = 0;
    for (int j = 0; j < n; j++) {
        sum += w[0][j];
        states[0][j] = sum;
    }
    sum = 0;
    for (int i = 0; i < n; i++) {
        sum += w[i][0];
        states[i][0] = sum;
    }
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < n; j++) {
            states[i][j] = w[i][j] + Math.min(states[i][j-1], states[i-1][j]);
        }
    }
    return states[n-1][n-1];
}

一维动态规划：Fibnacci

# 递归：自顶向下 O(2^N)
int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2); // 改进：return n <= 1 ? n : fib(n-1) + fib(n-2);
}

# 递归 + 备忘录 （记忆化搜索） O(N)
int fib(int n, int[] memo) {
    if (n <= 1) {
        return n;
    }
    if (memo[n] == 0) {
        memo[n] = fib(n-1, memo) + fib(n-2, memo);
    }
    return memo[n];
}

# 动态规划：自底向上 O(N)
int fib(int n) {
    int[] dp = new int[n];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}
   
# 一维的Equation: f(n) = f(n-1) + f(n-2)

二维动态规划：Count the paths

// 递归
int countPaths(boolean[][] grid, int row, int col) {
    if (!validSqure(grid, row, col)) return 0;
    if (isAtEnd(grid, row, col)) return 1;
    return countPaths(grid, row + 1, col) + countPaths(grid, row, col+1);
}

opt[i, j] = opt[i+1, j] + opt[i, j+1];
if a[i, j] == '空地'：
    opt[i, j] = opt[i+1, j] + opt[i, j+1];
else: 
	opt[i, j] = 0;

对比：
# 一维的Equation: f(n) = f(n-1) + f(n-2)
    
# 二维的Equation: opt[i, j] = opt[i+1, j] + opt[i, j+1];

总结代码库（示例）

Valid anagram

# 思路：手动模拟hashtable，将字符串”a-z“的ASCII码作key，计数求差异    
   def  isAnagram(self, s: str, t: str) -> bool:
        arr1, arr2 = [0]*26, [0]*26
        for i in s:
            arr1[ord(i) - ord('a')] += 1
        for i in t:
            arr2[ord(i) - ord('a')] += 1
        return arr1 == arr2
# 思路：map计数，对比计数差异
    def isAnagram(self, s: str, t: str) -> bool:
        dict1, dict2 = {}, {}
        for item in s:
            dict1[item] = dict1.get(item,0) + 1
        for item in t:
            dict2[item] = dict2.get(item,0) + 1
        return dict1 == dict2
# 思路：数组排序后比较差异
    def isAnagram(self, s: str, t: str) -> bool:
        return sorted(s) == sorted(t)

public class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()) return false;
        int [] a = new int [26];
        for(Character c : s.toCharArray()) a[c - 'a']++;
        for(Character c : t.toCharArray()) {
            if(a[c -'a'] == 0) return false;
            a[c - 'a']--;
        }
        return true;
    }
    
    public boolean isAnagram(String s1, String s2) {
        int[] freq = new int[256];
        for(int i = 0; i < s1.length(); i++) freq[s1.charAt(i)]++;
        for(int i = 0; i < s2.length(); i++) if(--freq[s2.charAt(i)] < 0) return false;
        return s1.length() == s2.length();
    }
    
    
	public boolean isAnagram(String s, String t) {
    	char[] sChar = s.toCharArray();
    	char[] tChar = t.toCharArray();
    	Arrays.sort(sChar);
    	Arrays.sort(tChar);
    	return Arrays.equals(sChar, tChar);   
	}
}

Group Anagrams

def groupAnagrams(self, strs):
    d = {}
    for w in sorted(strs):
        key = tuple(sorted(w))
        d[key] = d.get(key, []) + [w]
    return d.values()

def groupAnagrams(self, strs):
    dic = {}
    for item in sorted(strs):
        sortedItem = ''.join(sorted(item))
        dic[sortedItem] = dic.get(sortedItem, []) + [item]
    return dic.values()

public List<List<String>> groupAnagrams(String[] strs) {
	List<List<String>> res = new ArrayList<>();
    HashMap<String, List<String>> map = new HashMap<>();
    
    Arrays.sort(strs);
    for (int i = 0; i < strs.length; i++) {
    	String temp = strs[i];
    	char[] ch = temp.toCharArray();
    	Arrays.sort(ch);
    	if (map.containsKey(String.valueOf(ch))) {
    		map.get(String.valueOf(ch)).add(strs[i]);
    	} else {
    		List<String> each = new ArrayList<>();
    		each.add(strs[i]);
    		map.put(String.valueOf(ch), each);
    	}
    }
    for (List<String> item: map.values()) {
    	res.add(item);
    }
    return res;
}

Two sum

def twoSum(self, nums, target):
    d = dict()
    for index,num in enumerate(nums):
        if d.get(num) == None:
            d[target - num] = index
        else:
            return [d.get(num), index

public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> tracker = new HashMap<Integer, Integer>();
    int len = nums.length;
    for (int i = 0; i < len; i++){
        if (tracker.containsKey(nums[i])){
            int left = tracker.get(nums[i]);
            return new int[]{left+1, i+1};
        } else {
            tracker.put(target - nums[i], i);
        }
    }
    return new int[2];
}

刷题开始

Array

283. move zeros

方法1：将所有的非零元素都填充到数组前侧，然后将0填充到数组后侧 #双指针法

class Solution {
    public void moveZeroes(int[] nums) {
        int lastNotZeroIndex = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] != 0) {
                nums[lastNotZeroIndex++] = nums[i];
            }
        }
        
        for (int i = lastNotZeroIndex; i < nums.length; ++i) {
            nums[i] = 0;
        }
    }
}

方法2：一维数组的坐标转换 i, j #双指针法

用 j 记录上一个可能为0的值的索引，用 i 遍历数组，当遇到不为0的值的时候，将该元素 num[i] 与 nums[j] 交换，保证 j 前面的元素均为非0值。

class Solution {
    public void moveZeroes(int[] nums) {
        int lastZeroIndex = 0;
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] != 0) {
                int temp = nums[i];
                nums[i] = nums[lastZeroIndex];
                nums[lastZeroIndex] = temp;
                lastZeroIndex++;
            }
        }
    }
}

11. container with most water

思路：

1.枚举： left bar x, right bar y, (y - x) * min_height O(n^2) #枚举

// 遍历数组的一个常见的办法:遍历左右边界，且左右边界不能重复
class Solution {
    public int maxArea(int[] a) {
        int max = 0
        for (int i = 0; < a.length - 1; ++i) {
            for (int j = i + 1; j < a.length; ++j) {
                int area = (j - i) * Math.min(a[i], a[j]);
                max = Math.max(max, area); 
            }
        }
        return max;
    }
}

2.左右夹逼/双指针法：左右边界 i, j, 向中间收敛 #双指针法：左右夹中间，中间到两边

// 遍历数组的一个常见的办法:遍历左右边界，且左右边界不能重复
class Solution {
    public int maxArea(int[] a) {
        int max = 0
        for (int i = 0, j = a.length - 1; i < j; ) {
            int minHeight = a[i] < a[j] ? a[i++] : a[j--];
            max = Math.max(max, (j - i + 1) * minHeight); 
        }
        return max;
    }
}

70. climbing stairs

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int f1 = 1;
        int f2 = 2;
        int f3 = 3;
        for (int i = 3; i <= n; i++) {
            f3 = f1 + f2;
            f1 = f2;
            f2 = f1;
        }
        return f3;
    }
}

1. 2sum

方法1：暴力解法 O(n^2)

// 遍历数组的一个常见的办法:遍历左右边界，且左右边界不能重复
class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length - 1; ++i) {
            for (int j = i + 1; j < nums.length; ++j) {
                if (nums[i] + nums[j] == target) {
					return new int[] {i, j};
                }
            }
        }
        return new int[2];
    }
}

方法2：两遍哈希表

思想：空间换时间

保持数组中的每个元素与其索引相互对应的最好方式是什么？哈希表。

哈希表查找的时间复杂度为 O(1)。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            map.put(target - nums[i], i);
        }
        for (int i = 0; i < nums.length; ++i) {
            if (map.containsKey(nums[i]) && i != map.get(nums[i])) {
                return new int[] {i, map.get(nums[i])};
            }
        }
        return new int[2];
    } 
}

方法3：一遍哈希表

由于在遍历数组的过程中，可以回过头来查找哈希表中是否存储了目标元素的值，因此，没有必要遍历完整的数组将目标元素的值存储到哈希表中，可以边遍历边存储。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            int component = target - nums[i];
            if (map.containsKey(component)) {
                return new int[] {map.get(component), i};
            }
            map.put(nums[i], i);
        }
        return new int[2];
    } 
}

15. 3sum

思路：转化 a + b = -c

1.暴力解法：三重循环

2.HashMap

3.左右夹逼/双指针法，这种办法有时候需要排序。

Linked List

141. linked-list-cycle

1.暴力解法：遍历链表，hash/set

2.快慢指针 #快慢指针法

Stack

20. valid parentheses

为啥这个题目可以用栈解决？具有最近相关性

1.暴力解法：不断replace匹配的括号 -> "" O(n^2)

a. (){}[]

b.((({[]})))

2.Stack

155. min Stack

两个队列实现栈

两个栈实现队列

84. largest rectangle in histogram

思考一下这个题目和 container with most water 有何差别？

差别在于这个题目的高度是指所有柱子中最低的高度，而 container with most water 则是左右两边最小的高度。

1.暴力解法 O(n^3)
for i -> 0, n-2
    for j -> i+1, n-1
        (i, j) -> 最小高度， area
        update max-area
2.暴力加速
for i -> 0, n-1
    找到 left bound, right bound   // 固定中间一个高度，找到左右两边比他小的最小值
    area = height[i] * (right - left)
    update max-area
3.Stack：有序栈(单调栈)找左右边界 #单调栈

维护一个从小到大的有序栈

那么左边界left bound在栈里，而右边界则是比栈顶元素小的新元素

如果新元素的值大于栈顶元素，说明栈顶元素的右边界没有找到。

构造这个有序栈的过程，其实就是不断找到栈顶元素的右边界的过程（左边界在栈里）。

Queue

239. sliding window maximum

1.暴力 O(n*k)

2.deque O(n) 滑动窗口 -> 队列 #单调队列

Hash Table

242. valid anagram

#切题四件套

clarification

-确定异位词是什么意思？

-确定大小写是否敏感？

方法1：

暴力 sort -> sorted_str 是否相等？ O(NlogN)

方法2：哈希表

统计每个字符出现的频次

（1）第一个string，碰到字母加1，第二个string，碰到同样的字母减1，最后看map是否为空

（2）int[256] 的数组，ascii -> index

49.group anagrams

Tree

94. binary tree inorder traversal

98. validate binary search tree

中序遍历是递增的。

Recursion

70. climbing stairs

找 最近重复性

1: 1

2: 2

3: f(1) + f(2) 1的总的走法，跨2步走上3 + 2的总的走法，跨1步走上3 mutual exclusive, complete exhaustive

4: f(2) + f(3)

...

n: f(n) = f(n-1) + f(n-2) Fibonacci

class Solution {
    public int climbStairs(int n) {
        if(n <= 2) return n;
        return climbStairs(n-1) + climbStairs(n-2);
    }
}

22. generate parenthess *

// 递归模板
class Solution {
    public void generateParenthesis(int n) {
        generate(0, 2 * n, "");
    }
    
    private void generate(int level, int max, String s) {
        // terminator
        if (level >= max) {
            System.out.println(s);
            return; 
        }
        // process current logic
        String s1 = s + "(";
        String s2 = s + ")";
        // drill down
        generate(level + 1, max, s1);
        generate(level + 1, max, s2);
        // reverse states
    }
}

// 检查括号合法性
// left 随时加，只要不超标 n
// right 左括号个数 > 右括号个数
class Solution {
    List<String> result;
    
    public List<String> generateParenthesis(int n) {
        result = new ArrayList<>();
        generate(0, 0, n, "");
    }
    
    private void generate(int left, int right, int n, String s) {
        // terminator
        if (left == n && right == n) {
            result.add(s);
            return; 
        }
        // process current logic
        String s1 = s + "(";
        String s2 = s + ")";
        // drill down
        if (left < n) {
            generate(left + 1, right, n, s1);
        }
        if (left > right) {
            generate(left, right + 1, n, s2);
        }
        generate(level + 1, max, s1);
        generate(level + 1, max, s2);
        // reverse states
    }
}
// 本质就是DFS

Divide and conquer

50. Pow(x, n)

1.暴力 O(n)

result = 1;
for (int i = 0; i < n; i++) {
    result *= x;
}

2.分治 O(logn)

template: 1. terminator 2. process (divide your big problem) 3. drill down (conquer your subproblems ) 4. merge sub result 5. reverse states.

pow(x, n):
	subproblem: subresult = pow(x, n/2);
	mege:
		if (n % 2 == 1) {
        	result = subresult * subresult * x;
        } else {
            result = subresult * subresult;
        }

78. subsets *

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> ans = new ArrayList<>();
    if (nums == null) return ans;
    dfs(ans, nums, new ArrayList<Integer>(), 0);
    return ans;
}

private void dfs(List<List<Integer>> ans, int[] nums, List<Integer> list, int index) {
    // terminator
    if (index == nums.length) {
        ans.add(new ArrayList<Integer>(list));
        return;
    }
    
    // not pick the number at this index
    dfs(ans, nums, list, index + 1);
    
    // pick the number at this index
    list.add(num[index]);
    dfs(ans, nums, list, index + 1);
    
    // reverse the current state
    list.remove(list.size() - 1);
}

// or
private void dfs(List<List<Integer>> ans, int[] nums, List<Integer> list, int index) {
    // terminator
    if (index == nums.length) {
        ans.add(new ArrayList<Integer>(list));
        return;
    }
    
    // not pick the number at this index
    dfs(ans, nums, list.clone, index + 1);
    
    // pick the number at this index
    list.add(num[index]);
    dfs(ans, nums, list.clone, index + 1);
    
    // reverse the current state
}

class Solution(object):
    def subsets(self, nums):
        result =[[]]
        for num in nums:
            newsets = []
            for subset in result:
                new_subset = subset + [num]
                newsets.append(new_subset)
           	result.extend(newsets) 
       	return result

169. majority element

17. letter combinations of a phone number *

public List<String> letterCombination(String digits) {
    if (digits == null || digits.length() == 0) {
        return new ArrayList();
    }
    Map<Character, String> map = new HashMap<>();
    map.put('2', "abc");
    map.put('3', "def");
 	map.put('4', "ghi");
    map.put('5', "jkl");
    map.put('6', "mno");
    map.put('7', "pqrs");
    map.put('8', "tuv");
    map.put('9', "wxyz");   
    List<String> res = new ArrayList<>();
    search("", digits, 0, res, map);
    return res;
}

private void search(String s, 
                    String digits, 
                    int i, // level
                   List<String> res,
                   Map<Character, String> map) {
	// terminator
    if (i == digits.length) {
        res.add(s);
        return;
    }
    // process
    String letters = map.get(digits.charAt(i));
    for (int j = 0;  j < letters.length(); j++) {
        // drill down
        search(s+letters.charAt(j), digits, i+1, res, map);
    }
}

51. n queens

def sovleNQueen(self, n):
    if n < 1: return []
    self.result = []
    
    # 之前的皇后所攻击的位置(列，pie, na)
    self.cols = set();
    self.pie = set();
    self.na = set();
    
    self.DFS(n, 0, [])
    return self._generate_result(n)

def DFS(self, n, row, cur_state):
    # ternimator
    if row >= n:
        self.result.append(cur_state)
        return 
    
    # current level! Do it!
    for col in range(n):  # 遍历列 column
        if col in self.cols or row + col in self.pie or row - col in self.na:
            # go die
            continue
   		
        # update the flags
        self.cols.add(col)
        self.pie.add(row+col)
        self.na.add(row-col)
        
        self.DFS(n, row + 1, cur_state + [col])
        
        # reverse state
        self.cols.remove(col)
        self.pie.remove(row+col)
        self.na.remove(row-col)
       
def _generate_result(self, n):
    board = []
    for res in self.result:
        for i in res:
            board.append("." * i + "Q"  + "." * (n - i - 1))
    return [board[i: i + n] for i in range(0, len(board), n)]

Binary Search

69. sqrtx

class Solution {
    public int mySqrt(int x) {
        if (x == 0 || x == 1) {
            return x;
        }
        long left = 1;
        long right = x / 2; // (x/2)^2 >= x
        while (left < right) {
            long mid = left + (right - left + 1) / 2;
            if (mid * mid > x) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return (int)left;
    }
}

扩展阅读：牛顿迭代法

33. search in rotated sorted array

1.暴力遍历 O(N)

2.还原O(log N) -> 升序 -> 二分查找O(log N)

3.二分查找O(log N)

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[0] <= nums[mid] && (target > nums[mid] || target < nums[0])) {
                left = mid + 1;
            } else if (target > nums[mid] && target < nums[0]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left == right && nums[left] == target ? left : -1;
    }
}

BFS & DFS

102. binary tree level order traversal

1.BFS

2.DFS

22. generate parenthess *

DFS

200. number of islands

floodfill

class Solution {
    int[] dx = new int[]{-1, 1, 0, 0};
    int[] dy = new int[]{0, 0, -1, 1};
    char[][] g;
    
    public int numIslands(char[][] grid) {
    	int islands = 0;
        g = grid;
        for (int i = 0;  i < g.length; i++) {
            for (int j = 0; j < g[i].length; j++) {
                if (g[i][j] == '0') continue;
                islands += sink(i, j);
            }
        }
        return islands;
    }
    
    private int sink(int i, int j) {
        if (g[i][j] == '0') {
            return 0;
        }
        
        g[i][j] = '0';
        
        for (int k = 0; k < dx.length; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0 && x < g.length && y >= 0 && y < g[x].length) {
                if (g[x][y] == '0') continue;
                sink(x, y);
            }
        }
        
        return 1;
    }
}

79. word search 与212一起看

Greedy

从后往前

从前往后

从某个点切入往某一边

class Solution {
    public boolean canJump(int[] nums) {
        if (nums == null) {
            return false;
        }
        
        int endReachable = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] + i >= endReachable) {
                endReachable = i;
            }
        }
        
        return endReachable == 0;
    }
}

Dynamic Programming

70. climbing stairs

找 最近重复性

1: 1

2: 2

3: f(1) + f(2) 1的总的走法，跨2步走上3 + 2的总的走法，跨1步走上3 mutual exclusive, complete exhaustive

4: f(2) + f(3)

...

n: f(n) = f(n-1) + f(n-2) Fibonacci

class Solution {
    public int climbStairs(int n) {
        if(n <= 2) return n;
        return climbStairs(n-1) + climbStairs(n-2);
    }
}

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int f1 = 1;
        int f2 = 2;
        int f3 = 3;
        for (int i = 3; i <= n; i++) {
            f3 = f1 + f2;
            f1 = f2;
            f2 = f1;
        }
        return f3;
    }
}

class Solution {
    public int climbStairs(int n) {
        if (n <= 2) return n;
        int[] dp = new int[n];
        
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2; i < n; i++) {
        	dp[i] = dp[i-1] + dp[i-2];
    	}
    	return dp[n-1];
	}
}

进阶：

（1）可以走1, 2，3步，如何解决？easy -> f(n) = f(n-1) + f(n-2) + f(n-3)

（2）给定一个数组[x1, x2, ..., xn ] 表示可以走 x1，x2, ..., xn步，如何解决？

（2）相邻2步的步伐不同，如何解决？ medium

小结：一维动态规划：Fibnacci

# 递归：自顶向下 O(2^N)
int fib(int n) {
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2); // 改进：return n <= 1 ? n : fib(n-1) + fib(n-2);
}

# 递归 + 备忘录 （记忆化搜索） O(N)
int fib(int n, int[] memo) {
    if (n <= 1) {
        return n;
    }
    if (memo[n] == 0) {
        memo[n] = fib(n-1, memo) + fib(n-2, memo);
    }
    return memo[n];
}

# 动态规划：自底向上 O(N)
int fib(int n) {
    int[] dp = new int[n+1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}
   
# 一维的Equation: f(n) = f(n-1) + f(n-2)

62. unique paths

opt[i, j] = opt[i+1, j] + opt[i, j+1];
if a[i, j] == '空地'：
    opt[i, j] = opt[i+1, j] + opt[i, j+1];
else: 
	opt[i, j] = 0;

int countPaths(boolean[][] grid, int row, int col) {
    if (!validSqure(grid, row, col)) return 0;
    if (isAtEnd(grid, row, col)) return 1;
    return countPaths(grid, row + 1, col) + countPaths(grid, row, col+1);
} 

class Solution {
    // 二维DP数组
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int j = 0; j < n; j++) {
            dp[0][j] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
    
    // 一维DP数组：将每一行都压缩在固定的一行更新，更新m次
    public int uniquePaths(int m, int n) {
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j-1];
            }
        }
        return dp[n-1];
    }
}

65. unique paths ii

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int n = obstacleGrid[0].length;
        int[] dp = new int[n];
        dp[0] = 1;
        for (int[] row : obstacleGrid) {  // 注意这种写法
            for (int j = 0; j < n; j++) {  // 这里j一定要从0开始，因为row[0]可能是障碍物
                if (row[j] == 1) {
                    dp[j] = 0;
                } else if (j > 0){
                    dp[j] += dp[j-1];
                }
            }
        }
        return dp[n-1];
    }
}

64. minimum path sum

// 暴力解法
class Solution {
    public int minPathSum(int[][] grid) {
        return minPathSum(0, 0, grid);
    }

    private int minPathSum(int i, int j, int[][] grid) {
        if (i == grid.length || j == grid[0].length) return Integer.MAX_VALUE;
        if (i == grid.length - 1 && j == grid[0].length - 1) {
            return grid[i][j];
        }
        return grid[i][j] + Math.min(minPathSum(i+1, j, grid), minPathSum(i, j+1, grid));
    }
}

// 动态规划
class Solution {
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length <= 0 || grid[0].length <= 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[][] states = new int[m][n];
        int sum = 0;
        for (int j = 0; j < n; j++) {
            sum += grid[0][j];
            states[0][j] = sum;
        }
        sum = 0;
        for (int i = 0;  i < m; i++) {
            sum += grid[i][0];
            states[i][0] = sum;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                states[i][j] = grid[i][j] + Math.min(states[i][j-1], states[i-1][j]);
            }
        }
        return states[m-1][n-1];
    }
}

小结：二维动态规划：Count the paths

// 递归
int countPaths(boolean[][] grid, int row, int col) {
    if (!validSqure(grid, row, col)) return 0;
    if (isAtEnd(grid, row, col)) return 1;
    return countPaths(grid, row + 1, col) + countPaths(grid, row, col+1);
}

opt[i, j] = opt[i+1, j] + opt[i, j+1];
if a[i, j] == '空地'：
    opt[i, j] = opt[i+1, j] + opt[i, j+1];
else: 
	opt[i, j] = 0;

对比：
# 一维的Equation: f(n) = f(n-1) + f(n-2)
    
# 二维的Equation: opt[i, j] = opt[i+1, j] + opt[i, j+1];

120. triangle (一个不错的分析过程)

1、brute-force 递归， n层： left or right: O(2^N)

2、DP

a. 重复性 problem(i, j) = min(sub(i+1, j) , sub(i+1, j+1)) + a[i][j]

b. 状态数组 f(i, j)

c. DP方程 f(i, j) = min(f(i+1, j) , f(i+1, j+1)) + a[i][j]

class Solution:
    def minimumTotal(self, triangle):
        """
        :type triangle: List[List[int]]
        :rtype: int
        """
        dp = triangle
        for i in range(len(triangle) - 2, -1, -1):
            for j in range(len(triangle[i])):
                dp[i][j] += min(dp[i+1][j], dp[i+1][j+1])
        print(triangle[0][0])
        return dp[0][0]

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[] dp = new int[triangle.size() + 1];
        for (int i = triangle.size() - 1; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }
}

class Solution {
    int maxRow;
    public int minimumTotal(List<List<Integer>> triangle) {
		maxRow = triange.size();
        return helper(0, 0, triangle);
    }
    
    private int helper(int row, int col, List<List<Integer>> triangle) {
        if (row == maxRow-1) {
            return triangle.get(row).get(col);
        }
        int left = helper(row+1, col, triangle);
        int right = helper(row+1, col+1, triangle);
        return Math.min(left, right) + triangle.get(row).get(col);
    }
}

class Solution {
    int maxRow;
    Integer[][] memo;
    public int minimumTotal(List<List<Integer>> triangle) {
		maxRow = triange.size();
        memo = new Integer[row][row];
        return helper(0, 0, triangle);
    }
    
    private int helper(int row, int col, List<List<Integer>> triangle) {
        if (memo[row][col] != null) {
            return memo[row][col];
        }
        if (row == maxRow-1) {
            return memo[row][col] = triangle.get(row).get(col);
        }
        int left = helper(row+1, col, triangle);
        int right = helper(row+1, col+1, triangle);
        return memo[row][col] = Math.min(left, right) + triangle.get(row).get(col);
    }
}

53. maximum sum subarray

1、暴力 O(N^2)

2、DP

a. 重复性 max_sum(i) = Max(max_sum(i-1) , 0) + a[i] max_sum(i) : 表示以第i个元素结尾（包含）的连续子数组最大和

b. 状态数组 f(i)

c. DP方程 f(i) = max(f(i-1), 0) + a[i]

class Solution(object):
    def maxSubArray(self, nums):
        """
        1. dp[i] = max(nums[i], nums[i] + dp[i-1])
        2. 最大子序列和 = 当前元素最大（之前元素和为负） 或者 包含之前+当前之后最大
        """
        dp = nums
        for i in range(1, len(nums)):
            dp[i] = max(0, dp[i-1]) + nums[i]
        return max(dp)

152. maximum product subarray

322. coin change (推荐题解)

1、暴力递归

2、BFS

3、DP

a. 重复性

b. DP array

c. DP equation: f(n) = min{f(n-k), for k in [1, 2, 5]} + 1

变形：若问共有多少种组合方式?

分析：这个问题就类似于爬楼梯问题，爬楼梯每次可以爬1阶，每次可以爬2阶，每次也可以爬5阶，问爬到11阶有多少种方式？（不同之处在于硬币[1,2,1]和[1,1,2]是一种情况，而爬楼梯则不是）

public class Solution {
    public int coinChange(int[] coins, int amount) {
        return coinChange(0, coins, amount);
    }
    
    private int coinChange(int index, int[] coins, int amount) {
        if (amount == 0) {
            return 0;
        }
        if (index < coins.length && amount > 0) {
            int maxVal = amount / coins[index];
            int minCost = Integer.MAX_VALUE;
            for (int x = 0; x <= maxVal; x++) {
                if (amount >= x * coins[index]) {
                    int res = coinChange(index+1, coins, amount - x * coins[index]);
                    if (res != -1) {
                        minCost = Math.min(minCost, res + x);
                    }
                }
            }
            return minCost == Integer.MAX_VALUE ? -1 : minCost;
        }
        return -1;
    }
}

public class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount <=0) return 0;
        return coinChange(coins, amount, new int[amount]);
    }
    
    private int coinChange(int[] coins, int remain, int[] count) {
        if (remain < 0) {
            return -1;
        }
        if (remain == 0) {
            return 0;
        }
        if (count[remain-1] != 0) {
            return count[remain-1];
        }
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            int res = coinChange(coins, remain - coin, count);
            if (res >= 0 && res < min) {
                min = res + 1;
            }
        }
        count[remain - 1] = min == Integer.MAX_VALUE ? -1 : min;
        return count[remain - 1];
    }
}

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                	dp[i] = Math.min(dp[i], dp[i-coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

1143. longest common subsequence

# 经验

1.对于2个字符串的比较，很多时候，我们会从字符串的尾部向前看。

2.对于2个字符串的变化问题，很多时候会表示成一个二维数组，行和列的元素分别是2个字符串的字符

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        if (text1 == null || text2 == null) {
            return 0;
        }
        int n = text1.length();
        int m = text2.length();
        int[][] dp = new int[n+1][m+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (text1.charAt(i-1) == text2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[n][m];
    }
    
    public int longestCommonSubsequence(String text1, String text2) {
        if (text1 == null || text2 == null) {
            return 0;
        }
        int n = text1.length();
        int m = text2.length();
        int[] dp = new int[m+1];
        for (int i = 1; i <= n; i++) {
            int temp = 0;  
            for (int j = 1; j <= m; j++) {
                int prev = temp;
                temp = dp[j];
                if (text1.charAt(i-1) == text2.charAt(j-1)) {
                    dp[j] = prev + 1;
                } else {
                    dp[j] = Math.max(dp[j], dp[j-1]) ;
                }
            }
        }
        return dp[m];
    }
}

72. edit distance (莱文斯坦距离)

1、BFS, two-ended BFS

2、DP

dp[i][j] // word1.substr(0, i) 与 word2.substr(0, j)的编辑距离

(1) if w1[i] == w2[j]

w1: ............x (i)

w2: .............x (j)

edit_dist(i, j) = edit_dist(i-1, j-1)

(2) if w1[i] != w2[j]

w1: ............x (i)

w2: .............y (j)

edit_dist(i, j) =

min(

edit_dist(i-1, j-1) + 1 // x -> y (w1) or y -> x (w2)

edit_dist(i - 1, j) + 1 // 删除 x

edit_dist(i, j - 1) + 1 // 删除 y

)

class Solution {
    // 单独处理空字符串的dp
    public int minDistance(String word1, String word2) {
        if (word1 == null || word2 == null) {
            return 0;
        }
        int n = word1.length();
        int m = word2.length();
        if (n == 0) {
            return m;
        } else if (m == 0) {
            return n;
        }
        int[][] dp = new int[n][m];
        for (int j = 0; j < m; j++) {
            if (word1.charAt(0) == word2.charAt(j)) dp[0][j] = j;
            else if (j != 0) dp[0][j] = dp[0][j-1] + 1;
            else dp[0][j] = 1;
        }
        for (int i = 0; i < n; i++) {
            if (word1.charAt(i) == word2.charAt(0)) dp[i][0] = i;
            else if (i != 0) dp[i][0] = dp[i-1][0] + 1;
            else dp[i][0] = 1;
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (word1.charAt(i) == word2.charAt(j)) {
                    dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1]);
                } else {
                    dp[i][j] = min( dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
                }
            }
        }
        return dp[n-1][m-1];
    }
    // 统一处理空字符串的dp
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();
        int[][] dp = new int[n+1][m+1];
        for (int j = 0; j <= m; j++) {
            dp[0][j] = j;
        }
        for (int i = 0; i <= n; i++) {
            dp[i][0] = i;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (word1.charAt(i-1) == word2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1];
                } else {
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
                }
            }
        }
        return dp[n][m];
    }

    private int min(int x, int y, int z) {
        return Math.min(x, Math.min(y, z));
    }   
}

198. house robber

a[i] : 0...i 能偷到的 max value : a[n-1]

a[i][0,1]: 0：表示第 i 个房子不偷，1：偷

a[i][0] = max(a[i-1][0], a[i-1][1])

a[i][1] = a[i-1][0] + nums[i]

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int n = nums.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = nums[0];

        for(int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
            dp[i][1] = dp[i-1][0] + nums[i];
        }

        return Math.max(dp[n-1][0], dp[n-1][1]);
    }
}

a[i] : 0...i ，且包含了 nums[i] 必偷的情形，max value: max(a)

a[i] = max(a[i-1], a[i-2] + nums[i])

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) return nums[0];

        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        int res = Math.max(dp[0], dp[1]);

        for(int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
            res = Math.max(res, dp[i]);
        }

        return res;
    }
}

股票问题分析

Trie

208. implement trie prefix tree

class Trie {

    private TrieNode root;

    /** Initialize your data structure here. */
    public Trie() {
        this.root = new TrieNode('/');
    }
    
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode p = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (p.children[index] == null) {
                TrieNode newNode = new TrieNode(word.charAt(i));
                p.children[index] = newNode;
            }
            p = p.children[index];
        }
        p.isEndingChar = true;
    }
    
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        TrieNode p = root;
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (p.children[index] == null) {
                return false;
            }
            p = p.children[index];
        }
        if (p.isEndingChar) return true;
        else return false;
    }
    
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        TrieNode p = root;
        for (int i = 0; i < prefix.length(); i++) {
            int index = prefix.charAt(i) - 'a';
            if (p.children[index] == null) {
                return false;
            }
            p = p.children[index];
        }
        return true;
    }

    class TrieNode {
        public char data;
        public TrieNode[] children = new TrieNode[26];
	    public boolean isEndingChar = false;
    
        public TrieNode(char data) {
            this.data = data;
        }
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

212. word search ii

1、words 遍历 --> board 中 search

2、Trie

a. all words --> Trie

b. board --> DFS

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
END_OF_WORD = "#"

class Solution(object):
    def findWords(self, board, words):
        """
        :type board: List[List[str]]
        :type words: List[str]
        :rtype: List[str]
        """
        if not board or not board[0]: return []
        if not words: return []
        
        self.result = set()
        
        # 根据words构建Trie
        root = {}
        for word in words:
            node = root
            for char in word:
                node = node.setdefault(char, {})
            node[END_OF_WORD] = END_OF_WORD
        
        self.m, self.n = len(board), len(board[0])
        for i in range(self.m):
            for j in range(self.n):
                if board[i][j] in root: # 剪枝
                    self._dfs(board, i, j, "", root)
        
        return list(self.result)
    
    def _dfs(self, board, i, j, cur_word, cur_dict):
        # terminator
        cur_word += board[i][j]
        cur_dict = cur_dict[board[i][j]]
        if END_OF_WORD in cur_dict:
            self.result.add(cur_word)
        
        # process current logic
        tmp, board[i][j] = board[i][j], '@'  # @表示 board[i][j]用过了，就不再用了
       
    	# drill down
    	for k in range(4):
            x, y = i + dx[k], j + dy[k]
            if 0 <= x < self.m and 0 <= y < self.n and board[x][y] != '@' and board[x][y] in cur_dict:
                self._dfs(board, x, y, cur_word, cur_dict)
        
        # 恢复 board
        board[i][j] = tmp

Sort

242. valid anagram

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        char[] sArray = s.toCharArray();
        char[] tArray = t.toCharArray();
        Arrays.sort(sArray);
        Arrays.sort(tArray);
        return Arrays.equals(sArray, tArray);
    }
}

Files

刷题笔记.md

Latest commit

History

刷题笔记.md

File metadata and controls

刷题笔记

如何有效学习数据结构与算法？

如何精通一个领域？

如何精通数据结构与算法呢？

工具

代码模板

递归代码模板 Recursion

分治代码模板 Divide and Conquer

查找-搜索-遍历 模板

二分查找（Binary Search）

深度优先搜索（DFS, Depth First Search)

广度优先遍历（BFS, Breadth First Search）

A*

归并排序

Trie

定义

本质

实现

API

代码

性能

时间复杂度

空间复杂度

Trie 树的应用

UnionFind

八皇后问题

Dynamic Programming

动态规划基本理论

一个模型：多阶段决策最优解模型

三个特征

最优子结构

无后效性

重复子问题

复杂度

实例

分析：

求解:

一维动态规划：Fibnacci

二维动态规划：Count the paths

总结代码库（示例）

刷题开始

Array

283. move zeros

11. container with most water

70. climbing stairs

1. 2sum

15. 3sum

Linked List

141. linked-list-cycle

Stack

20. valid parentheses

155. min Stack

84. largest rectangle in histogram

Queue

239. sliding window maximum

Hash Table

Tree

Recursion

Divide and conquer

78. subsets *

17. letter combinations of a phone number *

Binary Search

BFS & DFS

79. word search 与212一起看

Greedy

Dynamic Programming

小结：一维动态规划：Fibnacci

小结：二维动态规划：Count the paths

120. triangle (一个不错的分析过程)

322. coin change (推荐题解)

股票问题 分析

Trie

Sort

位运算

查找-搜索-遍历模板

股票问题分析