Zexian Li

算法核心思想总结

2021-03-05 · 37 min read
algorithm

迫于打工，开刷算法！
本博客旨在归纳算法题的核心思想并总结对应的模板，从而指导具体的实际问题求解🎺同时感谢labuladong的算法讲解Gitbook访问相关文章。

0. 数据读取

简单记录一下ACM模式下Python3的数据读取方法。
举个例子，输入n组数据来实现两数之和，输入如下(第一行代表数据组数n，后n行为数据)：

3
1 2
3 4
5 6

数据读取方式如下，最后将结果以print形式输出：

import sys

n = int(sys.stdin.readline())
for i in range(n):
    line = sys.stdin.readline().strip()
    data = list(map(int, line.split()))
    a, b = data
    print(a + b)

1.动态规划

动态规划问题的一般形式就是求最值，求解动态规划问题的核心是穷举。

动态规划的三要素是重叠子问题、最优子结构、状态转移方程：

  • 动态规划问题存在“重叠子问题”(回想斐波那契数列求解过程复杂度)，故需要“备忘录”或者“DP table”来优化求解过程，避免不必要的计算。
  • 动态规划问题一定具备“最优子结构”(回想获取更高分数时对待每一门科目的态度)，故可以通过拆分成子问题求最值得到原问题的最值。这要求子问题间必须相互独立。
  • 动态规划问题需要列写正确的状态转移方程。

整体来说，(回想斐波那契数列求解过程)，动态规划的一般流程分三步：暴力的递归解法-->带备忘录的递归解法-->迭代的动态规划解法。
其中带备忘录的递归解法是“自顶向下”的，是将问题不断拆分成子问题的过程；“DP table”的递归解法是“自底向上”的。二者本质相同，都是在以空间换时间的思路进行“聪明的穷举”。

就思考流程来说，分为以下几步：找到状态和选择-->明确dp数组/函数的定义-->确定对每个状态可以做出的选择并择优执行-->确定base case。
其中，状态即为原问题和子问题中变化的变量；base case为初始状态和失败/退出条件。

题型归纳

思路借鉴Leetcode上的一篇英文博文。
现将DP主要归纳为以下五个题型：

  1. 达到目标的最大(最小)路径
    题干描述：给出到达目标的最大(最小)花费/路径/数值和。
    解题思路：在当前状态之前的所有路径中选择一个最大(最小)的，将当前值加到该路径中。
    典型例题：322零钱兑换(以最少的硬币数量凑出特定金额)
for (int j = 1; j <= amount; ++j) 
   for (int i = 0; i < coins.size(); ++i) 
       if (coins[i] <= j) 
           dp[j] = min(dp[j], dp[j - coins[i]] + 1);
  1. 达到目标的路径总数
    题干描述：给出到达目标的不同路径总数。
    解题思路：将所有能到达当前状态的路径数目相加。
    routes[i] = routes[i-1] + routes[i-2], ... , + routes[i-k]
    典型例题：62不同路径(左上角的人向右向下移动到右下角的路径数目和)
for (int i = 1; i < m; ++i) 
   for (int j = 1; j < n; ++j) 
       dp[i][j] = dp[i][j-1] + dp[i-1][j];
  1. 判断所有元素的状态
    题干描述：给定数值集合，对所有元素做取/舍（元素的连续取/舍性常被限制）。
    解题思路：对当前元素，若“舍”，则需借鉴上一元素被“取”时的状态值；若“取”，则需借鉴上一元素被“舍”时的值。
    典型例题：121股票问题/打家劫舍
// i - size of values
// j - options/status of certain value
for (int i = 1; i < n; ++i) 
    {
        // j = 0 : sell the stock
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]); 
        // j = 1 : hold the stock
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]); 
    }
  1. 区间合并/元素消去
    题干描述：给定数值集合，不断消去元素以合并整个集合，求过程最高得分。消去某一元素的得分判定既要考虑当前元素数值，也要考虑当前元素左/右侧的元素数值。
    解题思路：对某一区间，遍历区间内的所有元素，返回遍历过程的最优解。
for(int l = 1; l<n; l++) {        // l - length 
   for(int i = 0; i<n-l; i++) {   // i - start index
       int j = i+l;               // j - end index
       for(int k = i; k<j; k++) { // k - current index from i to j
           dp[i][j] = max(dp[i][j], dp[i][k] + result[k] + dp[k+1][j]);
       }
   }
}
return dp[0][n-1]
  1. 字符串DP
    题干描述：给出字符串，返回特定结果。
    解题思路：

当给定两个字符串，以两个指针从头分别遍历两个字符串：

// i - indexing string s1
// j - indexing string s2
for (int i = 1; i <= n; ++i) {
   for (int j = 1; j <= m; ++j) {
       if (s1[i-1] == s2[j-1]) {
           dp[i][j] = /*code*/; // eg dp[i][j] = dp[i-1][j-1] + 1;
       } else {
           dp[i][j] = /*code*/; // eg dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
       }
   }
}

当给定一个字符串，方法如下：

// l - length of sub-string
// i - start index of sub-string
// j - end index of sub-string
for (int l = 1; l < n; ++l) {
   for (int i = 0; i < n-l; ++i) {
       int j = i + l;
       if (s[i] == s[j]) {
           dp[i][j] = /*code*/;
       } else {
           dp[i][j] = /*code*/;
       }
   }
}

注：此类问题常需要给出O(n2n^2)内的解法。

套路总结

  1. 最优子结构并不是动态规划独有的一种性质，能求最值的问题大部分都具有这个性质(例如求二叉树最大值)，只是因为很多问题不具有重叠子问题，故不将其归为动态规划问题；但反过来，最优子结构性质作为动态规划问题的必要条件，一定是求最值的。
  2. 碰到恶心人的最值/子序列题，思路优先往动态规划想，时间复杂度一般为O(n2n^2)。
  3. 找最优子结构的过程，其实就是证明状态转移方程正确性的过程。方程符合最优子结构就可以写暴力解了，写出暴力解就可以看出有没有重叠子问题了，有则优化，无则 OK。
  4. 在优化时，需要判断当前算法是否存在重叠子问题，也就是寻找是否有不同路径可达到同一个问题。
  5. 当初始状态确定而末尾状态有多种的时候，可以考虑倒着DP。（平时也可以尝试）

解题思路

  1. 数学归纳法(递归框架)：假设已知f(1)···f(n-1)的情况，尝试求出f(n)，在此过程中总结规律并写出状态转移方程。如果无法完成这一步，通常是dp定义不恰当，需重新定义dp数组的含义；或者是dp数组存储的信息还不够，不足以推出下一步的答案，需要把dp扩大成二维甚至三维数组。
  2. 状态转移法(穷举框架)：具体到每一个元素，分析其相应可能的状态，再合并所有的元素。伪代码如下：
for 状态1 in 状态1所有取值:
    for 状态2 in 状态2所有取值:
        for ...
            dp[状态1][状态2][...] = 择优(选择1,选择2...)
  1. 两个字符串的动态规划问题：一般都是用两个指针分别指向两个字符串的末尾，再一步步往前退以缩小问题的规模。

Leetcode实战

  1. 198/213/337打家劫舍(劫匪不能抢相邻的两个房子)
    dp[i]表示从第0家到第i家抢劫的总金额。
    对于每一家的选择是抢或不抢：
    dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])。
  2. 983最低票价(一年的第{i}天出行，通行证{j}可保证接下来j天的出行)
    dp[i]表示从第0天到第i天花费的总金额。
    对于非出行日期：
    dp[i] = dp[i + 1]；
    对于出行日期在可能的天数中选一个合适的：
    dp[i] = min{cost(j) + dp[i + j]} 。
  3. 5最长回文子串(返回字符串最长回文子串的字符)
    dp[i, j]表示字符i-j是否构成回文串。
    如果现在的回文串前后字母相同，则将其拓展：
    dp[i - 1, j + 1] = dp[i, j] (if dp[i - 1] == dp[j + 1])。
  4. 121/122/123/188/309/714股票买卖(对一支股票在不同条件下买入卖出获得最大利润)
    套用状态转移法，dp[i][k][0 or 1]表示第i天结束后的利润，从第0天到第i天最多可交易k次，0表示暂时未持有股票，1表示正在持有股票。第一维度取值大于等于0，第二维度取值大于等于1。取还未开始交易时dp利润值为0，不可能发生的情形为INT_MIN。
    今天结束交易后未持有股票：
    dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])；
    今天结束交易后持有股票(此处默认k在买入时加1)：
    dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][1] - prices[i])。
  5. 221最大正方形(找出由0/1构成的矩形中，元素均为1的最大正方形)
    dp[i, j]表示(i, j)为右下角时，所构成正方形的最大边长。
    dp(i, j) = min(dp(i - 1, j), dp(i, j - 1), dp(i - 1, j - 1)) + 1。
  6. 300最长递增子序列的长度(子序列不一定是连续的，子串才是连续的)
    dp[i]表示以nums[i]这个数结尾的最长递增子序列的长度。
    for (j = 0; j < i; j++) {if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);}。
  7. 1143最长公共子序列(返回两个字符串最长公共子序列长度)
    dp[i][j]代表对于str1[1..i]和str2[1..j]，其最长公共子序列的长度。
    if (text1[i-1] == text2[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);。
  8. 877/1140/1406石头游戏(两个绝对理智的人从数组两侧/单侧拿n堆石头，分高胜)
    dp[i][j][0]代表对于i~j的石头堆，先手可获得的最高分数；dp[i][j][1]代表对于i~j的石头堆，后手可获得的最高分数。注意斜向遍历。
    dp[i][j][0] = max(stones[i] + dp[i+1][j][1], stones[j] + dp[i][j-1][1])// left right；
    if (first person chooses left) dp[i][j][1] = dp[i+1][j][0];；
    if (first person chooses right) dp[i][j][1] = dp[i][j-1][0];。
    这里写一个思路清晰的斜向遍历代码：
for k in range(1, length):          # k means stride
    for i in range(length - k):     # i means x-coordinate
        j = i + k                   # j means y-coordinate
  1. 10正则表达式匹配(.匹配任意单个字符，*匹配零个或多个前一字符)
    dp[i][j]表示a串前i个字符能否被b串前j个字符匹配。
  2. 139单词拆分(字符串能否拆分成一个或多个在字典中出现的单词)
    dp[i]表示字符串0-i能否用字典中的单词表示。
    if (s.substr(i, j) in dict && dp[i]) dp[j] = True;。
  3. 1227飞机座位分配概率(第一个人乱座，最后一个人坐自己座位概率)
    dp[i]表示第i个人需要找新座位(自己座位被占)的概率。
    由dp[i] = dp[1]/n + dp[2]/(n-1) ... + dp[i-2]/(n-i+3) + dp[i-1]/(n-i+2)可推导：
    dp[i-1] = dp[1]/n + dp[2]/(n-1) ... + dp[i-2]/(n-i+3)；
    dp[i] = dp[i-1] + dp[i-1]/(n-i+2)。
  4. 120三角形最小路径和(在仅能移动到下一行相邻节点的情况下找出自顶向下的最小路径和)
    dp[i][j]表示以第i行第j个元素为顶点的三角形最小路径和。
    dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + triangle[i][j];。
  5. 174地牢游戏(从左上角向右向下移动到右下角，一路不断加减对应格子的数值，生命值需大于0)
    dp[i][j]表示在(i, j)点，未吃(i, j)点血包时为成功抵达右下角需拥有的生命值-1。
    dp[i][j] = max(0, min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j])。
  6. 312戳气球(戳某个气球的得分为该气球、其左、其右三个数的乘积，求戳光气球得分最高的总分)
    dp[i][j]表示戳完第i~j个气球后得到的最高分，以k作为最后一个戳爆的气球编号进行遍历。
    for(int k = i; k <= j; k++) {dp[i][j] = max(dp[i][j], dp[i][k-1] + dp[k+1][j] + nums[i-1]*nums[k]*nums[j+1]);}。
  7. 1000合并石头的最小代价(给定数组和K，每次合并K个元素直至合并光，代价为K个元素之和)
    dp[i][j]表示在第i~j个元素经尽可能多次((j-i)%(k-1)+1)合并的最小成本。

2.搜索算法

深度优先搜索(Deep First Search, dfs)

回溯法的核心思想是将问题分步解决，而在每一步内都尝试所有的可能，当找到解或发现当前路径不可行时，回退到上一步继续尝试其他可能性，dfs则是回溯思想在图(树)上的具体表现形式，在很多情况下可将二者近似等价；由于多数情况下在每一步内的处理方式都是一致的，故递归是dfs的常用实现方式。
dfs可以理解为不撞南墙不回头，即先一条路走到底，不成功则退至最近的、尚有未遍历岔路的路口，选择下一个新岔路再走到底，循环往复。其基本思想是：当扩展的节点存在且未被遍历时，递归执行该节点。由于dfs就是简单地遍历所有情况，故其时间和空间复杂度基本均在O(n)。
(注：回溯法可适用于任何穷举法能解决的问题，DP仅能处理具有最优子结构的问题；回溯法无法大幅优化，只能暴力穷举，DP中存在重叠子问题可以优化；部分DP问题可以通过dfs+记忆化解决；DP一定需要存储子问题的解，回溯法/dfs视情况决定是否要记录当前路径。）
dfs最常用来解决树类问题。由于dfs函数常被递归调用，故常以采用helper辅助函数的形式出现。
Python下利用dfs+递归在树中寻找解的模板如下所示，同时需要思考具体的剪枝方式：

def main(root):

    def dfs_helper(root, path): 
        visited.add(root)
        if end condition: # eg:len(path) == target and path not in ans
            operation     # eg: ans.add(path.copy())
            return
        for node in root.adj():
            if node not in visited:
                path.append(node)
                dfs_helper(node, path)
                path.remove(node)

    if not root:
        return None
    visited = {}
    ans = {}
    dfs_helper(root, path=[root])
    return

在函数的具体写法上，如果path定义在dfs_helper外，则可以直接对其引用，将dfs_helper函数简化成def dfs_helper(root)。
在具体遍历时还需要考虑以下几种情况：图存在重复遍历，树不存在，故图的遍历时需要visited数组记录访问情况，而遍历树时不需要；树的叶节点可能为空，图的节点定存在，故树的遍历时需要判断当前遍历的节点是否为空，而遍历图时不需要；无向图不需要考虑遍历节点的顺序，而树的遍历需要考虑顺序(先遍历左子树还是右子树)。至于更具体的二叉树的前/中/后序遍历，参照我的另一篇博客二叉树的遍历。
在较高的角度审视上述这些代码，DFS的核心思想就是：维护走过的路径，探索当前可执行的选择列表，当触发结束条件时将当前路径记录进集合。而这些加粗的词，在某种程度上分别对应动态规划中的状态、选择和结束条件。可以说，动态规划的暴力求解阶段就是DFS。但因为DP问题具有重叠子问题的性质，通过dp table或备忘录优化，就是对DFS递归树大幅剪枝的过程。
在面对二叉树问题时，我们常常需考虑，能否使用函数在两个子树上的结果整合出当前问题的解，不要盲目冲DFS。最经典题目：树的高度height(root) = max(height(root.left), height(root.right)) + 1。
在优化时考虑非递归算法，dfs是后入先出结构，故采用栈实现。首先将初始节点压入栈，每个节点出栈时将其标记为已读并将其子节点由右至左压入栈，出栈过程即为输出过程。
遍历图的伪代码可见如下，这次只追求效率，不会再写得很像了🤠：

def dfs(start):
    visited = {start}
    stack = [start_node]
    print(start) # other op

    while(stack):
        top_of_stack = stack[-1]
        for i in iter(top_of_stack.adjacent):
            if(!visited[i]):
                print(i) # other op
                visited[i] = True
                stack.append(i)
                continue
        stack.pop(-1)

遍历二叉树的伪代码如下所示：

def dfs(root):
    stack = [root]
    while(stack):
        top_of_stack = stack.pop(-1)
        print(top_of_stack) # other op
        # for right_side_node in top_of_stack.child:
        #     stack.append(right_side_node)
        if top_of_stack.right: 
            stack.append(top_of_stack.right)
        if top_of_stack.left: 
            stack.append(top_of_stack.left)

dfs常用于解决可达性的问题。

广度优先搜索(Breath First Search, bfs)

bfs可以类比树的层序遍历。
bfs是先入先出结构，采用队列实现。
首先将初始节点压入队列，在节点出队列时进行输出/判断。由左至右地扩展出队列节点的子节点，若未遍历过则将其压入队列，同时标记为已读。
BFS问题的本质在于解决无权图内，起点到终点的的最短路径问题。当第一次遍历到目标节点时，所经过的路径为最短路径。在实现时，需注意使用队列存储节点，也不要忘记对遍历过的节点做标记。
Python伪代码如下所示：注意其中节点弹出、扩展及step累计的语句位置，背就完了。

# calculate the shortest distance from 'root' to 'target'.
def BFS(root, target):
    queen = [root]
    # use 'visited' to avoid repeat traversal in 'graph', no longer needed in 'tree'.
    visited = {root}  
    step = 0

    while queen:
        size = len(queen)
        for i in range(size):
            node = queen.pop(0)
            if (node == target):
                return step
            # expand current node
            for x in node.adj():
                if x not in visited:
                    queen.append(x)
                    visited.add(x)
        step = step + 1

C++伪代码如下所示：

// calculate the shortest distance from 'start' to 'target'.
int BFS(Node start, Node target) 
{
    queue<Node> q{start}; 
    unordered_set<Node> visited{start}; 

    int step = 0;
    while(!q.empty())
    {
        int size = q.size();
        for(int i = 0; i < size; i++) 
        {
            Node cur = q.front();
            q.pop();
            
            if(cur == target)
                return step;
            
            while(cur.adj())
            {
                Node x = cur.adj();
                if(!visited.count(x))
                {
                    q.push(x);
                    visited.insert(x);
                }
            }
        }
        step = step + 1;
    }
}

对于已知终点具体值的题型，有一种同量级复杂度下的优化trick：双向BFS。其核心思想是，从起点和终点同时扩展，当二者各自扩展得到的集合有交集时停止。具体在代码实现时，每次仅扩展一个集合，但在每个while循环的开始时，通过判断大小和集合交换，仅对规模相对较小的集合进行扩展，整体上便实现了双向扩展。需要终止条件的判断位置，由于不会对已遍历过的节点进行扩展，故不可在出栈时进行判断，而应在扩展节点时进行终止判断。
Python伪代码如下所示：

# calculate the shortest distance from 'start' to 'target'.
def BFS(start, target):
    queen1 = [start]
    queen2 = [target]
    # use 'visited' to avoid repeat traversal in 'graph', no longer needed in 'tree'.
    visited = {start, target}  
    step = 0

    while queen1 and queen2:
        if len(queen1) > len(queen2):
            queen1, queen2 = queen2, queen1
        size = len(queen1)
        for i in range(size):
            cur = queen1.pop(0)
            # expand node 'cur'
            for x in cur.adj():
                if x in queen2:
                    return step + 1
                if x not in visited:
                    queen1.append(x)
                    visited.add(x)
        step = step + 1

相较于DFS，BFS在解决最短路径问题时的时间复杂度会低很多(无须遍历所有情况，第一次遍历到正确解时即可返回)，但空间复杂度会相对较高。

BFS/DFS思路总结

BFS和DFS两个方法主要是对树、图进行遍历，即从某点出发，对所有顶点进行访问且只访问一次。
一般来说在找最短路径时用BFS，其余时候主要采用DFS。

为回溯，采用邻接矩阵（二维数组）和邻接表对遍历过程进行记录。
我们常将解题的过程融入到出/入 栈/队列的过程中。

二分搜索

二分查找的核心思路就是通过不断收缩左右边界在有序元素中进行高效查找。
二分查找的基本思路如下所示：

low, high = 0, len(nums)
# search in [low, high)
while(low < high):
    mid = low + (high - low) // 2
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        low = mid + 1 # search in [mid + 1, high)
    else:
        high = mid # search in [low, mid)
return low

C++中的lower_bound()函数和upper_bound()函数则意欲返回第一个大于等于target和第一个大于target的元素索引。也正是因为target可能不存在于数组中，故代码均进行了微小的调整（以下将两份代码写在一起)：

low, high = 0, len(nums)
# search in [low, high)
while(low < high):
    mid = low + (high - low) / 2
    if nums[mid] < target:  # lower bound
    if nums[mid] <= target: # upper bound
        low = mid + 1 # search in [mid + 1, high)
    else:
        high = mid # search in [low, mid)
return low

3. 树

树是由具有父子关系的节点构成的常见数据结构。算法题中常基于二叉树进行知识点的考察。
二叉树解题的方法主要分两种，一种是递归，一种是迭代。当题目有较清晰的子结构时可以选择递归。递归调用系统栈，可能占较大空间，但胜在思路清晰；可通过手动维护一个栈/队列的方式将解法优化成迭代方法。当然，部分题目可能会涉及广度/深度优先搜索的知识，需灵活变通。

树的遍历

参考Leetcode官解的一张图：
遍历方式示意图
不难得出：前、中、后序遍历的核心思想均是深度优先搜索，基于栈实现；层序遍历的核心思想是广度优先搜索，基于队列实现。
以下给出树的前、中、后序遍历的递归/迭代写法。注意，所有遍历方法都需谨慎考虑空节点情形。

前序遍历(preorder traversal)：对根节点的处理是在处理子节点之前进行的。以二叉树为例，先遍历根节点，再遍历左节点、右节点。
类比实例：遍历目录。其背后的逻辑可以用代码来解释：

def func(Root Node):
    print(Root Node)
    for each Child Node of Root Node:
        func(Child Node)

递归：从左至右遍历所有节点。

def dfs(root):
    if root:
        print(root) # other op
        dfs(root.left)
        dfs(root.right)

在此过程中需注意边界条件(叶节点/空节点)的判断和扩展节点的顺序(从左到右)。
迭代：dfs是后入先出结构，故采用栈实现。首先将初始节点压入栈，每个节点出栈时将其标记为已读并将其子节点由右至左压入栈，出栈过程即为输出过程。

def dfs(root):
    stack = [root]
    while(stack):
        node = stack.pop()
        print(node) # other op
        if node.right: 
            stack.append(node.right)
        if node.left: 
            stack.append(node.left)

还有一种近似于模板的写法，其思路为：先将根节点和所有的左孩子入栈并输出，每次当前节点为空时，弹出栈顶元素并访问其右孩子，循环操作。

def dfs(root):
    cur = root
    stack = []
    while cur or stack:
        if cur:
            print(cur) # other op
            stack.append(cur)
            cur = cur.left
        else:
            tmp = stack.pop()
            cur = tmp.right

中序遍历(inorder traversal)：对根节点的处理是在处理子节点之间进行的。以二叉树为例，先遍历左节点，再遍历根节点，最后遍历右节点。
类比实例：表达式树的读取。可以尝试将ab+cde+**的输入转换为(a+b) * (c*(d+e))。
递归：

def dfs(root):
    if root:
        dfs(root.left)
        print(root) # other op
        dfs(root.right)

迭代：参考上述模板，这次是在出栈时输出：

def dfs(root):
    cur = root
    stack = []
    while cur or stack:
        if cur:
            stack.append(cur)
            cur = cur.left
        else:
            tmp = stack.pop()
            print(tmp) # other op
            cur = tmp.right

后序遍历(postorder traversal)：对根节点的处理是在处理子节点之后进行的。以二叉树为例，先遍历左节点、右节点，再遍历根节点。
类比实例：统计目录内文件总容量。其背后的逻辑可以用代码来解释：

def size(Root Node):
    for each Child Node of Root Node:
        total_size += size(Child Node)
    total_size += size(Root Node)

递归：

def dfs(root):
    if root:
        dfs(root.left)
        dfs(root.right)
        print(root) # other op

迭代：后序遍历的迭代方法较为复杂，一种方法是将前序遍历的根-左-右代码稍加调整，变成根-右-左形式，再倒序输出结果，此方法不够劲，此处不加赘述。此处介绍一种基于辅助数组记忆已遍历节点的方法：

def bfs(root):
    stack = [(0, root)] # untraversed
    while stack:
        flag, node = stack.pop()
        if not node: 
            continue
        if flag:
            print(node)
        else:
            stack.append((1, node))
            stack.append((0, node.right))
            stack.append((0, node.left))

层序遍历(level-order traversal)：层序遍历与广度优先搜索方法类似，深度从小到大地逐层处理节点，采用队列进行实现。由于遍历时不存在明显的子结构，故放弃递归思路，用迭代法进行实现。
迭代：迭代法的核心思路是将初始节点压入队列后，在出队列输出该节点的同时，从左到右遍历并将其子节点压入队列。

def bfs(root):
    queen = [root]
    while queen:
        node = queen.pop(0)
        print(node) # other op
        if node.left:
            queen.append(node.left)
        if node.right:
            queen.append(node.right)

以上部分代码参考博客，在此致谢。

树的递归解法

以Leetcode104 二叉树的最大深度为例：

    int maxDepth(TreeNode* root) {
        if (root == nullptr) 
            return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }

以Leetcode235 二叉搜索树的最近公共祖先为例：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {

        //recursive
        if ((root->val > p->val) && (root->val > q->val))
            return lowestCommonAncestor(root->left, p, q);
        if ((root->val < p->val) && (root->val < q->val))
            return lowestCommonAncestor(root->right, p, q);
        return root;

        //iteratively
        TreeNode* cur = root;
        while(true)
        {
            if((cur->val > p->val)&&(cur->val > q->val))
                cur = cur->left;
            else if((cur->val < p->val)&&(cur->val < q->val))
                cur = cur->right;
            else
                break;
        }
        return cur;
    }
};

树的基本知识

二叉树：二叉树的平均深度为O(n)O(\sqrt {n})。
二叉查找树(ADT)：对于二叉树中的任一节点X，X的左子树中所有的值均小于X的值，X的右子树中所有的值均大于X的值。易知二叉查找树的平均深度是O(logn)，增删查改的时间复杂度也为O(logn)。
AVL树(Adelson-Velskii和Landis)：由于二叉查找树在多次插入和删除后可能不平衡，故产生了带有平衡条件的二叉查找树--AVL树。AVL树是每个节点的左子树和右子树的高度最多差1的二叉查找树。实践中，若单次插入使AVL树失衡，通过单旋转/双旋转操作来在O(logN)内平衡树。
当然，二叉树还有很多分类，例如斜树、完全二叉树、满二叉树等。
伸展树(splay tree)：二叉查找树和伸展树的单次最坏运行时间均为O(N)，但二叉查找树的连续M次最坏运行时间为O(MN)，伸展树的连续M次最坏运行时间为O(MlogN)，即每次操作的摊还代价是O(logN)。
伸展树的基本想法是，当一个节点被访问后，它就要经过一系列AVL树的旋转放到根上。实际操作中，通过对之字形(zig-zag)和一字形(zig-zig)的不同展开，在将访问节点移动到根处的基础上，将访问路径上大部分节点的深度大致减少一半。
B树：阶为M的B树有如下结构特性：
1 树的根要么为一片树叶，要么其儿子数在2和M之间；
2 除根外，所有非树叶节点的儿子数在⌈M/2⌉\lceil M/2 \rceil和M之间；
3 所有的树叶都在相同的深度上。
所有数据都存储在树叶上，每个内部节点上皆有指向该节点各儿子的指针P1，P2...，Pm和分别代表在子树P2，P3...，Pm中发现的最小关键字的值k1，k2...，km-1。每次find操作时，都从根开始，依据查找的关键字和存储在节点上值来确定当前层在n个方向中的一个方向，直到在最底层找到对应数据。
在插入时若当前树的平衡被破坏(阶为M的B树的某一个节点的儿子数大于M)，常通过分裂节点来解决，一些情况下也可以将数据迁移到临近的节点中。同理，删除节点时若破坏平衡，可通过与周围节点进行合并来解决。
对于一次find操作，途径的节点个数为logMNlog_{M}{N}，在路径上的每个节点需要花费O(logM)来确认分支的方向，故find操作的时间复杂度为O(logN)。对于一次插入/删除操作，在某个节点处，最坏时需要O(M)来调整该节点所有信息，整体运算的最坏运行时间为O(MlogMN)O(Mlog_{M}{N})。
B树的最大深度为⌈log⌈M/2⌉N⌉\lceil{log_{\lceil M/2 \rceil}N}\rceil。从运行时间考虑，M最优选择为3或4；从数据库应用考虑，为了使内部节点装满一个磁盘区块，常有32≤M≤256{32}\le{M}\le{256}。

4.数组、链表

链表

数据结构的存储方式只有两种：数组(顺序存储)和链表(链式存储)。数据结构的核心目的是在不同的场景中，尽可能高效地遍历和访问(增删查改)。
二者的特性对比可如下表所示：

实现方法\操作 Find_Kth Find_Key 插入 删除
数组 常数时间 线性时间 线性时间 线性时间
链表 线性时间 线性时间 线性时间 线性时间

链表在插入和删除元素时的时间主要花在遍历上。若已经拿到了要删除/插入节点及其前驱节点的信息，时间复杂度骤降到O(1)。链表还有其他形式，例如双链表、循环链表、多重表等。
链表类题目的解法主要有快慢指针法。

5. 栈和队列

栈和队列都隶属于线性表结构。

栈

栈是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈的顶端。栈可以理解为后进先出表。
栈可以通过单链表或数组实现。在单链表实现中，表的前端作为栈顶，所有操作均花费常数时间，但该方法的缺点在于对malloc和free的开销昂贵的；更流行的方法是采用数组实现，唯一缺点是需要提前声明一个数组的大小，且错误检测(数组越界)可能影响栈的执行效率。

队列

队列是在末端插入，在开头删除的表。
在采用数组实现队列时，会维护位置变量Front和Rear。为防止队列溢出，只要位置变量达到数组的末端，它就又绕回开头。

优先队列
优先队列是允许至少插入和删除最小者(找出、返回并删除优先队列的最小元素)的数据结构。二叉堆(堆，binary heap)可以在O(logN)内支持以上两种操作。
二叉堆具有结构性和堆序性，每次对堆的操作均需要到堆的所有性质全被满足时方可停止。
结构性：堆满足完全二叉树结构，一个堆数据结构由一个数组、一个代表最大值的整数和当前的堆大小组成。
堆序性：在堆的任意非根节点中，节点的关键字大于其父辈节点的关键字。换而言之，根节点最小。
在插入元素X时，在堆的下一个空闲位置创建一个空穴，若不满足堆结构，将空穴父节点的元素移入空穴，元素上移一层，迭代直至将X合理插入。这种方法称为上滤：新元素在堆中上滤直到找出正确的位置。

散列
散列以常数平均时间进行插入、删除和查找，但不支持任何基于元素间排序的的操作。
散列表数据结构是一个含有关键字的固定大小的数组，通常情况下，关键字是一个带有相关值的字符串(类比Python中的字典结构：关键字key和相关值value)。将每个关键字使用散列函数(Hash function)映射到0至TableSize-1范围中的一个数字，再在数组对应位置存放关键字对应的值。理想情况下，函数在运算简单的同时应尽可能在单元间均匀地分配关键字。
当一个元素准备插入处已存在另一个元素时(二者散列值相同)，为消除冲突，常采用分离链接法和开放定址法。
开放定址法的核心思路是在冲突发生时不断选择另外的单元，直到找到空的单元。此方法要求表稍大，装填因子应小于0.5。常用方法有线性探测法，平方探测法和双散列法。

6.贪心算法

套路总结

解题思路

Leetcode实战

  1. 435/452基于贪心的区间调度(计算若干区间中最多有几个互不相交的区间)
    依右区间大小对所有区间升序排序，(1)选取当前的第一个区间x(即右区间最小，结束最早的空间)，(2)将所有与x相交的区间从集合内删除，重复步骤(1)(2)直到集合为空，遍历过的x区间并集即为题解。
  2. 1029两地调度(给定花费，求一半人去A地另一半人去B地的最小花费)
    对所有人以price_A - price_B降序排序，前一半人去B，后一半人去A。可以理解为某个人去B地就是给组织节省price_A - price_B的钱，需求节省钱的最大值。

7. 位运算

先熟悉一下Python3的常用运算符

运算符 功能 用例
/ 除法 12 / 5 = 2.4
// 向下取整除 5 // 2 = 2; -10 // 3 = -4
% 取模(返回除法余数) 10 % 3 = 1; 10 % -3 = -2
& 按位与 60(0011 1100) & 13(0000 1101) = 12(0000 1100)
| 按位或 60(0011 1100) | 13(0000 1101) = 61(0011 1101)
^ 按位异或 60(0011 1100) ^ 13(0000 1101) = 49(0011 0001)
~ 按位取反 ~60(0011 1100) = -61(1100 0011)
<< 左移若干位(高位丢弃，低位补0) 60(0011 1100) << 2 = 240(1111 0000)
>> 右移若干位(高位补0，低位丢弃) 60(0011 1100) >> 2 = 15(0000 1111)

n.Leetcode刷题心得

普遍规律

  1. 进行极端值的判断，eg判断输入数组为空、输入数组仅单元素时程序的合理性；同时需要注意算法的索引是否会超过边界。
  2. 具有子结构的题目请优先考虑递归。
Bad decisions make good stories.