zdaiot

404NotFound

LeetCode总结

发表于 分类于
本文字数： 61k 阅读时长 ≈ 56 分钟

二叉树

二叉树遍历模板

  1. 前序遍历：先访问根节点，再前序遍历左子树，再前序遍历右子树
  2. 中序遍历：先中序遍历左子树，再访问根节点，再中序遍历右子树
  3. 后序遍历：先后序遍历左子树，再后序遍历右子树，再访问根节点

注意点：

  1. 以根访问顺序决定是什么遍历

  2. 左子树都是优先右子树

练习：

144. 二叉树的前序遍历

145. 二叉树的后序遍历

94. 二叉树的中序遍历

递归法

递归法三要素：

  1. 确定递归函数的参数和返回参数：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么，进而确定递归函数的返回类型；
  2. 确定终止条件；
  3. 确定单层递归逻辑：这里需要假定嵌套问题已经解决了。

前序遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

中序遍历：

1
2
3
4
5
6
void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    vec.push_back(cur->val);    // 中
    traversal(cur->right, vec); // 右
}

后序遍历：

1
2
3
4
5
6
void traversal(TreeNode* cur, vector<int>& vec) {
    if (cur == NULL) return;
    traversal(cur->left, vec);  // 左
    traversal(cur->right, vec); // 右
    vec.push_back(cur->val);    // 中
}

迭代法

前序遍历（迭代法）不难写出如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> preorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    vector<int> result;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        if (node != NULL) result.push_back(node->val);
        else continue;
        st.push(node->right);  // 栈是先进后出，访问顺序是根左右，所以先让右节点入栈
        st.push(node->left);
    }
    return result;
}

用迭代法很难写出统一的模板，在迭代过程中，有两个操作，一个是处理：将元素放进result数组中，一个是访问：遍历节点。前序遍历的顺序是中左右，要先访问的元素是中间节点，要处理的元素也是中间节点，要访问的元素和要处理的元素顺序是一致的，都是中间节点，所以才能写出相对简洁的代码。

中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

中序遍历，可以写出如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur != NULL || !st.empty()) {
        if (cur != NULL) {  // 一层一层的向下访问，直到树左边的底层
            st.push(cur);
            cur = cur->left;
        } else {  // 
            cur = st.top();
            st.pop();
            result.push_back(cur->val);
            cur = cur->right;
        }
    }
    return result;
}

4f49ee1ccbd7b2d641a740d63a68f69146dc0bcb6dd5c0471e4289730d902352-image

所以后序遍历只需要前序遍历的代码稍作修改就可以了，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> postorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    vector<int> result;
    st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top();
        st.pop();
        if (node != NULL) result.push_back(node->val);
        else continue;
        st.push(node->left); // 相对于前序遍历，这更改一下入栈顺序
        st.push(node->right);
    }
    reverse(result.begin(), result.end()); // 将结果反转之后就是左右中的顺序了
    return result;
}

DFS常见题目

110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

二叉树的高度：从该节点到叶子节点的最长简单路径边的条数。

二叉树的高度和深度的定义如下图所示。关于根节点的深度究竟是1 还是 0，不同的地方有不一样的标准，leetcode的题目中都是以节点为一度，即根节点深度是1。但维基百科上定义用边为1度，即根节点的深度是0，我们暂时以leetcode为准。

110.平衡二叉树2

该题目可以使用递归的方法解决，递归三步曲分析：

  1. 明确递归函数的参数和返回值：
    • 参数：当前传入节点。
    • 返回值：以当前传入节点为根节点的树的高度。使用-1返回值来表示当前已经不是平衡二叉树了，不需要返回高度了。
  2. 明确终止条件：递归的过程中依然是遇到空节点了为终止，返回0，表示当前节点为根节点的树高度为0。
  3. 明确单层递归的逻辑：分别求出其左右子树的高度，然后如果差值小于等于1，则返回当前二叉树的高度，否则则返回-1，表示已经不是二叉平衡树了。

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    // 返回以该节点为根节点的二叉树的高度，如果不是平衡二叉树了则返回-1
    int getHeight(TreeNode* node) {
        if (node == NULL) {
            return 0;
        }
        int leftHeight = getHeight(node->left);
        if (leftHeight == -1) return -1; // 不再继续递归了
        int rightHeight = getHeight(node->right);
        if (rightHeight == -1) return -1;
        return abs(leftHeight - rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);
    }
    bool isBalanced(TreeNode* root) {
        return getHeight(root) == -1 ? false : true;
    }
};

当然迭代三部曲中，也可以将高度作为参数，返回值是当前树是否为平衡二叉树，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool isBalancedCore(TreeNode* root, int& depth) {
    if(root==NULL) {
        depth = 0;
        return true;
    }

    int leftD, rightD;
    if(isBalancedCore(root->left, leftD) && isBalancedCore(root->right, rightD)) {
        if(abs(leftD-rightD) <= 1) {
            depth = 1 + (leftD > rightD?leftD:rightD);
            // depth = max(leftD, rightD) + 1;
            return true;
        }
    }
    return false;
}

bool isBalanced(TreeNode* root) {
    int depth;
    return isBalancedCore(root, depth);
}

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

这道题考察的是DFS（深度优先搜索算法）。我们按照递归三要素进行讲解：

  • 找出终止条件：当前节点为空
  • 找出返回值：节点为空时说明高度为 0，所以返回 0；节点不为空时则分别求左右子树的高度的最大值，同时加1表示当前节点的高度，返回该数值
  • 某层的执行过程：在返回值部分基本已经描述清楚

参考代码：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr)
            return 0;
        int left_depth = maxDepth(root->left);
        int right_depth = maxDepth(root->right);
        int res = max(left_depth, right_depth) + 1;
        return res;
    }
};

124. 二叉树中的最大路径和

路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

一般而言，关于二叉树的题目都可以用递归方法解决。我们按照递归的三要素进行分析。

  1. 确定递归函数的参数和返回参数：很明显在递归过程中除了要将TreeNode*作为参数之外，还需要记录两个值，一个是全局最大路径和，一个是当前节点能够给上层节点带来的最大值。前者可以用全局变量ans表示，后者可以用函数返回值表示，因为该返回值跟maxPathSum返回值含义不同，所以需要重新写一个函数maxPathsumCore。
  2. 确定终止条件：存在两种情况，若当前节点为空节点，则返回0；当左右子树遍历完毕，需要计算当前节点能够给上层节点带来的最大值，这需要从 当前节点、当前节点+左子树、当前节点+右子树中取出来最大值。需要注意的是，当前节点+左子树+右子树是一条封闭路径，它不能给上层节点带来贡献值，所以不能返回该值。
  3. 确定单层递归逻辑：这里需要假定嵌套问题已经解决了，也就是假设左右子树最大值已经求出来了，这时需要求出来 当前节点、当前节点+左子树、当前节点+右子树、当前节点++左子树+右子树 中的最大值，与全局变量ans比较并更新。

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
private:
    int maxPathsumCore(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int leftMax = max(0, maxPathsumCore(root->left));
        int rightMax = max(0, maxPathsumCore(root->right));
        int nowMax = root->val + leftMax + rightMax;
        if (nowMax > ans)
            ans = nowMax;
        return root->val + max(leftMax, rightMax);
    }
public:
    int ans = INT_MIN;
    int maxPathSum(TreeNode* root) {
        maxPathsumCore(root);
        return ans;
    }
};

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

根据定义，若 root是 p, q的 最近公共祖先 ，则只可能为以下情况之一：

  • p 和 q 在 root 的子树中，且分列 root 的 异侧（即分别在左、右子树中）；
  • p = root，且 q 在 root 的左或右子树中；
  • q = root，且 p 在 root 的左或右子树中；

考虑通过递归对二叉树进行先序遍历，当遇到节点 p 或 q 时返回。从底至顶回溯，当节点 p, q 在节点 root 的异侧时，节点 root 即为最近公共祖先，则向上返回 root。

一般而言，关于二叉树的题目都可以用递归方法解决。我们按照递归的三要素进行分析。

  1. 确定递归函数返回值以及参数：需要递归函数返回值，来告诉我们是否找到节点q或者p，那么返回值为bool类型就可以了。但我们还要返回最近公共节点，可以利用上题目中返回值是TreeNode *，那么如果遇到p或者q，就把q或者p返回。返回值不为空，就说明找到了q或者p；返回值为空，则说明没找到。

  2. 确定终止条件：如果找到了 节点p或者q，或者遇到空节点，就返回，不继续递归了。后者比较好理解，前面怎么理解呢？遇到了前面，有如下几种情况：

    • 找到了节点p/q，同时q/p位于它的左/右子树。此时当前节点就是要找的最近公共祖先，所以返回当前节点。
    • 找到了节点p/q，但是另外一个节点q/p不在它的左/右子树，此时也没有递归的需要了，因为再递归也找不到q/p了。将当前节点返回，将结果向上一次递归传递。

    所以，这两种情况，都可以确定是需要终止递归的。

  3. 确定单层递归逻辑：开启递归左子节点，返回值记为 left；开启递归右子节点，返回值记为 right。根据 left和 right ，可展开为四种情况。

    • 如果left 和 right 同时为空，则说明 root 的左 / 右子树中都不包含 p,q，返回 null；
    • 如果left 和 right 都不为空，说明此时root就是最近公共节点；
    • 如果left 为空，right不为空，说明p和q都不在root的左子树中，则返回right。具体的情况如下
      • p，q其中一个在root的右子树，此时 right指向 p（假设为 p，也就是right的值）；
      • p，q都在root的右子树，则此时的right指向最近公共祖先节点。
    • 当 left不为空 ， right为空 ：与第三种情况同理。

    情况一和合并到情况三、四。

这里重点介绍一下为啥left为空，right不为空，目标节点通过right返回呢？以right指向最近的公共祖先节点为例，如下图所示，图中节点10的左子树返回null，右子树返回目标值7，那么此时节点10的处理逻辑就是把右子树的返回值（最近公共祖先7）返回上去！

236.二叉树的最近公共祖先1

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            //只要当前根节点是p和q中的任意一个，就返回（因为不能比这个更深了，再深p和q中的一个就没了）
            return root;
        }
        //根节点不是p和q中的任意一个，那么就继续分别往左子树和右子树找p和q
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        //p和q都没找到，那就没有
        if(left == null && right == null) {
            return null;
        }
        //左子树没有p也没有q，就返回右子树的结果
        if (left == null) {
            return right;
        }
        //右子树没有p也没有q就返回左子树的结果
        if (right == null) {
            return left;
        }
        //左右子树都找到p和q了，那就说明p和q分别在左右两个子树上，所以此时的最近公共祖先就是root
        return root;
    }
}

简化之后的代码：

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr || root == p || root == q) return root;
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if(left == nullptr) return right;
        if(right == nullptr) return left;
        return root;
    }
};

BFS常见题目

102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

与前面几道题使用的DFS不同，这里使用到了BFS思想。需要借助于队列来实现。

首先对比一下DFS与BFS的代码区别：

DFS 遍历使用递归：

1
2
3
4
5
6
7
void dfs(TreeNode root) {
    if (root == null) {
        return;
    }
    dfs(root.left);
    dfs(root.right);
}

BFS遍历使用队列数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
void bfs(TreeNode root) {
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll(); // Java 的 pop 写作 poll()
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
}

只是比较两段代码的话，最直观的感受就是：DFS 遍历的代码比 BFS 简洁太多了！这是因为递归的方式隐含地使用了系统的 栈，我们不需要自己维护一个数据结构。如果只是简单地将二叉树遍历一遍，那么 DFS 显然是更方便的选择。

虽然 DFS 与 BFS 都是将二叉树的所有结点遍历了一遍，但它们遍历结点的顺序不同。这个遍历顺序也是 BFS 能够用来解「层序遍历」、「最短路径」问题的根本原因。

回到本题，乍一看，层次遍历顺序和 BFS 是一样的，我们可以直接用 BFS 得出层序遍历结果。层序遍历要求的输入结果和 BFS 是不同的。层序遍历要求我们区分每一层，也就是返回一个二维数组。而 BFS 的遍历结果是一个一维数组，无法区分每一层。

观察结点进队列和出队列的过程，可以修改代码，在每一层遍历开始前，先记录队列中的结点数量 n（也就是这一层的结点数量），然后一口气处理完这一层的 n个结点，这样就可以实现层次遍历了。

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (root == nullptr)
            return result;
        
        queue<TreeNode*> q;
        q.push(root);
      	// 若非空，则一直循环
        while(!q.empty()) {
            int n = q.size();
            vector<int> tmp;
            // 当前层次的
            for(int i=0; i<n; i++) {
                TreeNode* node = q.front();
                tmp.push_back(node->val);
                q.pop();
								// 下一层次的
                if(node->left)
                    q.push(node->left);
                if(node->right)
                    q.push(node->right);
            }
            result.push_back(tmp);
        }
        return result;
    }
};

107. 二叉树的层序遍历 II

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

这道题跟102题相比，无非就是从自上向低，改成了自底向上。最简单的方法就是将上一题的答案，reverse以下。如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> result;
        if (root == nullptr)
            return result;
        
        queue<TreeNode*> q;
        q.push(root);
      	// 若非空，则一直循环
        while(!q.empty()) {
            int n = q.size();
            vector<int> tmp;
            // 当前层次的
            for(int i=0; i<n; i++) {
                TreeNode* node = q.front();
                tmp.push_back(node->val);
                q.pop();
								// 下一层次的
                if(node->left)
                    q.push(node->left);
                if(node->right)
                    q.push(node->right);
            }
            result.push_back(tmp);
        }
      	// 相比102题，添加了这一行
        reverse(result.begin(), result.end());
        return result;
    }
};

当然，还可以每次迭代当前层次时，在前面insert一个vector，如下所示，但是采取insert比较耗时，因为每次插入都得移动元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ret;
        if(root == NULL)
            return ret;
        
        queue<TreeNode *> q;
        q.push(root);
        while(!q.empty())
        {
            ret.insert(ret.begin(),vector<int>());
            int n = q.size();
            for(int i=0; i<n; i++)
            {
                TreeNode* node = q.front();
                q.pop();
                ret.front().push_back(node->val);
                if(node->left)
                    q.push(node->left);
                if(node->right)
                    q.push(node->right);
            }
        }
        return ret;
    }
};

103. 二叉树的锯齿形层序遍历

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

遇到这道题，跟102题相比，第一反应想的是，用一个变量记录奇偶性。此时用两种解法，

  1. 当是偶次遍历时，就翻转一下结果。
  2. 如果是奇数，则从队头读，在队尾插入左右；如果是偶数，则从队尾读，并在队头插入右左。

这两种方法时间差不多，但是第一种更不容易出错。这里给出第一种方法的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (root == nullptr)
            return result;
        
        queue<TreeNode*> q;
        q.push(root);
        int count = 0;
      	// 若非空，则一直循环
        while(!q.empty()) {
            int n = q.size();
            vector<int> tmp;
            // 当前层次的
            for(int i=0; i<n; i++) {
                TreeNode* node = q.front();
                tmp.push_back(node->val);
                q.pop();
                // 下一层次的
                if(node->left)
                    q.push(node->left);
                if(node->right)
                    q.push(node->right);
            }
          	// 翻转结果
            if (count % 2 == 1)
                reverse(tmp.begin(), tmp.end());
            count++;
            result.push_back(tmp);
        }
        return result;
    }
};

参考

彻底吃透前中后序递归法（递归三部曲）和迭代法（不统一写法与统一写法）
画解算法：104. 二叉树的最大深度
#236. 二叉树的最近公共祖先
236. 二叉树的最近公共祖先（DFS ，清晰图解）
BFS 的使用场景总结：层序遍历、最短路径问题

链表

理论

链表代码经常考察点在于指针的理解，也就是NULL指针的处理，比如说有一个结构体Node，结构体指针为node*，访问结构体成员变量node->val的时候，要先判断node是否等于NULL。

常用技巧：

  1. 设置哑点可以简化很多判断和处理。当你需要创造一条新链表的时候，可以使用虚拟头结点简化边界情况的处理。

    比如说，让你把两条有序链表合并成一条新的有序链表，是不是要创造一条新链表？再比你想把一条链表分解成两条链表，是不是也在创造新链表？这些情况都可以使用虚拟头结点简化边界情况的处理。

  2. 快慢指针、双指针的使用

  3. 得到链表的中心节点之后翻转链表（可以翻转前半部分，也可以翻转后半部分。翻转前半部分指针代码更加简单）

这里补充一个常用代码，链表借助双指针，找到中间节点slow，若链表为偶数个元素，则slow节点在前半段的最后一个元素。

1
2
3
slow, fast = head, head.next
while fast and fast.next:
	fast, slow = fast.next.next, slow.next

若写成下面形式，则若链表为偶数个元素，则slow节点在后半段的第一个元素。

1
2
3
slow, fast = head, head
while fast and fast.next:
	fast, slow = fast.next.next, slow.next

常见题目

83. 删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

这个题目需要使用双指针的方法，一个指针记录前一个指针，一个指针记录当前遍历到的指针。若两个指针的元素值相同，则删除当前节点，否则的话，更新两个指针。

参考代码如下。为了简化代码，这里使用了cur和cur->next代替双指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode* deleteDuplicates(ListNode* head) {
    ListNode* cur = head;
    while(cur && cur->next) {
        // 如果节点值相同
        if(cur->next->val == cur->val) {
            cur->next = cur->next->next;   // 不需要更新cur指针
        }
        else {
            cur = cur->next;
        }
    }
    return head;
}

82. 删除排序链表中的重复元素 II

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

这个题目和上一个题目的区别在于，上一个题目重复出现的只保留一个，而这里重复出现的数字则需要全部删除。

首先，在上一个题目中首节点是不可能被删除的，而在本题目中首节点是有可能被删除的，所以需要借助哑点处理。另外需要删除所有重复的数字，刚拿到题目的思路是采用三指针的方法，但是这种方法的容易出错并且代码比较复杂。

因此可以换一种思路，我们使用双指针法，指针l记录左节点，指针r记录右节点。每次循环的时候，初始化l=r，若l->val=r->val则不断向后移动r指针（因为初始化了l=r，所以初始l->val=r->val一定成立）。

  1. 若l->next==r，则说明l->val肯定是唯一的，将l指针放到结果中，但此时r->val不一定是唯一的，所以重新初始化l=r；
  2. 若l->next!=r，则说明l到r->pre之间所有的值都是重复的，不更新结果，同样此时r->val不一定是唯一的，所以重新初始化l=r；

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ListNode* deleteDuplicates(ListNode* head) {        
    ListNode* dummy = new ListNode(-1);  // 哑点
    ListNode* node = dummy;
    
    ListNode* r = head;
    for(ListNode* l=head; l!=NULL; l=r) {  // 不管l节点是不是唯一，r节点是否唯一都不能得到结论，所以更新l=r
        while(r && l->val==r->val) r = r->next;
        if(l->next == r) {  // 若满足则说明l节点肯定是唯一的，不能用r-l==1，因为两个都是表示地址
            node->next = l;  // 将l指针添加到最后结果中
            node = node->next;
            node->next = NULL;  // 不要忘记置为NULL，否则当输入是[1,2,2]，预期输出[1]，实际输出[1,2,2]。
        }
    }
    return dummy->next;
}

206. 反转链表

反转一个单链表。

该题是典型的双指针题目，需要用一个pre指针记录前一个节点，一个node指针记录当前节点。这里需要注意的地方是pre指针的初始化特别重要，需要初始化为pre=NULL。

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
ListNode* reverseList(ListNode* head) {
    ListNode* pNode = head;
    ListNode* pPre = NULL;  // 这个初始化很重要
    while(pNode != NULL)  {
        ListNode* pNext = pNode->next;  // 记录下一个节点         
        pNode->next = pPre;  // 之前的pNode->next在pNext中记录了，这里更新对其不影响
        pPre = pNode;
        pNode = pNext;
    }
    return pPre;
}

92. 反转链表 II

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明:1 ≤ m ≤ n ≤ 链表长度。也就是说 m 和 n 的下标都是从1开始的。

这个题目有一个要求就是一趟扫描完成反转。定义两个指针，分别为g（guard）和p（point）。首先根据参数m确定g和p的位置。将g移动到第一个要反转的节点前面，将p移动到第一个要反转的节点位置上。以m=2,n=4为例：

5389db651086bd4bcd42dd5c4552f180b553a9b204cfc1013523dfe09beac382-1

然后使用头插法，将p后面的元素删除，然后添加到g的后面，重复该步骤。如下图所示：

db22bdb60035e45f8c354b3f45f2a844260d6cafcf81528d2c4f1b51e484fb45-2

最后返回dummyHead->next。

这里需要注意的是，根据m是否等于1，返回的结果是不一样的。为了避免对这些情况进行分类讨论，可以借助哑点。参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ListNode* reverseBetween(ListNode* head, int m, int n) {
    ListNode* dummyHead = new ListNode(0);
    dummyHead->next = head;
    ListNode* g = dummyHead;
    ListNode* p = dummyHead->next;
    
    for(int i=0; i<m-1; i++) { // 将g移动到第一个要反转的节点的前面，将p移动到第一个要反转的节点的位置上
        g = g->next;
        p = p->next;
    }

    for(int i=0; i<n-m; i++) {  // 由上图可得知，并不需要更新g、p指针
        ListNode* removed = p->next;
        p->next = p->next->next;
        removed->next = g->next;  // 注意这个地方不能直接等于p，画到第二次循环即可明白
        g->next = removed;
    }
    return dummyHead->next;
}

21. 合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

这个一个很典型的需要借助哑点来简化代码的题目。思想比较简单，参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode* dummyHead = new ListNode(0);
    ListNode* cur = dummyHead;
    while(l1!=NULL && l2!=NULL) {
        if(l1->val < l2->val) {
            cur->next = l1;
            l1 = l1->next;
        }
        else {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }
    if(l1 == NULL)
        cur->next = l2;
    else
        cur->next = l1;
    return dummyHead->next;
}

86. 分隔链表

给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。

这个题目可以使用双哑点指针解决。

参考代码如下，这里需要注意的是，因为涉及到节点的拼接，所以要避免陷入死循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ListNode* partition(ListNode* head, int x) {
    if(head == NULL)
        return NULL;
    
    ListNode* little = new ListNode(0);
    ListNode* big = new ListNode(0);
    ListNode* node1 = little;
    ListNode* node2 = big;

    while(head) {
        if(head->val < x) {
            node1->next = head;
            node1 = node1->next;
        }
        else {
            node2->next = head;
            node2 = node2->next;
        }
        head = head->next;
    }
    node2->next = NULL;  // 避免返回结果的时候陷入死循环
    node1->next = big->next;
    return little->next;
}

148. 排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

题目要求时间空间复杂度分别为$O(nlogn)$和$O(1)$，根据时间复杂度我们自然想到二分法，从而联想到归并排序（快速排序平均时间复杂度为$O(nlogn)$ ）；对数组进行归并排序的空间复杂度为$O(n)$，分别由新开辟数组$O(n)$和递归函数调用$O(logn)$组成，而根据链表特性：

  1. 数组额外空间：链表可以通过修改引用来更改节点顺序，无需像数组一样开辟额外空间
  2. 递归额外空间：递归调用函数将带来$O(logn)$的空间复杂度，若希望达到$O(1)$空间复杂度，则不能使用递归

为了方便理解，先阐述一下基于递归方法的思路：

分割环节：找到当前链表中点，并从中点将链表断开

  • 使用 fast,slow 快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的节点。
  • 找到中点 slow 后，执行 slow.next = None 将链表切断。
  • 递归分割时，输入当前链表左端点 head 和中心节点 slow 的下一个节点 tmp(因为链表是从 slow 切断的)。
  • cut 递归终止条件： 当head.next == None时，说明只有一个节点了，直接返回此节点。

合并环节：将两个排序链表合并，转化为一个排序链表。

  • 双指针法合并，建立辅助ListNode h 作为头部。
  • 设置两指针 left, right 分别指向两链表头部，比较两指针处节点值大小，由小到大加入合并链表头部，指针交替前进，直至添加完两个链表。
  • 返回辅助ListNode h 作为头部的下个节点 h.next。
  • 时间复杂度 O(l + r)，l, r 分别代表两个链表长度。

当题目输入的 head == None 时，直接返回None。

示意图如下：

Picture2.png

接下来阐述一下基于循环的方式，也就是从底至顶直接合并。需要使用迭代的方式替换上述分割环节，该环节本质上是通过二分法得到链表最小节点单元，再通过多轮合并得到排序结果。

每一轮合并merge操作针对的单元都有固定长度intv，例如：

  • 第一轮合并时intv = 1，即将整个链表切分为多个长度为1的单元，并按顺序两两排序合并，合并完成的已排序单元长度为2。
  • 第二轮合并时intv = 2，即将整个链表切分为多个长度为2的单元，并按顺序两两排序合并，合并完成已排序单元长度为4。
  • 以此类推，直到单元长度intv >= 链表长度，代表已经排序完成。

根据以上推论，我们可以仅根据intv计算每个单元边界，并完成链表的每轮排序合并，例如:

  • 当intv = 1时，将链表第1和第2节点排序合并，第3和第4节点排序合并，……。
  • 当intv = 2时，将链表第1-2和第3-4节点排序合并，第5-6和第7-8节点排序合并，……。
  • 当intv = 4时，将链表第1-4和第5-8节点排序合并，第9-12和第13-16节点排序合并，……。

此方法时间复杂度$O(nlogn)$，空间复杂度$O(1)$。

Picture1.png

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
ListNode* sortList(ListNode* head) {
    ListNode* node = head;

    // 统计链表的长度
    int length = 0;
    while(node) {
        length++;
        node = node->next;
    }

    ListNode* res = new ListNode(0);  // 设置哑点
    res->next = head;

    // 当前每个组别的长度
    int intv = 1;
    while(intv < length) {
        // h用于遍历，注意这次每次都需要这样的初始化，res每次也会更新，其next指向排序后的第一个指针
        ListNode* pre = res;
        ListNode* h = res->next;

        // 两两一组的遍历各个小块，当h为空的时候，加大intv
        while(h) {
            // h1是第一个块的开头，h2是第二个块的开头
            ListNode* h1 = h;
            // 向前移动intv个，得到第二个块的开头h
            int i = intv;
            while(i>0 && h) {
                h = h->next;
                i--;
            }
            if(i>0) 
                break; // 此时第二个块没有值，也就可以删除了
        
            i = intv;
            ListNode* h2 = h;
            // 得到第三个块的开始坐标h，方便接下来的循环
            while(i>0 && h) {
                h = h->next;
                i--;
            }

            // 开始进行合并，注意这里循环的时候不能够使用h1和h2，因为并没有截断
            int c1 = intv;
            int c2 = intv - i; // c2的长度可能比intv短
            while(c1>0 && c2>0) {
                if(h1->val < h2->val) {
                    pre->next = h1;
                    h1 = h1->next;
                    c1--;
                }
                else {
                    pre->next = h2;
                    h2 = h2->next;
                    c2--;
                }
                pre = pre->next;
            }

            // 如果有一方有剩余
            if(c1>0) 
                pre->next = h1;
            else if(c2>0) 
                pre->next = h2;
            
            // 排序好的链表末尾指针pre的next指向第三块的开始坐标
            while(c1>0 || c2>0) {  
                pre = pre->next;
                c1--;
                c2--;
            }
            pre->next = h;
        }
        intv *= 2;
    }
    return res->next;
}

143. 重排链表

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

这个题目根据一头一尾取元素的特性。可以分为三个步骤：

  1. 将链表平均分为两半，并从中间截断，防止陷入死循环
  2. 将第二个链表逆序
  3. 依次连接两个链表

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void reorderList(ListNode* head) {
    if(head == nullptr)
        return;
    
    ListNode* slow = head;  // slow指向的是中间元素
    ListNode* fast = head->next;
    while(fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    ListNode* mid = slow->next;  // mid指向第二个链表的首元素
    slow->next = nullptr; // 进行截断，防止陷入死循环
    
    // 旋转后面的链表，最终pre指向旋转后首元素
    ListNode* pre = nullptr; // 这个初始化需要注意
    while(mid) {
        ListNode* third = mid->next;
        mid->next = pre;
        pre = mid;
        mid = third;
    }

    // 开始进行拼接操作
    ListNode* node = head;
    while(pre) {
        ListNode* third = node->next;
        node->next = pre;
        pre = pre->next;
        node->next->next = third;
        node = third;
    }
}

141. 环形链表

给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。如果链表中存在环，则返回 true 。 否则，返回 false 。请尝试使用 O(1)（即，常量）内存解决此问题。

这个题目可以使用快慢指针的方法，若链表中存在环，则快慢指针肯定存在相等的情况，否则的话肯定不存在环。

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool hasCycle(ListNode *head) {
    if(head == NULL)
        return false;
    
    ListNode* slow = head;
    ListNode* fast = head->next;  // 访问肯定不会报错，但是不是NULL就不一定了
    while(fast!=slow) {
        slow = slow->next;
        
        if(fast == NULL || fast->next == NULL) // 肯定不存在环了
            return  false;
        else
            fast = fast->next->next;
    }
    return true;
}

142. 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。说明：不允许修改给定的链表。

这个题目和上一个题目的区别在于本题目不仅要判断是不是有环，而且要得到入环的第一个节点。

阶段一：判断存在环；阶段二：找到环的入口，下面对第二个阶段进行讨论。

当环很大的时候，这个过程用示意图表示如下图所示。其实这个结论对于环很小的时候也适用。

未命名文件.png

为了更加严谨的证明这个结论，我们不对环的大小进行限制进行讨论。

  1. 假设链表共有 a+b 个节点，其中 链表头部到链表入口 有 a 个节点（不计链表入口节点）， 链表环 有 b 个节点。设快慢指针分别走了$f,s$步，则在两个指针第一次相遇有：
    • fast指针走的是slow步数的两倍，即$f=2s$
    • fast比slow多走了$n$个环的长度，即$f=s+nb$；（ 双指针都走过 a 步，然后在环内绕圈直到重合，重合时 fast 比 slow 多走 环的长度整数倍 ）
    • 以上两式相减得：$f=2nb,s=nb$，即fast和slow 指针分别走了 2n，n 个 环的周长 （注意： n 是未知数，不同链表的情况不同）
  2. 此时，若让指针从链表头部一直向前走并统计步数$k$，那么所有走到链表入口节点时的步数是：$k=a+nb$（先走 $a$ 步到入口节点，之后每绕 1 圈环（ $b$ 步）都会再次到入口节点）。而目前slow指针已经走了$nb$步了，只需要再走$a$步停下来即为环的入口。但是此时不知道$a$的值，所以仍然使用双指针法，让另外一个指针从链表头部出发，与slow一起向前走$a$步后，两者在入口节点重合。

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ListNode *detectCycle(ListNode *head) {
    ListNode *pre=head, *post=head;
    while(true) {
        if(post==NULL || post->next==NULL) return NULL;  // 肯定不存在环
        pre = pre->next;
        post = post->next->next;
        if(pre == post)  // 第一次相遇停止
            break;
    }

    pre = head;
    while(pre != post) {  // 再次相遇停止
        pre = pre->next;
        post = post->next;
    }
    return pre;
}

234. 回文链表

请判断一个链表是否为回文链表。你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

若想使用$O(1)$的空间复杂度解决这个题目，可以使用快慢指针遍历的同时翻转前半部分，然后与后半部分比较即可。这个技巧也经常被其他题目使用。

值得注意的是，这里将fast和slow指针都初始化为了head，若将fast初始化为head->next，则当链表有偶数个元素的时候，最后一个中位数没办法处理到。参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
bool isPalindrome(ListNode* head) {
    if(head == NULL)
        return true;
    ListNode* prepre=NULL, *pre=head;  // pre指针指向前半部分翻转后的首地址
    ListNode* slow=head, *fast=head;
    while(fast && fast->next) {  // 快慢指针遍历的同时翻转前半部分
        pre = slow;
        slow = slow->next;
        fast = fast->next->next;
        pre->next = prepre;    
        prepre = pre;
    }
    if(fast)  // 说明链表元素有奇数个，此时slow在中位数上，需要向后移动一位；若链表元素为偶数个，slow在后半段的开头位置
        slow = slow->next;

    while(pre!=NULL && slow!=NULL) {
        if(pre->val != slow->val)
            return false;
        pre = pre->next;
        slow = slow->next;
    }
    return true;
}

138. 复制带随机指针的链表

给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的 深拷贝。

我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

  • val：一个表示 Node.val 的整数。
  • random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

该题主要有两个思路。

第一个思路是不借助外部存储空间，使用三步走的方法。

第一步，根据遍历到的原节点创建对应的新节点，每个新创建的节点是在原节点后面，比如下图中原节点1不再指向原原节点2，而是指向新节点1

5.jpg

第二步是最关键的一步，用来设置新链表的随机指针

6.jpg

此时可以观察到一个规律，原节点i的随机指针(如果有的话)，指向的是原节点j。那么新节点i的随机指针，指向的是原节点j的next。

第三步就简单了，只要将两个链表分离开，再返回新链表就可以了

7.jpg

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
Node* copyRandomList(Node* head) {
    if(head == NULL)
        return NULL;
    
    Node* node = head;
    // 开始复制
    while(node) {
        Node* newNode = new Node(node->val);
        newNode->next = node->next;
        node->next = newNode;
        node = newNode->next;
    }

    // 开始复制随机指针
    node = head;
    while(node) {
        if(node->random)
            node->next->random = node->random->next;
        node = node->next->next;
    }

    // 开始拆分链表，借助哑点让newNode在node的前面，可以简化代码，不需要对newNode->next是否为空进行特殊判断了
    Node* newHead = new Node(-1);
    Node* newNode = newHead;
    node = head;
    while(node) {
        newNode->next = node->next;
        newNode = newNode->next;
        node->next = newNode->next;
        node = node->next;
    }
    return newHead->next;
}

第二个解法是借助额外存储空间，也就是借助哈希表来解决这个问题。

首先创建一个哈希表，再遍历原链表，遍历的同时再不断创建新节点。我们将原节点作为key，新节点作为value放入哈希表中。

8.jpg

第二步我们再遍历原链表，这次我们要将新链表的next和random指针给设置上。

参考代码如下，我这里将next指针的设置放在了第一个循环中，这个位置其实无所谓。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Node* copyRandomList(Node* head) {
    if(head == NULL)
        return NULL;
    
    unordered_map<Node*, Node*> um;
    Node* newHead = new Node(head->val);
    um[head] = newHead;
    Node* pre2 = newHead;
    Node* cur1 = head->next;
    while(cur1) {
        Node* newNode = new Node(cur1->val);
        um[cur1] = newNode;
        pre2->next = newNode;
        cur1 = cur1->next;
        pre2 = pre2->next;
    }

    cur1 = head;
    Node* cur2 = newHead;
    while(cur1) {
        cur2->random = um[cur1->random];
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    return newHead;
}

参考

Java-双指针-头插法
Sort List （归并排序链表）
详细图解(肯定看的明白)
环形链表 II（双指针法，清晰图解）
回文链表（1.栈，2.快慢指针+翻转）
两种实现+图解 138. 复制带随机指针的链表

数组

在处理数组和链表相关问题时，双指针技巧是经常用到的，双指针技巧主要分为两类：左右指针和快慢指针。

所谓左右指针，就是两个指针相向而行或者相背而行；而所谓快慢指针，就是两个指针同向而行，一快一慢。

对于单链表来说，大部分技巧都属于快慢指针。没有真正意义上的指针，但我们可以把索引当做数组中的指针，这样也可以在数组中施展双指针技巧

栈和队列

理论

  1. 栈的特点是后入先出。根据这个特点可以临时保存一些数据，之后用到依次再弹出来，常用于 DFS 深度搜索。
  2. 队列一般用于BFS广度搜索，类似一层一层的搜索。

栈常见题目

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

  • push(x) —— 将元素 x 推入栈中。
  • pop() —— 删除栈顶的元素。
  • top() —— 获取栈顶元素。
  • getMin() —— 检索栈中的最小元素。

这个题目要在常数时间内检索到最小元素，那么可以借助额外的一个栈保存当前最小元素。其中push函数比较特殊，这里给出其实现，其余的均不给出了。

1
2
3
4
5
6
7
8
stack<int> s;
vector<int> vec{INT_MAX};

void push(int x) {
    s.push(x);
    // 注意这个必须每次和top比较，不能拿个全局值
    vec.push_back(min(vec.back(), x));
}

150. 逆波兰表达式求值

根据 逆波兰表示法，求表达式的值。有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。说明：

  • 整数除法只保留整数部分。
  • 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) ( 3 + 4 ) 。该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) ) 。

我们一般看到的都是中缀表达式，但这对于计算机来说就很不友好了。例如$4+13/5$，计算机从左到右扫描的话，扫到13还要判断13以后是什么运算符，还要比较优先级。是比较麻烦的。但是转换为中缀表达式之后，即为["4", "13", "5", "/", "+"]，计算机可以按照栈里面的顺序处理，不需要考虑优先级，也不需要后退了。

对于本题的解决思路为：

  1. 定义一个栈辅助计算；
  2. 当遇到运算符”+”、”-“、”*”、”/“时，从栈中pop出两个数字计算，运算结果入栈；否则将数字入栈。

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int evalRPN(vector<string>& tokens) {
    if(tokens.empty())
        return 0;
    
    vector<int> vec;
    for(int i=0; i<tokens.size(); i++) {
        string c = tokens[i];
        if(c=="+" || c=="-" || c=="*" || c=="/") {
            // 弹出最前面两个元素
            int first = vec.back();
            vec.pop_back();
            int two = vec.back();
            vec.pop_back();
            if(c == "+") vec.push_back(two+first);
            else if(c == "-") vec.push_back(two-first);
            else if(c == "*") vec.push_back(two*first);
            else if(c == "/") vec.push_back(two/first);
        }
        else {
            vec.push_back(atoi(c.c_str()));
        }
    }
    return vec.back();
}

394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

本题难点在于括号内嵌套括号，需要从内向外生成与拼接字符串，这与栈的先入后出特性对应。

构建辅助栈stack，遍历字符串s中每个字符c：

  • 当c为数字时，将数字字符转化为数字multi，用于后续倍数计算
  • 当c为字母时，在res尾部添加c
  • 当 c 为[ 时，将当前 multi 和 res 入栈，并分别置空置 0：
    • 记录此 [ 前的临时结果 res 至栈，用于发现对应 ] 后的拼接操作；
    • 记录此 [ 前的倍数 multi 至栈，用于发现对应 ] 后，获取 multi × [...]字符串。
    • 进入到新 [ 后，res 和 multi 重新记录
  • 当 c 为 ] 时，stack 出栈，拼接字符串 res = last_res + cur_multi * res，其中:
    • last_res是上个 [ 到当前 [ 的字符串，例如 "3[a2[c]]" 中的 c；
    • cur_multi是当前 [ 到 ] 内字符串的重复倍数，例如"3[a2[c]]" 中的 2。

返回字符串res。

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
string decodeString(string s) {
    stack<pair<int, string>> sta;
    int num = 0;
    string res;
    for(int i=0; i<s.size(); i++) {
        char c = s[i];
        if(isdigit(c)) {
            num *= 10;
            num += c - '0';
        }
        else if(c == '[') {  //遇到[压栈数字和字符串，置零置空
            sta.push(make_pair(num, res));
            num = 0;
            res = "";
        }
        else if(c == ']') {  //遇到]出栈数字和字符串，组装
            int n = sta.top().first;  //n指示的是res的循环次数，不是a的
            string a = sta.top().second;
            sta.pop();
            for(int i=0; i<n; i++) // 将a拼接到n次res前面
                a = a + res;
            res = a;  // 更新当前的已有字符
        }
        else {
            res += s[i];
        }
    }
    return res;
}

133. 克隆图

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

1
2
3
4
5
> class Node {
>     public int val;
>     public List<Node> neighbors;
> }
>

这个题目明显是深度优先遍历的题目。深度优先遍历有三个关键点：

  1. 遍历路径：假设目前所在的节点为node，则由该点向此点的邻居节点做深度搜索
  2. 遍历终止条件：若节点node==NULL，则返回NULL；若出现在哈希表中，则已经遍历过了，返回对应的新节点
  3. 如何避免重复遍历：在遍历的同时，使用一个哈希表记录原始节点和新节点的对应关系，这样若访问过了，直接返回对应的新节点即可
1
2
3
4
5
6
7
8
9
10
11
12
13
unordered_map<Node*, Node*> mp; // 声明在外面
Node* cloneGraph(Node* node) {
    if(node == NULL)
        return NULL;
    
    if (mp.count(node)) return mp[node]; // 如果已经访问过了，则直接从哈希表中取出对应的克隆节点返回
    const auto new_root = new Node(node->val); // 克隆节点，注意到为了深拷贝我们不会克隆它的邻居的列表
    mp[node] = new_root;  // 哈希表存储
    for (const auto&e : node->neighbors) { // 遍历该节点的邻居并更新克隆节点的邻居列表
        mp[node]->neighbors.push_back(cloneGraph(e));
    }
    return mp[node];
}

200. 岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。

该题目也是典型的深度优先遍历题目。

深度优先遍历有如下三个关键点：

  1. 遍历路径：假设目前指针在岛屿中的(i,j)点，那么由该点向此点的上下左右 (i+1,j),(i-1,j),(i,j+1),(i,j-1) 做深度搜索。
  2. 遍历终止条件：(i,j)越过矩阵边界；grid[i][j] == '2'代表此分支已经越过岛屿边界
  3. 如何避免重复遍历：搜索岛屿的同时，执行 grid[i][j] = '2'，即将岛屿所有节点删除，以免之后重复搜索相同岛屿。

主循环（深度优先遍历不一定都对这个分析，因为本题在DFS的时候，会中断掉，所以需要分析）：遍历整个矩阵，当遇到grid[i][j] == '1' 时，从此点开始做深度优先搜索 dfs，岛屿数 count + 1 且在深度优先搜索中删除此岛屿。

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void infect(vector<vector<char>>& grid, int i, int j) {
    if(i<0 || j<0 || i>=grid.size() || j>=grid[0].size()|| grid[i][j] != '1')
        return;

    grid[i][j] = '2';
    infect(grid, i-1, j);
    infect(grid, i+1, j);
    infect(grid, i, j-1);
    infect(grid, i, j+1);
}

int numIslands(vector<vector<char>>& grid) {
    int nums = 0;
    for(int i=0; i<grid.size(); i++) {
        for(int j=0; j<grid[0].size(); j++) {
            if(grid[i][j] == '1') {
                infect(grid, i, j);                
                nums++;
            }
        }
    }
    return nums;
}

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

这个题目是典型的单调栈题目。单调栈分为单调递增栈和单调递减栈：

  1. 单调递增栈，即栈中的元素都是单调不递减的。
    • 若新元素大于等于栈顶元素，则入栈
    • 若新元素小于栈顶元素，则不断弹栈，直到新元素大于等于栈顶元素，将新元素入栈
  2. 单调递减栈，即栈中的元素都是单调不递增的。
    • 若新元素小于等于栈顶元素，则入栈
    • 若新元素大于栈顶元素，则不断弹栈，直到新元素小于等于栈顶元素，将新元素入栈

解决本问题需要借助单调递增栈+哨兵技巧。具体思路为：

首先，在栈中记录高度是不可以的，因为计算矩阵还需要计算宽度，而宽度是需要是由下标确定的。记录下标也可以从数组中得到对应的高度。因此应该记录的是下标。

其次，考虑找到第i个位置最大面积。是以i为中心，向左找第一个小于heights[i]的位置left_i；向右找第一个小于于heights[i]的位置right_i，那么对应的宽度为right_i - left_i -1，即最大面积为heights[i] * (right_i - left_i -1)，如下图所示：

1559826097853.png

这样的一个要求与单调递增栈的性质不谋而合。考虑新元素比栈顶元素严格小的情况，此时需要出栈

  1. 新元素是出栈元素向后找第一个比其小的元素
  2. 新栈顶元素是出栈元素向前找第一个比其小的元素

最后，这里需要借助哨兵技巧，这是因为：

  1. 若输入是递增的话，则代码无法弹出计算面积，需要在heights数组后面加上一个0，这样就可以强迫栈内元素出栈计算面积了
  2. 考虑首元素计算时需要知道左边第一个小于它的元素位置，所以在heights数组前面加上一个0

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int largestRectangleArea(vector<int>& heights) {
    stack<int> sta;
    int ans = 0;
    // 添加哨兵
    heights.insert(heights.begin(), 0);
    heights.push_back(0);
    for(int i=0; i<heights.size(); i++) {
        // 注意这个判断要用while，如果要用top必须让sta不等于空
        while(!sta.empty() && heights[sta.top()]>heights[i]) {
            int num = heights[sta.top()];
            sta.pop();

            // i表示向后找第一个比其小的元素下标，sta.top()表示向前找第一个比其小的元素
            ans = max(ans, (i-sta.top()-1)*num);
        }
        sta.push(i);
    }
    return ans;
}

队列常见题目

232. 用栈实现队列

使用栈实现队列的下列操作：

  • push(x) — 将一个元素放入队列的尾部。
  • pop() — 从队列首部移除元素。
  • peek() — 返回队列首部的元素。
  • empty() — 返回队列是否为空。

使用两个栈，一个栈（stackPush）用于元素进栈，一个栈（stackPop）用于元素出栈；

push的时候，直接push到stackPush栈中

pop() 或者 peek() 的时候：

（1）如果 stackPop 里面有元素，直接从 stackPop 里弹出或者 peek 元素；

（2）如果 stackPop 里面没有元素，一次性将 stackPush 里面的所有元素倒入 stackPop。

为此，可以写一个 shift 辅助方法，一次性将 stackPush 里的元素倒入 stackPop。

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
stack<int> stackPush;
stack<int> stackPop;

void push(int x) {
    stackPush.push(x);
}   

void shift() {
    if(stackPop.empty()) {  // 只有当stackPop为空的时候，才会执行下面的转移操作
        while(!stackPush.empty()) {
            stackPop.push(stackPush.top());
            stackPush.pop();
        }
    }
}

int pop() {
    shift();
    int val = stackPop.top();
    stackPop.pop();
    return val;
}

int peek() {
    shift();
    return stackPop.top();
}

bool empty() {
    return stackPop.empty() && stackPush.empty();
}

542. 01 矩阵

给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。两个相邻元素间的距离为 1 。

广度优先搜索大概可以分为两种：

  1. 对于「Tree 的 BFS」 （典型的「单源 BFS」）：首先把 root 节点入队，再一层一层遍历
  2. 对于「图 的 BFS」 （「多源 BFS」） 其实也是一样的，不过需要注意以下两点：
    • Tree 只有 1 个 root，而图可以有多个源点，所以首先需要把多个源点都入队；
    • Tree 是有向的因此不需要标识是否访问过，而对于无向图来说，必须得标志是否访问过。并且为了防止某个节点多次入队，需要在其入队之前就将其设置成已访问！

那么对于本题而言，可以借助广度优先搜索完成，具体思路是首先将每个源点 0 入队，然后从各个 0 同时开始一圈一圈的向 1 扩散（每个 1 都是被离它最近的 0 扩散到的 ）。扩散的时候可以实时更新矩阵元素的值来几记录距离（即扩散的层次）并同时标志是否访问过。这里需要注意的是，需要首先将所有非 0 的元素统一设置为-1这个无效距离值来标记这个位置的1没有访问过。

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
    int rows = matrix.size();
    int cols = matrix[0].size();

    queue<pair<int, int>> q;
    // 先将所有的零入列
    for(int i=0; i<rows; i++) {
        for(int j=0; j<cols; j++) {
            if(matrix[i][j] == 0)
                q.push(make_pair(i, j));
            else 
                matrix[i][j] = -1; // 表明没有被访问过
        }
    }

    vector<int> dx{-1, 1, 0, 0};
    vector<int> dy{0, 0, -1, 1};
    // 开始由零一圈一圈的向外扩散
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        for(int k=0; k<4; k++) {
            int i = x + dx[k];
            int j = y + dy[k];
            if(i>=0 && i<rows && j>=0 && j<cols && matrix[i][j]==-1) {
                matrix[i][j] = matrix[x][y] + 1;
                q.push(make_pair(i, j));
            }
        }
    }
    return matrix;
}

参考

150. 逆波兰表达式求值:【栈的经典应用】详解
Java 易懂,易解,效率高
字符串解码（辅助栈法 / 递归法，清晰图解）
克隆图
200. 岛屿数量（DFS / BFS）
暴力解法、栈（单调栈、哨兵技巧）
找两边第一个小于它的值
【柱状图中最大的矩形】单调栈入门，使用单调栈快速寻找边界
负负得正，使用两个栈，一个专门入队，一个专门出队
2种BFS，详解DP， 🤷‍♀️必须秒懂！

二进制

规律

  1. 移除最后一个1：a = n&(n-1);

  2. 获取最右端的一个1：a = n&(-n);

  3. 异或满足交换律且两个相同元素异或结果为0：a=a^b^b=b^a^b;

  4. 整数的二进制编码：

    • 正数的编码为原码，如8的二进制编码为：00001000
    • 负数的编码为最高位为1，其余位等于原码取反加1，如-8的二进制编码为：1…1111000

  5. 两个数交换：

    1
    2
    3
    a = a^b
    b = a^b
    a = a^b

  6. ^：相当于无进位的求和；&相当于求每位的进位数。

常见题目

136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

这个题目比较简单，使用到了上面的规律3。参考代码如下：

1
2
3
4
5
6
7
int singleNumber(vector<int>& nums) {
    int num = 0;
    for(int i=0; i<nums.size(); i++) {
        num ^= nums[i];
    }
    return num;
}

137. 只出现一次的数字 II

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

最简单的思路是统计数组元素二进制表达中每个位置1出现的次数。若某个位置1出现的次数不能被3整除，则说明目标元素的该位置为1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int singleNumber(vector<int>& nums) {
    vector<int> dp(32, 0);
    for(auto &num: nums) {
        unsigned int mask = 1;
        for(int j=31; j>=0; j--) {
            if(num&mask == 1) {
                dp[j]++;
            }
            num = num>>1;
        }
    }

    int res = 0;
    for(int i=0; i<32; i++) {
        res = res<<1;
        res += dp[i]%3;
    }
    return res;
}

另外一种思路是使用位运算符的性质。

XOR异或运算符可以用来检测出现奇数次的位：0与任何数异或均为该数，而两个相同数异或结果为0。

以此类推，只有某个位置的数字出现奇数次时，该位的掩码才不为 0。

img

因此，可以检测出出现一次的位和出现三次的位，但是要区分这两种情况。这个时候需要借助AND和NOT运算：为了区分出现一次的数字和出现三次的数字，使用两个位掩码：seen_once 和 seen_twice。思路是：

  • 仅当 seen_twice 未变时，改变 seen_once。

  • 仅当 seen_once 未变时，改变seen_twice。

可以看到，位掩码 seen_once 仅保留出现一次的数字，不保留出现三次的数字。

img

对应的代码为：

1
2
3
4
5
6
7
8
int singleNumber(vector<int>& nums) {
    int seenOnce = 0, seenTwice = 0;
    for(auto num:nums) {
        seenOnce = ~seenTwice & (seenOnce ^ num);
        seenTwice = ~seenOnce & (seenTwice ^ num);
    }
    return seenOnce;
}

260. 只出现一次的数字 III

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

由异或性质可得，若将所有的数字进行异或，最终结果为只出现一次的那两个元素异或的结果。接下来考察其的某个非0位（比如最低非0位），那么只出现一次的两个数中，在这个位上一个为0，一个为1。由此可以将数组中的元素分成两部分，重新遍历，求两个异或值。参

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> singleNumber(vector<int>& nums) {
    int mask = 0;
    for(auto num:nums) {
        mask ^= num;
    }
    
    int index = mask & (-mask);   // 得到最右端的1
    
    int num1=0, num2=0;
    for(auto num:nums) {
        if(num&index)
            num1 ^= num;
        else
            num2 ^= num;
    }
    vector<int> vec{num1, num2};
    return vec;
}

191. 位1的个数

编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

该题考察的是上面的性质1。具体来说，每次都将最后一个1变成0，然后结果加1。代码如下：

1
2
3
4
5
6
7
8
int hammingWeight(uint32_t n) {
    int num = 0;
    while(n>0) {
        num++;
        n = n&(n-1);   // 将最后一个为1变成0
    }
    return num;
}

338. 比特位计数

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

这个题目可以使用动态规划来做。对于所有的数字，只有两类：

  1. 奇数：二进制表示中，奇数一定比前面的那个偶数多一个1，因为多的就是最低位的 1

    1
    2
    3
    举例： 
    0 = 0       1 = 1
    2 = 10      3 = 11

  2. 偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。因为最低位是 0，除以 2 就是右移一位，也就是把那个 0 抹掉而已，所以 1 的个数是不变的。

    1
    2
    3
    举例：
    2 = 10       4 = 100       8 = 1000
    3 = 11       6 = 110       12 = 1100

另外，0 的 1 个数为 0，于是就可以根据奇偶性开始遍历计算了。

1
2
3
4
5
6
7
8
9
10
11
vector<int> countBits(int num) {
    vector<int> result;
    result.push_back(0);
    for(int i=1; i<=num; i++) {
        if(i%2==1)   // 奇数
            result.push_back(result[i-1]+1);
        else
            result.push_back(result[i>>1]);
    }
    return result;
}

190. 颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。比如输入00000010100101000001111010011100，输出00111001011110000010100101000000。

依次颠倒即可。

1
2
3
4
5
6
7
8
9
10
uint32_t reverseBits(uint32_t n) {
    int ans = 0;
    int i = 32;
    while(i--) {
        ans = ans<<1;
        ans += n&1;
        n = n>>1;   // 右移一位
    }
    return ans;
}

201. 数字范围按位与

给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。

按位相与的结果可以概括为：两个位的值都为1，按位与的结果才为 1，否则必为 0。可以得到两个结论：

  1. 多个数字按位与，其结果中值为 1 的位绝对不会增加，只有可能减少。
  2. 多个数字按位与，其结果中值为 1 的位，在多个数字中的对应位必然也为 1。

因题目传参用了有符号整型（实际上都是大于0的），忽略符号位后，还剩31位。从高位到低位依次编号为 0, 1, 2, 3, … 29, 30。首先来寻找一下n和m的二进制最长相同前缀，设这个前缀长度为x。因为加法只会影响连续的低位，所以 [n,m] 中的所有数字的长度为 x 的二进制前缀都是相等的。那也就导致，按位与的结果的长度x的二进制前缀也相同。

因为n和m的最长相同前缀长度为 x，此时 x 有两种情况：

  1. x = 31。即 n 和 m 完全相等。这种情况没啥好说的，答案就是 n&m。这种情况太简单了，不做讨论。
  2. 0 <= x < 31。因为 n >= m，所以 m 的第 x 位必然为 0，而 n 的第 x 为必然为 1。(不然就成 m >= n 了)

从 n 的后缀 0abcd… 累加到 m 的后缀 1hijk… 这个过程中，不管abcd…，hijk… 取值如何，必然要经过 10000…。0abcd… 和 10000… 使得答案中长度为 31-x 的后缀必然都为 0。

例如n 和 m 的二进制及最长前缀如下图所示，后缀 011 累加到 110 必然经过 100。011 和 100 保证了答案中长度为 3 的后缀必然均为 0。

image.png

所以对应的代码为：

1
2
3
4
5
6
7
8
9
int rangeBitwiseAnd(int m, int n) {
    int mask = 1 << 30; // 最高位开始
    int anw = 0;
    while(mask > 0 && (m&mask) == (n&mask)) { //寻找相同前缀
        anw |= m&mask;  // 将该位的结果使用或运算更新到anw的对应位置
        mask >>= 1;  // 判断下一个低位
    }
    return anw;
}

1371. 每个元音包含偶数次的最长子字符串

给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 ‘a’，’e’，’i’，’o’，’u’ ，在子字符串中都恰好出现了偶数次。

这道题目如果采用暴力方法，肯定能够做出来，但是肯定会超时。如果采用滑窗的方法，那么何时收缩窗口，难以确定。所以该题目其实考察的是前缀和和位运算。

我们知道，一个数加上偶数不改变奇偶性，例如奇数+偶数=奇数，偶数+偶数=偶数。那么如果子串[0,i]奇偶性和[0,j]相同，那么子串[i+1,j]一定偶数。

只考虑每个元音的奇偶次数，可以用二进制进行记录：定义aeiou 分别对应二进制 00001，00010，00100，01000，10000。其中 0 表示对应元音出现了偶数次数，1 表示奇数。

从左到右遍历字符串，不断更新dp：dp[pattern] 的作用是用来记录当前索引值下对应的元音奇偶次数组合特征。例如：如果 pattern 为 10，也就是对应二进制01010，dp[pattern] = 8的意思为，当索引值为 8 的时候，e 和 o 都出现了奇数次，其它元音为偶数次。

根据异或运算规律，异或本身为 0，所以当重复出现偶数次，对应位变为 0，否则为 1。由这个规律可以断定，当再次出现这个 pattern 的时候，一定出现了偶数次。例如pattern 的值变化为 31-->30-->28-->29-->31，对应的二进制位 [11111]-->[11110]-->[11100]-->[11101]-->[11111]，此时对应的一个合理字符串变化为aeiou —> aeioua —>aeiouae—>aeiouaea—>aeiouaeae。由此可见，从 aeiou 到 aeiouaeae 这个过程中，多余出来的 aeae 为符合条件的字符串。

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int findTheLongestSubstring(string s) {
    int ans = 0, pattern = 0, n = s.length();
    vector<int> pos(1 << 5, -1);
    pos[0] = 0;
    for (int i = 0; i < n; ++i) {
        if (s[i] == 'a') {
            pattern ^= 1<<0;
        } else if (s[i] == 'e') {
            pattern ^= 1<<1;
        } else if (s[i] == 'i') {
            pattern ^= 1<<2;
        } else if (s[i] == 'o') {
            pattern ^= 1<<3;
        } else if (s[i] == 'u') {
            pattern ^= 1<<4;
        }
        if (~pos[pattern]) {
            ans = max(ans, i + 1 - pos[pattern]);
        } else {
            pos[pattern] = i + 1;
        }
    }
    return ans;
}

参考

只出现一次的数字 II
巨好理解的位运算思路
【leetcode】5337. 每个元音包含偶数次的最长子字符串( Find the Longest Substring Containing Vowels in Even Counts)
小学生解释

二分查找

二分查找常见问题

适用情况：给一个有序数组和目标值，找到第一个/最后一个/任何一次出现的索引，如果没有返回-1。时间复杂度$O(logn)$。

二分查找并不简单，Knuth 大佬（发明 KMP 算法的那位）都说二分查找：思路很简单，细节是魔鬼。很多人喜欢拿整型溢出的 bug 说事儿，但是二分查找真正的坑根本就不是那个细节问题，而是在于到底要给 mid 加一还是减一，while 里到底用 <= 还是 <。个人总结需要注意一下几点：

  1. 是否会出现数组越界，以及是否会出现遗漏情况

  2. 是否会while死循环，尤其是当更新条件为left = mid或者right = mid时，一般来说，前者需要搭配int mid = left + (right-left+1)/2;，后者需要int mid = left + (right-left)/2;使用。

  3. 是否覆盖了数组为空的情况

为了更好的理解这三点细节，我们通过如下三个函数进行说明，可通过下面几道典型题目进行总结练习：

704. 二分查找

34. 在排序数组中查找元素的第一个和最后一个位置

这几个函数只是为了更好的理解这里的问题，尤其是上述第2点，但是感觉细节不是很好记。所以强烈建议如果不拘泥于细节的话，直接看下一节二分查找模板。

另外提前说明一下，计算 mid 时需要防止溢出，代码中 left + (right - left) / 2 就和 (left + right) / 2 的结果相同，但是有效防止了 left 和 right 太大，直接相加导致溢出的情况。

函数一：在排序数组中查找目标元素任何一次出现的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
int search(vector<int>& nums, int target) {
    int mid, left = 0, right = nums.size() - 1;
    while (left <= right) {
        mid = left + (right - left) / 2;
        if (nums[mid] == target) 
            return mid;
        if (target < nums[mid]) 
            right = mid - 1;
        else 
            left = mid + 1;
    }
    return -1;
}

下面我们分析我们上述说的几点。

  1. 数组是否会越界，以及是否会出现遗漏情况：这里的搜索区间为[left, right]闭区间，left最小为0，right最大为nums.size() - 1，所以搜索区间最大为[0, nums.size() - 1]，所以不会出现数组越界；终止条件为left = right+1，会遍历的区间为[0, nums.size())，所以不会出现遗漏的情况。
  2. 是否会出现死循环：出现死循环是因为若出现mid = left(mid = right)，同时更新的时候触发了left = mid(right = mid)。而该代码中更新条件为right = mid - 1以及left = mid + 1，所以不会出现死循环。
  3. 是否覆盖了数组为空的情况：数组为空的时候，right = -1，不会进入循环，会正确的返回-1。

函数二：在排序数组中查找目标元素的第一个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int findFirst(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;

    while(left < right) {
        int mid = left + (right-left)/2;

        if(nums[mid] < target)
            left = mid + 1;
        else
            right = mid;
    }
    if(nums.size()<=0 || nums[left] != target)
        return -1;
    return left;
}

下面我们分析我们上述说的几点。

  1. 数组是否会越界，以及是否会出现遗漏情况：这里的搜索区间为[left, right)左闭右开区间，left最小为0，right最大为nums.size() - 1，所以搜索区间最大为[0, nums.size() - 1)，所以不会出现数组越界；终止条件为left = right，会遍历的区间为[0, nums.size() - 1)，所以会出现遗漏的情况，遗漏了nums.size() - 1的情况，所以需要额外判断nums[left]是否等于target(当然是用nums[right]也行，因为left = right，但此时要把nums.size()<=0放在前面，防止数组为空时，right=-1越界)。

    其实这里判断nums[left]包含了两种情况，第一种情况是找到了target，此时left不一定是nums.size() - 1，但是因为找的是左边界，所以就不用再看nums.size() - 1了；第二种情况是没有找到target，此时若全部元素都大于target，则left一直右移，最终等于nums.size() - 1，若全部元素都小于target，则也没有必要看nums.size() - 1了。

  2. 是否会出现死循环：出现死循环是因为若出现mid = left(mid = right)，同时更新的时候触发了left = mid(right = mid)。注意到代码的更新条件出现了right = mid;，此时必须int mid = left + (right-left)/2;，而不能是int mid = left + (right-left+1)/2;。此时不管数组个数是奇数还是偶数，mid都会向下取整，只可能出现mid = left，所以避免了死循环（可带入nums = [0，1], target = 1理解）。

  3. 是否覆盖了数组为空的情况：数组为空的时候，right = -1，不会进入循环，若不加判断，会直接返回left = 0，是错误的，所以需要额外判断。

函数三：在排序数组中查找目标元素的第一个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int findLast(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;

    while(left < right) {
        int mid = left + (right-left+1)/2;  // 这个地方注意

        if(nums[mid] > target)
            right = mid - 1;
        else
            left = mid;
    }
    if(nums.size()<=0 || nums[left] != target)
        return -1;
    return left;
}

下面我们分析我们上述说的几点。

  1. 数组是否会越界，以及是否会出现遗漏情况：这里的搜索区间为[left, right)左闭右开区间，left最小为0，right最大为nums.size() - 1，所以搜索区间最大为[0, nums.size() - 1)，所以不会出现数组越界；终止条件为left = right，会遍历的区间为[0, nums.size() - 1)，所以会出现遗漏的情况，遗漏了nums.size() - 1的情况，所以需要额外判断nums[left]是否等于target(当然是用nums[right]也行，因为left = right，但此时要把nums.size()<=0放在前面，防止数组为空时，right=-1越界)。

    其实这里判断nums[left]包含了两种情况，第一种情况是找到了target，此时left不一定是nums.size() - 1，但对于nums[nums.size() - 1] = target，left = nums.size() - 1；第二种情况是没有找到target，此时若全部元素都大于target，则left一直右移，nums.size() - 1也会被判断，若全部元素都小于target，则也没有必要看nums.size() - 1了。

  2. 是否会出现死循环：出现死循环是因为若出现mid = left(mid = right)，同时更新的时候触发了left = mid(right = mid)。注意到代码的更新条件出现了left = mid;，此时必须int mid = left + (right-left+1)/2;，而不能是int mid = left + (right-left)/2;。此时不管数组个数是奇数还是偶数，mid都会向上取整，只可能出现mid=right，所以避免了死循环（可带入nums = [1], target = 1理解）。
  3. 是否覆盖了数组为空的情况：数组为空的时候，right = -1，不会进入循环，若不加判断，会直接返回left = 0，是错误的，所以需要额外判断。

二分查找模板

以下内容主要来源于我写了首诗，把二分搜索算法变成了默写题。我这里对不懂的地方添加一些个人注解。这部分代码主要是java代码。

寻找一个数（基本的二分搜索）

搜索一个数，如果存在，返回其索引，否则返回 -1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意

    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
    }
    return -1;
}

这段代码可以解决力扣第 704 题「二分查找」，但我们深入探讨一下其中的细节。

1、为什么 while 循环的条件中是 <=，而不是 <？

答：因为初始化 right 的赋值是 nums.length - 1，即最后一个元素的索引，而不是 nums.length。

这二者可能出现在不同功能的二分查找中，区别是：前者相当于两端都闭区间 [left, right]，后者相当于左闭右开区间 [left, right)。因为索引大小为 nums.length 是越界的，所以我们把 right 这一边视为开区间。

这句话的含义是：对于前者，初始left = 0, right = nums.length - 1，初始搜索区间应该整个数组，所以相当于两端都闭区间 [left, right]；对于后者，初始left = 0, right = nums.length，初始搜索区间应该整个数组，所以相当于左闭右开区间 [left, right)。

也就是说，相当于开区间和闭区间是由left和right的初始值决定的，因为我们的初始搜索区间要包含整个数组。

我们这个算法中使用的是前者 [left, right] 两端都闭的区间。这个区间其实就是每次进行搜索的区间。

什么时候应该停止搜索呢？当然，找到了目标值的时候可以终止：

1
2
if(nums[mid] == target)
    return mid;

但如果没找到，就需要 while 循环终止，然后返回 -1。那 while 循环什么时候应该终止？搜索区间为空的时候应该终止，意味着你没得找了，就等于没找到嘛。

while(left <= right) 的终止条件是 left == right + 1，写成区间的形式就是 [right + 1, right]，或者带个具体的数字进去 [3, 2]，可见这时候区间为空，因为没有数字既大于等于 3 又小于等于 2 的吧。所以这时候 while 循环终止是正确的，直接返回 -1 即可。

while(left < right) 的终止条件是 left == right，写成区间的形式就是 [right, right]，或者带个具体的数字进去 [2, 2]，这时候区间非空，还有一个数 2，但此时 while 循环终止了。也就是说区间 [2, 2] 被漏掉了，索引 2 没有被搜索，如果这时候直接返回 -1 就是错误的。

这里，因为初始化 right 的赋值是 nums.length - 1，所以相当于闭区间，所以while(left < right) 的终止条件是 left == right，写成区间的形式就是 [right, right]。

当然，如果你非要用 while(left < right) 也可以，我们已经知道了出错的原因，就打个补丁好了：

1
2
3
4
5
//...
while(left < right) {
    // ...
}
return nums[left] == target ? left : -1;

2、为什么 left = mid + 1，right = mid - 1？我看有的代码是 right = mid 或者 left = mid，没有这些加加减减，到底怎么回事，怎么判断？

答：这也是二分查找的一个难点，不过只要你能理解前面的内容，就能够很容易判断。

刚才明确了「搜索区间」这个概念，而且本算法的搜索区间是两端都闭的，即 [left, right]。那么当我们发现索引 mid 不是要找的 target 时，下一步应该去搜索哪里呢？

当然是去搜索区间 [left, mid-1] 或者区间 [mid+1, right] 对不对？因为 mid 已经搜索过，应该从搜索区间中去除。

3、此算法有什么缺陷？

答：至此，你应该已经掌握了该算法的所有细节，以及这样处理的原因。但是，这个算法存在局限性。

比如说给你有序数组 nums = [1,2,2,2,3]，target 为 2，此算法返回的索引是 2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是无法处理的。

这样的需求很常见，你也许会说，找到一个 target，然后向左或向右线性搜索不行吗？可以，但是不好，因为这样难以保证二分查找对数级的复杂度了。

我们后续的算法就来讨论这两种二分查找的算法。

寻找左侧边界的二分搜索

以下是最常见的代码形式，其中的标记是需要注意的细节：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int left_bound(int[] nums, int target) {
    int left = 0;
    int right = nums.length; // 注意
    
    while (left < right) { // 注意
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}

1、为什么 while 中是 < 而不是 <=?

答：用相同的方法分析，因为 right = nums.length 而不是 nums.length - 1。因此每次循环的「搜索区间」是 [left, right) 左闭右开。

while(left < right) 终止的条件是 left == right，此时搜索区间 [left, left) 为空，所以可以正确终止。

info：这里先要说一个搜索左右边界和上面这个算法的一个区别，也是很多读者问的：刚才的 right 不是 nums.length - 1 吗，为啥这里非要写成 nums.length 使得「搜索区间」变成左闭右开呢？

因为对于搜索左右侧边界的二分查找，这种写法比较普遍，我就拿这种写法举例了，保证你以后遇到这类代码可以理解。你非要用两端都闭的写法反而更简单，我会在后面写相关的代码，把三种二分搜索都用一种两端都闭的写法统一起来，你耐心往后看就行了。

2、为什么没有返回 -1 的操作？如果 nums 中不存在 target 这个值，怎么办？

答：其实很简单，在返回的时候额外判断一下 nums[left] 是否等于 target 就行了，如果不等于，就说明 target 不存在。

不过我们得考察一下 left 的取值范围，免得索引越界。假如输入的 target 非常大，那么就会一直触发 nums[mid] < target 的 if 条件，left 会一直向右侧移动，直到等于 right，while 循环结束。

由于这里 right 初始化为 nums.length，所以 left 变量的取值区间是闭区间 [0, nums.length]，那么我们在检查 nums[left] 之前需要额外判断一下，防止索引越界：

1
2
3
4
5
6
7
while (left < right) {
    //...
}
// 此时 target 比所有数都大，返回 -1
if (left == nums.length) return -1;
// 判断一下 nums[left] 是不是 target
return nums[left] == target ? left : -1;

3、为什么 left = mid + 1，right = mid ？和之前的算法不一样？

答：这个很好解释，因为我们的「搜索区间」是 [left, right) 左闭右开，所以当 nums[mid] 被检测之后，下一步应该去 mid 的左侧或者右侧区间搜索，即 [left, mid) 或 [mid + 1, right)。

看一下区间[left, mid)，可以看到已经搜索过的元素mid已经排除在外了。

4、为什么该算法能够搜索左侧边界？

答：关键在于对于 nums[mid] == target 这种情况的处理：

1
2
if (nums[mid] == target)
    right = mid;

可见，找到 target 时不要立即返回，而是缩小「搜索区间」的上界 right，在区间 [left, mid) 中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。

如果此时nums[mid]正好是最左边的边界，则继续执行下去，那么就会一直触发 nums[mid] < target 的 if 条件，left 会一直向右侧移动，直到等于 right，而此时right = mid，所以也能返回正确结果。

5、为什么返回 left 而不是 right？

答：都是一样的，因为 while 终止的条件是 left == right。

6、能不能想办法把 right 变成 nums.length - 1，也就是继续使用两边都闭的「搜索区间」？这样就可以和第一种二分搜索在某种程度上统一起来了。

答：当然可以，只要你明白了「搜索区间」这个概念，就能有效避免漏掉元素，随便你怎么改都行。下面我们严格根据逻辑来修改：

因为你非要让搜索区间两端都闭，所以 right 应该初始化为 nums.length - 1，while 的终止条件应该是 left == right + 1，也就是其中应该用 <=：

1
2
3
4
5
6
7
int left_bound(int[] nums, int target) {
    // 搜索区间为 [left, right]
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // if else ...
    }

因为搜索区间是两端都闭的，且现在是搜索左侧边界，所以 left 和 right 的更新逻辑如下：

1
2
3
4
5
6
7
8
9
10
if (nums[mid] < target) {
    // 搜索区间变为 [mid+1, right]
    left = mid + 1;
} else if (nums[mid] > target) {
    // 搜索区间变为 [left, mid-1]
    right = mid - 1;
} else if (nums[mid] == target) {
    // 收缩右侧边界
    right = mid - 1;
}

和刚才相同，如果想在找不到 target 的时候返回 -1，那么检查一下 nums[left] 和 target 是否相等即可：

1
2
3
4
// 此时 target 比所有数都大，返回 -1
if (left == nums.length) return -1;
// 判断一下 nums[left] 是不是 target
return nums[left] == target ? left : -1;

至此，整个算法就写完了，完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    // 搜索区间为 [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 收缩右侧边界
            right = mid - 1;
        }
    }
    // 判断 target 是否存在于 nums 中
    // 此时 target 比所有数都大，返回 -1
    if (left == nums.length) return -1;
    // 判断一下 nums[left] 是不是 target
    return nums[left] == target ? left : -1;
}

解释一下这里最后为啥是left而不是left + 1，因为终止条件是left = right + 1，而right + 1才等于target，所以正好只需要拿left判断即可。

这样就和第一种二分搜索算法统一了，都是两端都闭的「搜索区间」，而且最后返回的也是 left 变量的值。只要把住二分搜索的逻辑，两种形式大家看自己喜欢哪种记哪种吧。

寻找右侧边界的二分查找

类似寻找左侧边界的算法，这里也会提供两种写法，还是先写常见的左闭右开的写法，只有两处和搜索左侧边界不同：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length;
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1; // 注意
}

1、为什么这个算法能够找到右侧边界？

答：类似地，关键点还是这里：

1
2
if (nums[mid] == target) {
    left = mid + 1;

当 nums[mid] == target 时，不要立即返回，而是增大「搜索区间」的左边界 left，使得区间不断向右靠拢，达到锁定右侧边界的目的。

如果此时nums[mid]正好是最右边的边界，则继续执行下去，那么就会一直触发 nums[mid] > target 的 if 条件，right 会一直向右侧移动，直到等于 left，而此时left = mid + 1，所以也能返回正确结果。

2、为什么最后返回 left - 1 而不像左侧边界的函数，返回 left？而且我觉得这里既然是搜索右侧边界，应该返回 right 才对。

答：首先，while 循环的终止条件是 left == right，所以 left 和 right 是一样的，你非要体现右侧的特点，返回 right - 1 好了。

至于为什么要减一，这是搜索右侧边界的一个特殊点，关键在锁定右边界时的这个条件判断：

1
2
3
4
// 增大 left，锁定右侧边界
if (nums[mid] == target) {
    left = mid + 1;
    // 这样想: mid = left - 1

因为我们对 left 的更新必须是 left = mid + 1，就是说 while 循环结束时，nums[left] 一定不等于 target 了，而 nums[left-1] 可能是 target。

至于为什么 left 的更新必须是 left = mid + 1，当然是为了把 nums[mid] 排除出搜索区间，这里就不再赘述。

3、为什么没有返回 -1 的操作？如果 nums 中不存在 target 这个值，怎么办？

答：只要在最后判断一下 nums[left-1] 是不是 target 就行了。

类似之前的左侧边界搜索，left 的取值范围是 [0, nums.length]，但由于我们最后返回的是 left - 1，所以 left 取值为 0 的时候会造成索引越界，额外处理一下即可正确地返回 -1：

1
2
3
4
5
6
7
8
while (left < right) {
    // ...
}
// 判断 target 是否存在于 nums 中
// 此时 left - 1 索引越界
if (left - 1 < 0) return -1;
// 判断一下 nums[left] 是不是 target
return nums[left - 1] == target ? (left - 1) : -1;

4、是否也可以把这个算法的「搜索区间」也统一成两端都闭的形式呢？这样这三个写法就完全统一了，以后就可以闭着眼睛写出来了。

答：当然可以，类似搜索左侧边界的统一写法，其实只要改两个地方就行了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 这里改成收缩左侧边界即可
            left = mid + 1;
        }
    }
    // 最后改成返回 left - 1
    if (left - 1 < 0) return -1;
    return nums[left - 1] == target ? (left - 1) : -1;
}

当然，由于 while 的结束条件为 right == left - 1，所以你把上述代码中的 left - 1 都改成 right 也没有问题，这样可能更有利于看出来这是在「搜索右侧边界」。

left - 1才等于target，所以判断的时候要使用left - 1。

至此，搜索右侧边界的二分查找的两种写法也完成了，其实将「搜索区间」统一成两端都闭反而更容易记忆，你说是吧？

逻辑统一

有了搜索左右边界的二分搜索，你可以去解决力扣第 34 题「在排序数组中查找元素的第一个和最后一个位置」，

接下来梳理一下这些细节差异的因果逻辑：

第一个，最基本的二分查找算法：

1
2
3
4
5
6
7
因为我们初始化 right = nums.length - 1
所以决定了我们的「搜索区间」是 [left, right]
所以决定了 while (left <= right)
同时也决定了 left = mid+1 和 right = mid-1

因为我们只需找到一个 target 的索引即可
所以当 nums[mid] == target 时可以立即返回

第二个，寻找左侧边界的二分查找：

1
2
3
4
5
6
7
8
因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid + 1 和 right = mid

因为我们需找到 target 的最左侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧右侧边界以锁定左侧边界

第三个，寻找右侧边界的二分查找：

1
2
3
4
5
6
7
8
9
10
11
因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid + 1 和 right = mid

因为我们需找到 target 的最右侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧左侧边界以锁定右侧边界

又因为收紧左侧边界时必须 left = mid + 1
所以最后无论返回 left 还是 right，必须减一

对于寻找左右边界的二分搜索，常见的手法是使用左闭右开的「搜索区间」，我们还根据逻辑将「搜索区间」全都统一成了两端都闭，便于记忆，只要修改两处即可变化出三种写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
int binary_search(int[] nums, int target) {
    int left = 0, right = nums.length - 1; 
    while(left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1; 
        } else if(nums[mid] == target) {
            // 直接返回
            return mid;
        }
    }
    // 直接返回
    return -1;
}

int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定左侧边界
            right = mid - 1;
        }
    }
    // 判断 target 是否存在于 nums 中
    // 此时 target 比所有数都大，返回 -1
    if (left == nums.length) return -1;
    // 判断一下 nums[left] 是不是 target
    return nums[left] == target ? left : -1;
}

int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 别返回，锁定右侧边界
            left = mid + 1;
        }
    }
    // 判断 target 是否存在于 nums 中
    // if (left - 1 < 0) return -1;
    // return nums[left - 1] == target ? (left - 1) : -1;
    
    // 由于 while 的结束条件是 right == left - 1，且现在在求右边界
    // 所以用 right 替代 left - 1 更好记
    if (right < 0) return -1;
    return nums[right] == target ? right : -1;
}

如果以上内容你都能理解，那么恭喜你，二分查找算法的细节不过如此。通过介绍，你学会了：

1、分析二分查找代码时，不要出现 else，全部展开成 else if 方便理解。

2、注意「搜索区间」和 while 的终止条件，如果存在漏掉的元素，记得在最后检查。

3、如需定义左闭右开的「搜索区间」搜索左右边界，只要在 nums[mid] == target 时做修改即可，搜索右侧时需要减一。

4、如果将「搜索区间」全都统一成两端都闭，好记，只要稍改 nums[mid] == target 条件处的代码和返回的逻辑即可，推荐拿小本本记下，作为二分搜索模板。

最后我想说，以上二分搜索的框架属于「术」的范畴，如果上升到「道」的层面，二分思维的精髓就是：通过已知信息尽可能多地收缩（折半）搜索空间，从而增加穷举效率，快速找到目标。

常见题目

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

考虑插入的位置为pos，则成立的条件为：

这个条件可以转换为：在一个有序数组中找第一个大于等于 target 的下标。套用模板一可以得到下面代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int searchInsert(vector<int>& nums, int target) {
    int n = nums.size();
    int left = 0, right = n - 1, ans = n;
    while (left <= right) {
        int mid = ((right - left) >> 1) + left;
        if (target <= nums[mid]) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}

74. 搜索二维矩阵

编写一个高效的算法来判断 $m \times n$ 矩阵中，是否存在一个目标值。该矩阵具有如下特性：

  • 每行中的整数从左到右按升序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

这个问题其实是与704. 二分查找思想一致，只是需要将一维数组的下标转换为二维数字的下标即可。根据模板一参考代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool searchMatrix(vector<vector<int>> &matrix, int target) {
    int m = matrix.size();
    if (m == 0) return false;
    int n = matrix[0].size();

    // 二分查找
    int left = 0, right = m * n - 1;
    int pivotIdx, pivotElement;
    while (left <= right) {
        pivotIdx = (left + right) / 2;
        pivotElement = matrix[pivotIdx / n][pivotIdx % n];
        if (target == pivotElement) 
            return true;
        else if (target < pivotElement) 
            right = pivotIdx - 1;
        else 
            left = pivotIdx + 1;
    }
    return false;
}

278. 第一个错误的版本

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

这个明显可以使用模板二：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int firstBadVersion(int n) {
    int start = 1;
    int end = n;

    while(start < end) {
        int mid = start + (end - start) / 2;
        // 当前版本不是错误的
        if(!isBadVersion(mid)) {
            start = mid + 1;
        }
        else {
            end = mid;
        }
    }
    return start;
}

153. 寻找旋转排序数组中的最小值

假设按照升序排序的数组在预先未知的某个点上进行了旋转（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] ）。请找出其中最小的元素。你可以假设数组中不存在重复元素。

旋转数据查找这类题目的解决关键在于：

  1. 通过画图将问题模型抽象为下图：

捕获5.PNG

  1. 考虑和最后一个元素比较大小
  2. 考虑旋转点在0，也就是没有任何旋转的特殊情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int findMin(vector<int>& nums) {
    int start = 0;
    int end =  nums.size() - 1;
    
    while(start < end) {
        int mid = start + (end - start)/2;
        int cur = nums[mid];
        if(cur > nums[end])
            start = mid+1;
        else if(cur < nums[end])  // 可以这样写，因为while条件，决定了cur!=end
            end = mid;
    }
    return min(nums[start], nums[end]);
}

154. 寻找旋转排序数组中的最小值 II

假设按照升序排序的数组在预先未知的某个点上进行了旋转（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] ）。请找出其中最小的元素。注意数组中可能存在重复的元素。

这个题目是上一道题目的区别在于，该题目的元素是可以重复的。

捕获6.PNG

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int findMin(vector<int>& nums) {
    int start = 0;
    int end =  nums.size() - 1;
    
    while(start < end) {
        int mid = start + (end - start)/2;
        int cur = nums[mid];
        if(cur > nums[end])
            start = mid+1;
        else if(cur < nums[end])
            end = mid;
        else // 无法判断mid的位置，可能位于最小值的前面，也可能后面。唯一可以确定的是最小值在end的左边
            end--;   // 跟上一题题解的区别
    }
    return min(nums[start], nums[end]);
}

33. 搜索旋转排序数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。 (不包含重复元素)

这个题目和上两个题目不同点在于该题目是搜索特定元素，而前两个题目是找到最小元素值。

解题思路是：根据arr[mid]与arr[end]的值大小关系，划分出完全有序部分和部分有序部分。接着对于前半段有序的情况，判断出目标值是否在该有序的区间内，更新start和end；若是后半段有序，判断出目标值是否在该有序的区间内，更新start和end。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int search(vector<int>& nums, int target) {
    int start = 0;
    int end = nums.size() - 1;

    while(start <= end) {
        int mid = start + (end - start)/2;
        if(nums[mid] == target)
            return mid;
        
        if(nums[mid] < nums[end]) {  // mid到end有序
            if(nums[mid]<target && target<=nums[end]) // 目标值是否在有序区间内
                start = mid + 1;
            else
                end = mid - 1;
        }
        else {  // 从start到mid有序
            if(nums[mid]>target && target>=nums[start])  // 目标值是否在有序区间内
                end = mid - 1;
            else 
                start = mid + 1;
        }
    }
    return -1;
}

81. 搜索旋转排序数组 II

假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。 编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。(包含重复元素)

这个题目和上一个题目的不同点在于该题目中的元素是可以重复的。

解题思路是：根据arr[mid]与arr[end]的值大小关系，划分出完全有序部分和部分有序部分。接着对于前半段有序的情况，判断出目标值是否在该有序的区间内，更新start和end；若是后半段有序，判断出目标值是否在该有序的区间内，更新start和end。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
bool search(vector<int>& nums, int target) {
    int start = 0;
    int end = nums.size() - 1;

    while(start <= end) {
        int mid = start + (end - start)/2;
        if(nums[mid] == target)
            return true;
        
        if(nums[mid] < nums[end]) {  // mid到end有序
            if(nums[mid]<target && target<=nums[end]) // 目标值是否在有序区间内
                start = mid + 1;
            else
                end = mid - 1;
        }
        else if(nums[mid] > nums[end]) {  // 从start到mid有序
            if(nums[mid]>target && target>=nums[start])  // 目标值是否在有序区间内
                end = mid - 1;
            else 
                start = mid + 1;
        }
        else {   // 无法判断哪一个是单调区间，极端情况下，退化为从end到start的遍历查找
            end--;  // 跟上一题题解的区别
        }
    }
    return false;
}

参考

通过画图来深刻理解二分法
通过画图来深刻理解二分法

排序算法

原理可以参考十大经典排序算法（动图演示）。

C++代码可以参考DataStructure-And-Algorithm。

动态规划

动态规划：是一种解决问 题的思想，大规模问题的结果，是由小规模问 题的结果运算得来的。动态规划可用递归来实现(Memorization Search)。递归只是一种程序的实现方式。

理论

使用场景，需要满足几个条件：

  1. 满足以下条件之一：

    求最大/最小值（Maximum/Minimum ）

    求是否可行（Yes/No ）

    求可行个数（Count(*) ）

  2. 最优子结构（如果不能利用子问题的最优解获得整个问题的最优解，那么这种问题就不具有最优子结构。简单来说后面阶段的状态要能够通过前面阶段的状态推导出来，对应的一定能写出来状态转移方程）

  3. 重复子问题

  4. 满足不能排序或者交换（Can not sort / swap ）

如题：128. 最长连续序列 位置可以交换，所以不用动态规划

四点要素：

  1. 状态 State：灵感，创造力，存储小规模问题的结果
  2. 方程 Function：状态之间的联系，怎么通过小的状态，来算大的状态
  3. 初始化 Intialization：最极限的小状态是什么，起点
  4. 答案 Answer：最大的那个状态是什么，终点

动态规划的tabel通常会为长度+1，tabel[0]的初始化很重要，通常可以简化很多操作。但是这样操作的时候记住遍历原数组的时候，下标减1。

常见四种类型：

  1. 矩阵类型（10%）
  2. 序列类型（40%）
  3. 两个序列类型（40%）
  4. 零钱和背包（10%）

贪心算法大多题目靠背答案，所以如果能用动态规划就尽量用动规，不用贪心算法。

矩阵类型（10%）

120. 三角形最小路径和

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。

这是一个典型的动态规划问题。

  1. 状态State：用f[i][j]表示从三角顶部走到位置(i,j)的最小路径和。这里的位置(i,j)表示第 i 行第 j 列（下标从0开始）
  2. 方程：若j=0，则f[i][j]=f[i−1][0]+c[i][0]；若j=i，则f[i][j]=f[i−1][i−1]+c[i][i]；f[i][j] = min(f[i−1][j−1], f[i−1][j]) + c[i][j]，c[i][j]表示位置(i,j)对应的元素值。需要注意第 i 行有 i+1 个元素，在计算状态转移的时候注意不要
  3. 初始化：f[0][0]
  4. 答案：max(f[n-1][:])

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
int minimumTotal(vector<vector<int>>& triangle) {
    int n = triangle.size();
    vector<vector<int>> f(n, vector<int>(n));
    f[0][0] = triangle[0][0];
    for (int i = 1; i < n; ++i) {
        f[i][0] = f[i - 1][0] + triangle[i][0];   // j=0
        for (int j = 1; j < i; ++j) {
            f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j];
        }
        f[i][i] = f[i - 1][i - 1] + triangle[i][i];  // j=i
    }
    return *min_element(f[n - 1].begin(), f[n - 1].end());
}

回顾方法一中的状态转移方程，可以发现f[i][j]只与f[i-1][..]有关，而与f[i-2][..]及之前的状态无关。可以使用两个长度为$n$的一位数组进行，根据$i$的奇偶性进行转移。

image-20200910195806939

优化空间：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int minimumTotal(vector<vector<int>>& triangle) {
    int n = triangle.size();
    vector<vector<int>> f(2, vector<int>(n));
    f[0][0] = triangle[0][0];
    for (int i = 1; i < n; ++i) {
        int curr = i % 2;   // 分奇偶性
        int prev = 1 - curr;
        f[curr][0] = f[prev][0] + triangle[i][0];  // j=0
        for (int j = 1; j < i; ++j) {
            f[curr][j] = min(f[prev][j - 1], f[prev][j]) + triangle[i][j];
        }
        f[curr][i] = f[prev][i - 1] + triangle[i][i];  // j=i
    }
    return *min_element(f[(n - 1) % 2].begin(), f[(n - 1) % 2].end());  // 注意这个结尾的写法
}

64. 最小路径和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。每次只能向下或者向右移动一步。

很明显这个题目是求最优解的；存在最优子结构；并且存在重复子问题（若采用回溯法，相同子路径会重复出现）。可以使用动态规划来求解。按照上面所说的四个要素：

  1. 状态State：f[x][y]为从起点走到 x,y 的最短路径
  2. 方程：f[x][y] = min(f[x-1][y], f[x][y-1]) + A[x][y]
  3. 初始化：f[0][0] = A[0][0]、f[i][0] = sum(0,0 -> i,0)、 f[0][i] = sum(0,0 -> 0,i)
  4. 答案：f[m-1][n-1]

其实，仔细分析状态转移方程，发现f[x][y]只与上一行正上方元素和该行左边元素有关，因此可以省略掉x维，使用一维数组代替二维数组完成动态规划。参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int minPathSum(vector<vector<int>>& grid) {
    if(grid.empty())
        return 0;
    
    vector<int> vec(grid[0].size());
    for(int i=0; i<grid.size(); i++) {
        for(int j=0; j<grid[0].size(); j++) {
            if(i==0 && j==0)
                vec[0] = grid[0][0];
            else if(i == 0)
                vec[j] = vec[j-1] + grid[i][j];
            else if(j == 0)
                vec[j] = vec[j] + grid[i][j]; 
            else 
                vec[j] = min(vec[j], vec[j-1]) + grid[i][j];
        }
    }
    return vec.back();
}

62. 不同路径

一个机器人位于一个 m x n 网格的左上角。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。 问总共有多少条不同的路径？

这个问题可以转换为，最多有多少条不同的路径，所以是一个求最优解的问题；存在最优子结构；假设f[x][y]表示从 x 到 y 最多有多少条路径，那么在求解f[x+1][y]、f[x][y+1]都需要求解f[x][y]，所以存在重复子问题，可以使用动态规划解决。按照上面所说的四个要素：

  1. 定义State：f[x][y]表示从 x 到 y 最多有多少条路径
  2. 方程：f[x][y]=f[x][y-1]+f[x-1][y]
  3. 初始化：f[i][0]=f[0][i]=1
  4. 答案：f[m-1][n-1]

仔细分析状态转移方程，发现f[x][y]只与上一行正上方元素和该行左边元素有关，因此可以省略掉x维，使用一维数组代替二维数组完成动态规划。参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int uniquePaths(int m, int n) {
    if(m<=0 || n<=0)
        return 0;
    
    vector<int> vec(n);
    for(int i=0; i<m; i++) {
        for(int j=0; j<n; j++) {
            if(i==0 || j==0)
                vec[j] = 1;
            else
                vec[j] = vec[j] + vec[j-1];
        }   
    } 
    return vec.back();
}

63. 不同路径 II

一个机器人位于一个 m x n 网格的左上角 。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

这个问题和上面问题的区别在于，这里加上了一个障碍物。使用动态规划，按照上面所说的四个要素：

  1. 定义State：f[x][y]表示从 x 到 y 最多有多少条路径。若当前位置为障碍物，则f[x][y]=0，下面讨论没有障碍物时候的状态转移以及初始化
  2. 方程：f[x][y]=f[x][y-1]+f[x-1][y]
  3. 初始化：f[0][0]=1、f[i][0]=f[i-1][0]、f[0][i]=f[0][i]，这个初始化因为障碍物存在，不能全部置为1
  4. 答案：f[m-1][n-1]

仔细分析状态转移方程，发现f[x][y]只与上一行正上方元素和该行左边元素有关，因此可以省略掉x维，使用一维数组代替二维数组完成动态规划。参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
    if(obstacleGrid.empty())
        return 0;
    
    vector<int> vec(obstacleGrid[0].size());
    for(int i=0; i<obstacleGrid.size(); i++) {
        for(int j=0; j<obstacleGrid[0].size(); j++) {
            if(obstacleGrid[i][j] == 1)
                vec[j] = 0;
            else {
                if(i==0 && j==0)
                    vec[j] = 1;
                else if(j > 0)
                    vec[j] = vec[j] + vec[j-1];
            }
        }
    }
    return vec.back();
}

序列类型（40%）

70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

这应该是最简单的动态规划问题。按照上面四个要素进行分析：

  1. 状态State：f(x)爬到台阶 x 有多少种方法
  2. 方程：f(x)=f(x-1)+f(x-2)
  3. 初始化：f(1)=1、f(2)=2
  4. 答案：f(n)

分析状态转移方程，发现f(x)只与前两个状态有关，所以可以用两个变量保存这两个状态即可。参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int climbStairs(int n) {
    if(n <= 0)
        return 0;

    vector<int> vec{1, 2};
    if(n <= 2) 
        return vec[n-1];
    
    for(int i=3; i<=n; i++) {
        int val = vec[0] + vec[1];
        vec[0] = vec[1];
        vec[1] = val;
    }
    return vec.back();
}

55. 跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。

这个题目有两种解法。

第一种方法是借助贪心算法，使用一个变量k记录能够跳到的最远元素的下标（从0开始）。依次遍历数组的元素，若k大于等于当前下标，证明可以跳到该元素，然后看是否需要更新k以及是否已经可以跳到最后一个位置了；若k小于当前下标，则证明无法跳到该元素，返回false。参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
bool canJump(vector<int>& nums) {
    int k = 0;
    for(int i=0; i<nums.size(); i++) {
        if(k >= i) {
            k = max(k, nums[i]+i);
            if(k >= nums.size()-1)
                return true;
        }
        else
            return false;
    }
    return true;
}

第二种方法是借助动态规划，该方法求解过程并没有贪心简单。还是按照上面四个要素进行分析：

  1. 状态State：f[i]表示 i 下标能不能到达
  2. 方程：f[i] = OR(f[j],j<i&&j能跳到i) 判断之前所有的点最后一跳是否存在能跳到当前点的（OR表示存在）。
  3. 初始化：f(0)=1
  4. 答案：f(n-1)

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool canJump(vector<int>& nums) {
    int n = nums.size();
    vector<bool> dp(n, false);
    dp[0] = true;
    for(int i=1; i<n; i++) {
        for(int j=i-1; j>=0; j--) {
            if(dp[j] && j+nums[j]>=i) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp.back();
}

45. 跳跃游戏 II

给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

跟上一道题目一样，这也是典型的贪心算法，每次都是贪心的选择最远距离，通过局部最优解得到全局最优解。这里的贪心有两种方法。

第一种方法是反向查找出发位置。有多个位置通过跳跃可以达到最后一个位置，直观上，可以贪心地选择距离最后一个位置最远的那个位置，可以从左到右遍历数组，选择第一个满足要求的位置。找到最后一步跳跃前所在的位置之后，继续贪心地寻找倒数第二步跳跃前所在的位置，以此类推，直到找到数组的开始位置。这种思路需要遍历多遍（时间复杂度为$O(n^2)$），C++会超时，这里给出Java版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int jump(int[] nums) {
    int position = nums.length - 1;
    int steps = 0;
    while (position > 0) {
        for (int i = 0; i < position; i++) {
            if (i + nums[i] >= position) {
                position = i;
                steps++;
                break;
            }
        }
    }
    return steps;
}

第二种方法是正向查找可达到的最大位置。假设第一个元素最远可以跳 j 个位置，将从这 j 个位置开始能够跳到的最远距离记做 sum；使用 end 变量（初始化为0）记录第一步可以跳的最远距离；依次遍历所有位置，若当前位置下标大于 end，则证明需要再跳一步，此时需要更新end和step。另外，我们不会遍历到最后一个元素，因为若刚好end=n-1，那么遍历到最后一个元素时，会凭空的多一个step。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int jump(vector<int>& nums) {
    int step = 0;
    int sum = 0;
    int end = 0;
    
    for(int i=0; i<nums.size()-1; i++) {  // 注意没有遍历到最后一个元素
        sum = max(sum, i+nums[i]); // 用于记录该step能跃过的所有节点中，下一个能跳过的最大值
        if(i == end) {  // 需要再跳，才有可能到最终元素，注意更新end
            end = sum;
            step++;
        }
    }
    return step;
}

5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。根据这样的思路，可以使用动态规划的方法解决本题。

  1. 状态State：定义dp[i][j]为s[i, j]是否为回文子串
  2. 方程：dp[i][j] = dp[i+1][j-1] and (s[i]==s[j])
  3. 初始化：dp[i][i]=1、dp[i][j]=s[i][j] if j-i=1
  4. 答案：若dp[i][j]=1，则判断是否需要更新最终的最长回文子串答案

这道题需要注意的是dp[i][j]的更新次序，参考代码为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
string longestPalindrome(string s) {
    int n = s.size();
    string ans;

    vector<vector<int>> dp(n, vector<int>(n));
    for(int l=0; l<n; l++) {  // j-i的值
        for(int i=0; i+l<n; i++) { // 开始坐标，注意停止条件
            int j = i+l; // 结束坐标
            if(l == 0)
                dp[i][j] = 1;
            else if(l == 1)
                dp[i][j] = s[i]==s[j];
            else   
                dp[i][j] = dp[i+1][j-1] && (s[i]==s[j]);
            
            if(dp[i][j] && l+1>ans.size())
                ans = s.substr(i, l+1);
        }
    }
    return ans; 
}

132. 分割回文串 II

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回符合要求的最少分割次数。

  1. 状态State：dp[i]表示前缀子串 s[0,i] 分割成若干个回文子串所需要最小分割次数
  2. 方程：若s[0,i]本身为回文串，则d[i]=0；否则dp[i] = min([dp[j] + 1 for j in range(i) if s[j+1, i] 是回文])
  3. 初始化：dp[0]=0
  4. 答案：s[n-1]

可以看到这个问题其实包含了5. 最长回文子串子问题，与之相似的131. 分割回文串却是一个回溯法解决的题目。该题目的参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
int minCut(string s) {
    int n = s.size();
    if(n<=1)
        return 0;

    vector<vector<int>> dp(n, vector<int>(n));
    for(int l=0; l<n; l++) {    // j-i的值
        for(int i=0; i+l<n; i++) {   // 开始坐标，注意停止条件
            int j = i + l;   // 结束坐标
            if(l == 0)
                dp[i][j] = 1;
            else if(l == 1)
                dp[i][j] = s[i]==s[j];
            else 
                dp[i][j] = dp[i+1][j-1] && (s[i]==s[j]);
        }
    }

    vector<int> vec(n);
    for(int i=0; i<n; i++) {
        vec[i] = i;  // 初始化最大所需切割次数
    }

    for(int i=1; i<n; i++) {
        if(dp[0][i] == 1) {  // 若s[o,i]为回文串
            vec[i] = 0;
            continue;
        }

        for(int j=0; j<i; j++) {
            if(dp[j+1][i] == 1)
                vec[i] = min(vec[i], vec[j] + 1);  // 找到最小值
        }
    }
    return vec.back();
}

300. 最长上升子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。子序列下标可以不连续。

  1. 状态State：f[i]表示从0开始到 i 结尾的最长序列长度
  2. 方程：f[i] = max(f[j])+1 ,a[j]<a[i] and j<i
  3. 初始化：f[i]=1
  4. 答案：max(f[0]...f[n-1])

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    // 特殊输入测试
    if(n==0) return 0;

    vector<int> dp(n, 1);
    for(int i=0; i<n; i++) {
        for(int j=0; j<i; j++) {
            if(nums[i] > nums[j])
                dp[i] = max(dp[j]+1, dp[i]);
        }
    }
    return *max_element(dp.begin(), dp.end());
}

139. 单词拆分

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

  1. 状态State：f[i]表示前 i 个字符是否可以被划分
  2. 方程：f[i] = f[j] && s[j~i-1] in wordDict, j<i（注意下标）
  3. 初始化：f[0]=true
  4. 答案：f[n]

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool wordBreak(string s, vector<string>& wordDict) {
    auto wordDictSet = unordered_set <string> ();
    for (auto word: wordDict) {
        wordDictSet.insert(word);
    }

    auto dp = vector <bool> (s.size() + 1);
    dp[0] = true;
    for (int i = 1; i <= s.size(); ++i) {
        for (int j = 0; j < i; ++j) {
            if (dp[j] && wordDictSet.find(s.substr(j, i - j)) != wordDictSet.end()) {   // 注意下标
                dp[i] = true;
                break;
            }
        }
    }

    return dp[s.size()];
}

两个序列类型（40%）

1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。若这两个字符串没有公共子序列，则返回 0。

  1. 状态State：dp[i][j]为text1前 i 个和text2前 j 个字符最长公共子序列
  2. 方程：若text1[i-1]=text2[j-1]，则dp[i][j]=dp[i-1][j-1]+1；否则dp[i][j]=max(dp[i-1][j], dp[i][j-1])
  3. 初始化：dp[0][i]=dp[i][0]=0
  4. 答案：dp[m][n]

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int longestCommonSubsequence(string text1, string text2) {
    int length1 = text1.size();
    int length2 = text2.size();

    vector<vector<int>> dp(length1+1, vector<int>(length2+1, 0));
    for(int i=1; i<=length1; i++) {
        for(int j=1; j<=length2; 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]);
        }
    }
    return dp[length1][length2];
}

72. 编辑距离

给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：插入一个字符、删除一个字符、替换一个字符。

  1. 状态State：dp[i][j]为word1前 i 个字符编辑为word2前 j 个字符最少需要多少次操作

  2. 方程：若word1[i-1]==word2[j-1]，则dp[i][j]=dp[i-1][j-1]；否则dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1。

    对dp[i-1][j-1]表示替换操作，dp[i-1][j]表示删除操作，dp[i][j-1]表示插入操作的补充理解：以 word1 为 “horse”，word2 为 “ros”，求dp[5][3] 为例，即要将 word1的前 5 个字符转换为 word2的前 3 个字符，也就是将 horse 转换为 ros，因此有：

    • dp[i-1][j-1]，即先将 word1 的前 4 个字符 hors 转换为 word2 的前 2 个字符 ro，然后将第五个字符word1[4]（因为下标基数以 0 开始） 由 e 替换为 s（即替换为 word2 的第三个字符，word2[2]）
    • dp[i][j-1]，即先将 word1 的前 5 个字符 horse 转换为 word2 的前 2 个字符 ro，然后在末尾补充一个 s，即插入操作
    • dp[i-1][j]，即先将 word1 的前 4 个字符 hors 转换为 word2 的前 3 个字符 ros，然后删除 word1 的第 5 个字符

  3. 初始化：dp[0][i] = i、dp[i][0] = i;

  4. 答案：dp[m][n]

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int minDistance(string word1, string word2) {
    int length1 = word1.size();
    int length2 = word2.size();
    if(length1*length2 == 0)
        return word1.size()+word2.size();

    vector<vector<int>> dp(length1+1, vector<int>(length2+1, 0));
    for(int i=1; i<=length2; i++)
        dp[0][i] = i;
    for(int i=0; i<=length1; i++)
        dp[i][0] = i;

    for(int i=1; i<=length1; i++) {
        for(int j=1; j<=length2; j++) {
            if(word1[i-1] == word2[j-1])
                dp[i][j] = dp[i-1][j-1];
            else {
                int minV = min(dp[i-1][j-1], dp[i][j-1]);
                minV = min(minV, dp[i-1][j]);
                dp[i][j] = minV + 1;
            }
        }
    }
    return dp[length1][length2];
}

零钱和背包（10%）

322. 零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

  1. 状态State：dp[i]组成总金额为 i 所需的最少硬币个数
  2. 方程：dp[i]=min(dp[i-coins[j]]+1)
  3. 初始化：dp[0]=0、dp[i]=amount+1(i>0)
  4. 答案：若dp[amount]==amount+1，则返回-1；否则返回dp[amount]

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int coinChange(vector<int>& coins, int amount) {
    if(amount <= 0)
        return 0;

    vector<int> dp(amount+1, amount+1);
    dp[0] = 0;

    for(int i=1; i<=amount; i++) {
        for(int j=0; j<coins.size(); j++)
            if(i-coins[j] >= 0)
                dp[i] = min(dp[i], dp[i-coins[j]]+1);
    }
    return dp[amount]==amount+1?-1:dp[amount];
}

92. 背包问题

在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]。你不可以将物品进行切割。

  1. 状态State：dp[i][j]表示前i个物品，能不能填满容量为j的背包。
  2. 方程：dp[i][j] = dp[i-1][j] OR dp[i-1][j-A[i-1]]。注意i表示前i个物品，换算到下标时为i-1
  3. 初始化：dp[0][0]=True
  4. 答案：j if dp[m-1][j]=1 else -1 for j in range(m, -1, -1)

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int backPack(int m, vector<int> &A) {
    // write your code here
    int n = A.size();
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
    dp[0][0] = 1;

    for(int i=1; i<=n; i++) {
        for(int j=0; j<=m; j++) {
            dp[i][j] = dp[i-1][j];
            if(j-A[i-1]>=0)
                dp[i][j] = dp[i][j] || dp[i-1][j-A[i-1]];
        }
    }

    for(int j=m; j>=0; j--) {
        if(dp[n][j])
            return j;
    }
    return -1;
}

很明显，本题所用的存储空间可以优化。参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int backPack(int m, vector<int> &A) {
    // write your code here
    int n = A.size();
    vector<int> dp(m+1, 0);
    dp[0] = 1;

    for(int i=1; i<=n; i++) {
        for(int j=m; j>=A[i-1]; j--) {
            dp[j] = dp[j] || dp[j-A[i-1]];
        }
    }

    for(int j=m; j>=0; j--) {
        if(dp[j])
            return j;
    }
    return -1;
}

01背包问题

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 $v_i$，价值是 $w_i$。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输入第一行N、V分别表示物品数量和背包容积；接下来有N行，每行两个整数$v_i,w_i$，分别表示第$i$个物品的体积和价值。输出最大价值。

这个问题是典型的动态规划问题。最大的特点是每一件物品只能使用一次。

  1. 状态State：定义f[i][j]为所有选法集合中，只从前i个物品中选，并且总体积 $\leq j$ 的选法集合，它的值是这个集合中每一个选法的最大值。
  2. 方程：f[i][j] = max(f[i-1][j], f[i-1][j-v[i]]+w[i] if j>=v[i])。其中f[i-1][j]表示不选第i个物品的集合中的最大值；f[i-1][j-v[i]]+w[i]表示选第i个物品的集合中的最大值。
  3. 初始化：f[0][0]=0
  4. 答案：f[N][V]

示例代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;

int main() {
    int n, m; // n goods
    cin >> n >> m;
    vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
    
    for(int i=1; i<=n; i++) {
        int v, w;
        cin >> v >> w;
        for(int j=1; j<=m; j++) {
            dp[i][j] = dp[i-1][j];
            if(j>=v)
                dp[i][j] = max(dp[i][j], dp[i-1][j-v]+w);
        }
    }
    cout << dp[n][m] << endl;
    return 0;
}

优化之后的代码实例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;

int main() {
    int n, m; // n goods
    cin >> n >> m;
    vector<int> dp(m+1, 0);
    
    for(int i=0; i<n; i++) {
        int v, w;
        cin >> v >> w;
        for(int j=m; j>=v; j--) {
            dp[j] = max(dp[j], dp[j-v]+w);
        }
    }
    cout << dp.back() << endl;
    return 0;
}

完全背包问题

有 N 件物品和一个容量是 V 的背包。每件物品都有无限件可用。第 i 件物品的体积是 $v_i$，价值是 $w_i$。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输入第一行N、V分别表示物品数量和背包容积；接下来有N行，每行两个整数$v_i,w_i$，分别表示第$i$个物品的体积和价值。输出最大价值。

该题目和上一个题目区别在于本题的每件物品可以重复使用。同理可以采用动态规划解决该问题。

  1. 状态State：定义f[i][j]为所有选法集合中，只从前i个物品中选，并且总体积 $\leq j$ 的选法集合，它的值是这个集合中每一个选法的最大值。
  2. 方程：f[i][j] = max(f[i-1][j], f[i-1][j-v[i]*k]+w[i]*k if j>=v[i]*k)。其中f[i-1][j]表示不选第 i 个物品的集合中的最大值；f[i-1][j-v[i]*k]+w[i]*k表示选第i个物品k次的集合中的最大值。
  3. 初始化：f[0][0]=0
  4. 答案：f[N][V]

上一道题中，逆序遍历体积是为了保证更新当前状态时，用到的状态是上一轮的状态，保证每个物品只有一次或零次；在这里，因为每个物品可以取任意多次，所以不再强求用上一轮的状态，即本轮放过的物品，在后面还可以再放，所以可以顺序遍历体积。参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> dp(m+1, 0);
    
    for(int i=1; i<=n; i++) {
        int v, w;
        cin >> v >> w;
        for(int j=v; j<=m; j++) {
            //dp[j] = max(dp[j], dp[j-v]+w);
            for(int k=1; k<=j/v; k++)
               dp[j] = max(dp[j], dp[j-k*v]+w*k);
        }
    }
    cout << dp.back() << endl;
    return 0;
}

参考

最优子结构（optimal substructure）
动态规划（Java、Python）
动态规划、中心扩散、Manacher 算法
Python列表解析配合if else
AcWing 3. 完全背包问题—一维动态规划转移过程模拟

贪心算法

贪心算法一般用来解决需要 “找到要做某事的最小数量” 或 “找到在某些情况下适合的最大物品数量” 的问题，且提供的是无序的输入。

递归思维

理论

递归是一种应用非常广泛的算法（或者编程技巧）。递归分为两个步骤：去的过程叫“递”，回来的过程叫“归”。

当问题满足如下三个条件时，则适合使用递归解决：

  1. 一个问题的解可以分解为几个子问题的解
  2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
  3. 存在递归终止条件。另外，还需要注意的是，要通过几个边界值例子，看终止条件是否足够。

写递归代码有两个最关键的步骤：

  1. 写出递推公式
  2. 找到终止条件

理解递归代码需要把握住如下几点：

  1. 如果试图想清楚整个递和归过程的做法，实际上是进入了一个思维误区
  2. 如果一个问题 A 可以分解为若干子问题 B、C、D，可以假设子问题 B、C、D 已经解决，在此基础上思考如何解决问题 A。而且，只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，理解起来就简单多了。
  3. 因此，编写递归代码的关键是，只要遇到递归，就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

递归有利有弊，利是递归代码的表达力很强，写起来非常简洁；而弊就是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。所有的递归代码都可以改为迭代循环的非递归写法。

常见题目

344. 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

这道题可以采用递归的方式解决。参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
void reverseStringCore(vector<char>& s, int start, int end) {
    if(start >= end)
        return;

    swap(s[start], s[end]);
    reverseStringCore(s, start+1, end-1);
}

void reverseString(vector<char>& s) {
    reverseStringCore(s, 0, s.size()-1);
}

当然，可以采用循环以及交换元素的方式解决，参考代码如下：

1
2
3
4
5
6
7
8
9
10
void reverseString(vector<char>& s) {
    int length = s.size();
    
    int start=0, end=length-1;
    while(start<end) {
        swap(s[start], s[end]);
        start++;
        end--;
    }
}

24. 两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

可以采用递归方法解决这个问题，参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ListNode* swapPairsCore(ListNode* first, ListNode* two) {
    ListNode* third = two->next;
    two->next = first;

    if(third && third->next)
        first->next = swapPairsCore(third, third->next);
    else
        first->next = third;
    return two;
}

ListNode* swapPairs(ListNode* head) {
    if(head!=NULL && head->next!=NULL)
        return swapPairsCore(head, head->next);
    return head;
}

95. 不同的二叉搜索树 II

给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。

根据二叉树的性质，若根节点的值为$i$，则左子树的范围为$1\sim i-1$，右子树的范围为$i+1 \sim n$，且左子树和右子树也同样为二叉搜索树，因此可以递归的解决这个问题。

定义generateTrees(start, end)函数表示当前值的集合[start,end]，返回序列[start,end]生成的所有可行的二叉搜索树（使用vector表示，每个值均为可行二叉搜索树的根节点）。考虑枚举[start,end]中的值i为当前二叉搜索树的根，那么序列划分为了[start,i−1]和[i+1,end]两部分。递归调用这两部分，即generateTrees(start, i - 1)和generateTrees(i + 1, end)，获得所有可行的左子树和可行的右子树，那么最后一步只要从可行左子树集合中选一棵，再从可行右子树集合中选一棵拼接到根节点上，并将生成的二叉搜索树放入答案数组即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
vector<TreeNode*> generateTreesCore(int start, int end) {
    // 某棵树终止
    if(start>end)
        return {nullptr};
    
    vector<TreeNode*> res;
    for(int i=start; i<=end; i++) {  // 枚举可行根节点
        vector<TreeNode*> leftV = generateTreesCore(start, i-1);  // 获得所有可行的左子树集合（存储根节点）
        vector<TreeNode*> rightV = generateTreesCore(i+1, end);   // 获得所有可行的右子树集合（存储根节点）

        for(auto nodeL:leftV) {   // 遍历每一个可行左子树
            for(auto nodeR:rightV) {  // 遍历每一个可行右子树
                TreeNode* node = new TreeNode(i);   // 接到根节点上，形成一棵树，放到本次迭代的vecotr中
                node->left = nodeL;
                node->right = nodeR;
                res.push_back(node);
            }
        }
    }
    return res;
}

// 返回的是所有可行搜索树的根节点
vector<TreeNode*> generateTrees(int n) {
    vector<TreeNode*> res;
    if(n<1)
        return res;
    
    res = generateTreesCore(1, n);
    return res;
}

509. 斐波那契数

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。

这道题其实可以用循环来做，但是一般来说，这是一道很典型的递归问题。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
private:
    vector<int> vec;
public:
    int fib(int N) {
        if(N==1 || N==0) 
            return N;
        
        return fib(N-1) + fib(N-2);
    }
};

滑动窗口思想

理论

这类题目更像是双指针的升级版，滑动窗口的核心是维护一个窗口集，根据窗口集来进行处理。核心步骤包括：

  1. 右指针右移，窗口数据更新（注意移动的范围）
  2. 判断窗口是否需要收缩
  3. 左指针右移，窗口数据更新
  4. 根据题意计算结果

常见题目

76. 最小覆盖子串

给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。

很明显，这个题目需要用滑动窗口去做。在 S 上滑动窗口，通过移动右指针不断扩张窗口。当窗口包含 T 全部所需的字符后，如果能收缩，就收缩窗口得到最小窗口。而判断是否包含 T 所需的全部字符，需要借助哈希表记录所有字符以及出现的位置。

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
bool judge(unordered_map<char, int>& need, unordered_map<char, int>& window) {
    for(const auto& p:need) {  // 注意必须是need循环，window可能字符并不全
        if(window[p.first] < p.second)
            return false;
    }
    return true;
}

string minWindow(string s, string t) {
    unordered_map<char, int> need, window;  // need 存储 t 每个字符出现的次数
    for(int i=0; i<t.size(); i++)
        need[t[i]]++;

    int left=0, right=-1;  // 注意这个初始值，是为了使用++right，而不是right++，保证统计windows时下标与need.find一致
    int ansL=-1, len=INT_MAX;
    while(right+1<int(s.size())) {  // 注意这个right的取值
        if(need.find(s[++right]) != need.end()) {  // 右移，注意window只存储了t中出现的字符
            window[s[right]]++;
        }

        while(judge(need, window) && left<=right) {
            if(right-left+1 < len) {   // 记录最小字符子串的开始坐标和长度，上面用的是++right，所以这里要加1
                len = right-left+1;
                ansL = left;
            }

            if(need.find(s[left]) != need.end())   // 左移，注意window只存储了t中出现的字符
                window[s[left]]--;

            left++;  // 注意这个left的位置，不要放在上面的if条件里面
        }
    }
    return ansL>-1?s.substr(ansL, len):string();
}

算法的空间复杂度可以优化，使用一个哈希表，哈希表的每个字符对应的值含义为：

  1. 若大于0，则滑动窗口中该字符还应该出现几次
  2. 若等于0，则滑动窗口中该字符次数的次数正好
  3. 若小于0，则滑动窗口中该字符多出现了几次

对应的若哈希表中的所有值均小于等于0，则应该缩小窗口，参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
bool judge(unordered_map<char, int>& need) {
    for(const auto& p:need) {  // 注意必须是need循环，window可能字符并不全
        if(p.second > 0)
            return false;
    }
    return true;
}

string minWindow(string s, string t) {
    unordered_map<char, int> need, window;  // need 存储 t 每个字符出现的次数
    for(int i=0; i<t.size(); i++)
        need[t[i]]++;

    int left=0, right=-1;  // 注意这个初始值，是为了使用++right，而不是right++，保证统计windows时下标与need.find一致
    int ansL=-1, len=INT_MAX;
    while(right+1<int(s.size())) {
        if(need.find(s[++right]) != need.end()) {
            need[s[right]]--;
        }

        while(judge(need) && left<=right) {
            if(right-left+1 < len) {   // 记录最小字符子串的开始坐标和长度
                len = right-left+1;
                ansL = left;
            }

            if(need.find(s[left]) != need.end())   // 左移
                need[s[left]]++;

            left++;
        }
    }
    return ansL>-1?s.substr(ansL, len):string();
}

567. 字符串的排列

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。换句话说，第一个字符串的排列之一是第二个字符串的子串。

这道题乍一看比上一道题要难，该题要判断是否包含 s1 的排列，而上一道题是判断包含 T 所有字符的最小子串。其实包含 s1 的排列和包含 T 所有字符只是两个说法而已，实际在用的时候都只需要使用一个哈希表记录出现过的字符以及出现的次数即可。

另外，该题和上一道题的区别在于本题的滑动窗口大小是固定的。有两个思路可以解决这个问题。

第一个思路是使用上一道题的模板，使用一个match变量记录当前滑动窗口中有多少个字符满足了出现的次数。滑动窗口的缩小条件为当前窗口的大小大于等于 s1 的长度，注意在移动左右指针的时候，更新window窗口以及match变量的值。参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
bool judge(unordered_map<char, int>& need, unordered_map<char, int>& window) {
    for(const auto& p: need) {  // 注意必须是need循环，window可能字符并不全
        if(window[p.first] < p.second)
            return false;
    }
    return true;
}

bool checkInclusion(string s1, string s2) {
    unordered_map<char, int> need, window;
    for(const auto& c: s1)
        need[c]++;

    int left=0, right=-1;  // 注意这个初始值，是为了使用++right，而不是right++，保证统计windows时下标与need.find一致
    int match = 0;
    while(right+1 < int(s2.size())) {
        if(need.find(s2[++right]) != need.end()) {   // 移动右指针的时候更新 window 和 match的值
            window[s2[right]]++;
            if(window[s2[right]] == need[s2[right]]) {
                match++;
            }
        }
        
        while(right-left+1 >= s1.size()) {  // 目标框大小固定，当超过时，缩小框
            if(match == need.size())  // 包含了 s1 的全排列
                return true;
            if(need.find(s2[left]) != need.end()) {  // 移动左指针的时候更新 window 和 match的值
                if(window[s2[left]] == need[s2[left]])
                    match--;
                window[s2[left]]--;
            }
            left++;  // 注意这个left的位置，不要放在上面的if条件里面
        }
    }
    return false;
}

第二个思路是只使用一个哈希表，哈希表的每个字符对应的值含义为：

  1. 若大于0，则滑动窗口中该字符还应该出现几次
  2. 若等于0，则滑动窗口中该字符次数的次数正好
  3. 若小于0，则滑动窗口中该字符多出现了几次

对应的代码为（该代码是比较标准的固定窗口大小的模板）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool checkInclusion(string s1, string s2) {
    unordered_map<char, int> need;
    for(const auto& c: s1)
        need[c]++;

    int left=0, right=0;
    while(right < s2.size()) {
        char c = s2[right++];
        need[c]--;
        while(need[c]<0 && left<=right) {  // 该字符多出现了，收缩窗口
            need[s2[left]]++;
            left++;
        }
        if(right-left == s1.size())  // 注意上面的right++了，所以这里不需要加1了
            return true;  // 当满足此条件是，一定是need中所有的值均为0，否则的话一定会有小于0的值，执行上述while循环
    }

    return false;
}

438. 找到字符串中所有字母异位词

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

  • 字母异位词指字母相同，但排列不同的字符串。
  • 不考虑答案输出的顺序

该题目可以使用滑动窗口的思想解决，并且由题意可知这是一个固定大小窗口的题目。因此窗口收缩的判断条件为当前窗口的大小大于等于 p 的长度。另外，在收缩窗口的时候，注意判断当前窗口是否满足要求。

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
vector<int> findAnagrams(string s, string p) {
    vector<int> result;

    unordered_map<char, int> need, window;
    int left=0, right=-1;
    int match = 0;
    for(const auto& c: p)
        need[c]++;
    
    while(right+1<int(s.size())) {
        if(need.find(s[++right]) != need.end()) {
            window[s[right]]++;
            if(window[s[right]] == need[s[right]])
                match++;
        }

        if(right-left+1 >= p.size()) {
            if(match == need.size()) {
                result.push_back(left);
            }
            
            if(need.find(s[left]) != need.end()) {
                if(need[s[left]] == window[s[left]])
                    match--;
                window[s[left]]--;
            }
            left++;
        }
    }
    return result;
}

参考上一个题目，可以简化为使用一个哈希表解决。另外，上一题目是比较标准的固定窗口大小的模板，套用之后代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> findAnagrams(string s, string p) {
    vector<int> result;
    unordered_map<char, int> need;
    for(const auto& c: p)
        need[c]++;

    int left=0, right=0;        
    while(right<int(s.size())) {
        char c = s[right++];
        need[c]--;

        while(need[c]<0 && left<=right) {
            need[s[left]]++;
            left++;
        }

        if(right-left == p.size())
            result.push_back(left);
    }
    return result;
}

3. 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

这个题目明显可以使用滑窗思想解决。使用一个哈希表记录每个字符出现了多少次，窗口收缩条件为若当前字符出现了多次，则收缩左指针直到当前字符出现一次。

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> record;

    int result=0;
    int left=0, right=0;
    while(right<int(s.size())) {
        char c = s[right];
        record[c]++;
        right++;

        // 缩小窗口
        while(record[c] > 1) {
            record[s[left]]--;
            left++;
        }

        result = max(result, right-left);
    }
    return result;
}

总结

滑动窗口的模板可以分为两个：

  1. 一般模板
  2. 固定滑窗大小的模板

第二个模板代码更加简洁，并且空间时间复杂度较低。若遇到固定窗口大小的题目，优先使用第二个模板。

参考

不同的二叉搜索树 II
滑动窗口(十行代码)

二叉搜索树

理论

  1. 定义：

    • 每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值。
    • 每个节点中的值必须小于（或等于）存储在其右子树中的任何值。

  2. 二叉搜索树的中序遍历是递增序列，这个性质经常能够使用到。

  3. 二叉搜索树经常使用递归方法实现。

  4. 在平均情况下，能够在 $\mathcal{O}(\log N)$ 的时间内完成搜索和插入元素。

常见题目

98. 验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

这个题目的难点在于，一个节点的左子树节点值必须都小于该节点，而该节点的右子树节点值必须大于该节点。因此递归过程中需要使用两个变量在递归的时候记录端点值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool isValidBSTCore(TreeNode* node, long long minV, long long maxV) {
    if(node == NULL)
        return true;

    if(node->val<=minV || node->val>=maxV) 
        return false;
    
    return isValidBSTCore(node->left, minV, node->val) && isValidBSTCore(node->right, node->val, maxV);
}


bool isValidBST(TreeNode* root) {
    long long minV = (long long)INT_MIN - 1;
    long long maxV = (long long)INT_MAX + 1;
    return isValidBSTCore(root, minV, maxV);
}

701. 二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。

考虑最简单的插入方式。将插入的节点作为叶子节点插入。插入到哪个叶节点可以遵循如下原则：

  1. 若val > node.val，且右子树为空，则插入到右子树
  2. 若val < node.val，且左子树为空，则插入到左子树

基于循环方式的参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
TreeNode* insertIntoBST(TreeNode* root, int val) {
    TreeNode* newNode = new TreeNode(val);
    if(root == NULL)
        return newNode;
    
    TreeNode* node = root;
    while(node) {
        if(node->val < val) {
            if(node->right == NULL) {
                node->right = newNode;
                break;
            }
            node = node->right;
        }
        else {
            if(node->left == NULL) {
                node->left = newNode;
                break;
            }
            node = node->left;
        }
    }
    return root;
}

Java版本的基于递归的方式参考代码如下：

1
2
3
4
5
6
7
8
9
public TreeNode insertIntoBST(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);

    // insert into the right subtree
    if (val > root.val) root.right = insertIntoBST(root.right, val);
    // insert into the left subtree
    else root.left = insertIntoBST(root.left, val);
    return root;
}

450. 删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。一般来说，删除节点可分为两个步骤：

  1. 首先找到需要删除的节点；
  2. 如果找到了，删除它。

说明： 要求算法时间复杂度为 O(h)，h 为树的高度。

该题的考察点在于二叉搜索树的定义。

首先介绍一下二叉搜索树前驱节点、后继节点的概念：

  1. 前驱节点：比当前节点小的最大节点，即中序遍历序列的下一个节点。
  2. 后继节点：比当前节点大的最小节点，即中序遍历序列的前一个节点。

然后，还需要注意几个关键点：

1. 对于删除节点，只需要更改当前节点的值即可，不需要调整左右指针
   2. 删除节点的时候只需要让当前节点值等于NULL即可
   3. C++在函数内部会更改形参的值，对于实际调用或者递归的时候，要考虑形参和实参的关系

解决问题的思路为：

  1. 若删除的是叶子节点，直接删除即可
  2. 如果含有右节点，则将后继节点的值赋值给当前节点，递归删除后继节点
  3. 如果含有左节点，则将前驱节点的值赋值给当前节点，递归删除前驱节点

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
// 找到前驱节点
TreeNode* findPre(TreeNode* node) {
    node = node->left;
    while(node->right) // 注意这个判断条件，可以返回不为NULL的结果
        node = node->right;
    return node;
}
// 找到后驱节点
TreeNode* findPost(TreeNode* node) {
    node = node->right;
    while(node->left)
        node = node->left;
    return node;
} 

TreeNode* deleteNode(TreeNode* root, int key) {
    if(root == NULL)
        return root;
    
    if(root->val < key) 
        root->right = deleteNode(root->right, key);  // 注意调用递归的时候更新递归子函数的更改的结果
    else if(root->val > key)
        root->left = deleteNode(root->left, key);
    else {
        if(root->left==NULL && root->right==NULL) {  // 删除的是叶子节点
            //delete root;  // new对应delete，new[]对应delete[]
            root = NULL;
        }
        else if(root->right) {  // 如果含有右子树
            TreeNode* post = findPost(root);
            root->val = post->val;
            root->right = deleteNode(root->right, root->val); // 必须采用递归的方式，不能直接置post=NULL
        }
        else {
            TreeNode* pre = findPre(root);
            root->val = pre->val;
            root->left = deleteNode(root->left, root->val);
        }
    }

    return root;
}

这里解释一下为什么第32行需要采用递归的方式删除。

首先，从特殊例子来看，如下图所示，节点33的前驱节点为25，后继节点为34，这两个节点均不是叶子节点，所以需要递归删除。

在这里插入图片描述

其次，从语法上来看：

  1. 函数内部若直接将post=NULL，则只是局部指针变量指向了NULL，并没有对整个树进行更改
  2. 若在函数内部*post=NULL，则*post是一个TreeNode对象，将该对象置为NULL，会隐式的调用构造函数，而NULL会隐式的转换为0，调用构造函数的结果会将该节点的val置为0，而不是将该块区域置为NULL。
  3. 若采用递归的方式调用，极端情况下，考虑调用的结果root->right=NULL，root->right是一个TreeNode指针，可以置为NULL。然后该次调用会将root的结果返回，直到更新整个树。

参考

二叉搜索树中的插入操作

回溯法

理论

回溯法（backtrack）常用于遍历列表所有子集，是 DFS 深度搜索一种，一般用于全排列，穷尽所有可能，遍历的过程实际上是一个决策树的遍历过程。时间复杂度一般 $O(N!)$，它不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。

常用模板如下，核心就是从选择列表里做一个选择，然后一直递归往下搜索答案，如果遇到路径不通，就返回来撤销这次选择。

1
2
3
4
5
6
7
8
9
result = []
func backtrack(选择列表,路径):
    if 满足结束条件:
        result.add(路径)
        return
    for 选择 in 选择列表:
        做选择
        backtrack(选择列表,路径)
        撤销选择

在这个模板中需要注意的有：

  1. 路径：也就是已经做出的选择
  2. 选择列表：也就是当前可以做的选择（可以使用可以遍历的下标范围或者标记是否访问过的数组来得到选择列表并避免回溯重复。若访问某一个元素的时候，前面的元素不在选择列表中，则可以使用前者，否则的话可以使用后者）
  3. 结束条件：也就是到达决策树底层，无法再做选择的条件

常见题目

78. 子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。

这道题明显是需要用回溯法解决的，因为要遍历所有可能的子集。因为不含重复元素，所以参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void subsetsCore(vector<vector<int>>& result, vector<int>& tmp, vector<int>& nums, int begin) {
    result.push_back(tmp);

    for(int i=begin; i<nums.size(); i++) {
        tmp.push_back(nums[i]);
        subsetsCore(result, tmp, nums, i+1);
        tmp.pop_back();
    }
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> tmp;

    subsetsCore(result, tmp, nums, 0);
    return result;
}

90. 子集 II

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。

该题和上一个题目的区别在于，本题的 nums 中是可能包含重复元素的。若还采用上一题的思路，会出现重复的子集。相比上一个题目，主要多了两个步骤：

  1. 将 nums 中的元素从小到大排序，这样可以保证相同的数字挨在一起
  2. 若i>begin && nums[i]==nums[i-1]则说明该次循环还在这一级，且出现了重复元素，直接跳过。其中i>begin保证只跳过同级的相同元素，而不同级的相同元素不会跳过

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void subsetsWithDupCore(vector<vector<int>>& res, vector<int>& tmp, vector<int>& nums, int begin) {
    res.push_back(tmp);
    
    for(int i=begin; i<nums.size(); i++) {
        // 只跳过同级的相同元素，而不同级的相同元素不会跳过
        if(i>begin && nums[i]==nums[i-1])
            continue;
        tmp.push_back(nums[i]);
        subsetsWithDupCore(res, tmp, nums, i+1);
        tmp.pop_back();
    }
}

vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    sort(nums.begin(), nums.end());  // 将元素从小到大排序，方便之后跳过重复元素
    vector<vector<int>> res;
    vector<int> tmp;
    subsetsWithDupCore(res, tmp, nums, 0);
    return res;
}

46. 全排列

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

因为这是一个全排列问题，在以后面数字作为首字母的时候，前面的数字也要遍历到，因此不能使用下标的变换去更新下一次的回溯范围，而只能使用标记是否访问过的数组。

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void permuteCore(vector<vector<int>>& res, vector<int>& tmp, vector<int>& flag, vector<int>& nums) {
    if(tmp.size() == nums.size()) {
        res.push_back(tmp);
        return;
    }

    for(int i=0; i<nums.size(); i++) {
        if(flag[i] == 1)
            continue;
        flag[i] = 1;
        tmp.push_back(nums[i]);
        permuteCore(res, tmp, flag, nums);
        tmp.pop_back();
        flag[i] = 0;
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> tmp;
    vector<int> flag(nums.size(), 0);
    permuteCore(res, tmp, flag, nums);
    return res;
}

47. 全排列 II

给定一个可包含重复数字的序列，返回所有不重复的全排列。

该题和上一题的区别在于该题的序列可能包含重复数字。按照 90. 子集 II 的解题思路，并结合上一题的解法：

  1. 将序列从小到大进行排序，这样可以让重复数字放在一块
  2. i>0 && !flag[i-1] && nums[i]==nums[i-1]保证若处于不同层次的循环，且相邻两个元素相等，则不需要进行回溯了。

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void permuteUniqueCore(vector<vector<int>>& res, vector<int>& tmp, vector<int>& flag, vector<int>& nums) {
    if(tmp.size() == nums.size()) {
        res.push_back(tmp);
        return;
    }
    
    for(int i=0; i<nums.size(); i++) {
        /* 需要跳过的有几种情况
        1. flag[i] 表示当前回溯路径第i个元素已经访问了
        2. !flag[i-1]表示已经处于上一层回溯了，此时需要判断是否与前一个元素值相等，相等的话就不用回溯了
        */
        if(flag[i] || (i>0 && !flag[i-1] && nums[i]==nums[i-1]))
            continue;
        
        flag[i] = 1;
        tmp.push_back(nums[i]);
        permuteUniqueCore(res, tmp, flag, nums);
        tmp.pop_back();
        flag[i] = 0;
    }
}

vector<vector<int>> permuteUnique(vector<int>& nums) {
    sort(nums.begin(), nums.end()); // 一定要排序
    vector<vector<int>> res;
    vector<int> flag(nums.size(), 0); // 注意大小，与nums元素一一对应
    vector<int> tmp;
    permuteUniqueCore(res, tmp, flag, nums);
    return res;
}

39. 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的数字可以无限制重复被选取。

说明：

  • 所有数字（包括 target）都是正整数。
  • 解集不能包含重复的组合。

这个题目有两个地方需要注意：数组 candidates无重复元素、每个元素可以使用多次。使用一个变量sum记录当前路径的累加和，若累加和等于target则停止并添加到最终结果中，若累加和大于target则停止。因为遍历到后面的元素后，前面的元素不在回溯路径中了，所以可以使用下标范围来得到选择列表。

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void combinationSumCore(vector<vector<int>>& res, vector<int>& tmp, vector<int>& candidates, int index, int target, int& sum) {
    if(sum >= target) {
        if(sum == target)
            res.push_back(tmp);
        return;
    }

    for(int i=index; i<candidates.size(); i++) {
        sum += candidates[i];
        tmp.push_back(candidates[i]);
        combinationSumCore(res, tmp, candidates, i, target, sum);  // 注意这里的index传参为i，因为数字可以无限制重复选取
        sum -= candidates[i];
        tmp.pop_back();
    }
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> res;
    vector<int> tmp;
    int sum = 0;
    combinationSumCore(res, tmp, candidates, 0, target, sum);
    return res;
}

40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。

说明：

  • 所有数字（包括目标数）都是正整数。
  • 解集不能包含重复的组合。

这个题目和上一个题目的区别在于：数组candidates可能含有重复元素、每个元素只能使用一次。根据前面的经验，处理重复元素的方法：

  1. 将 candidates 中的元素从小到大排序，这样可以保证相同的数字挨在一起
  2. 若i>index && candidates[i]==candidates[i-1]则说明该次循环还在这一级，且出现了重复元素，直接跳过。其中i>index保证只跳过同级的相同元素，而不同级的相同元素不会跳过

另外，因为每个元素只能使用一次，因此在进行下一次回溯的时候，下标需要加1。最终参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void combinationSumCore(vector<vector<int>>& res, vector<int>& tmp, vector<int>& candidates, int index, int target, int& sum) {
    if(sum >= target) {
        if(sum == target)
            res.push_back(tmp);
        return;
    }

    for(int i=index; i<candidates.size(); i++) {
        if(i>index && candidates[i]==candidates[i-1])
            continue;
        sum += candidates[i];
        tmp.push_back(candidates[i]);
        combinationSumCore(res, tmp, candidates, i+1, target, sum);  // 注意这里的index传参为i+1，因为数字可以只能选取一次
        sum -= candidates[i];
        tmp.pop_back();
    }
}

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end());
    vector<vector<int>> res;
    vector<int> tmp;
    int sum = 0;
    combinationSumCore(res, tmp, candidates, 0, target, sum);
    return res;
}

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

img

这个题目明显要使用回溯去解决，因为要从各个按键里面找到一个字母，然后组成结果，不存在优化的可能。

  1. 路径：使用vector记录
  2. 选择列表：当前按下数字对应的所有字母
  3. 结束条件：若当前路径的长度等于digits的长度，则将路径添加到最终路径，终止本次回溯

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void letterCombinationsCore(vector<string>& res, string& digits, unordered_map<char, string>& m, string& tmpS, int index) {
    if(index == digits.size()) {
        res.push_back(tmpS);
        return;
    }
    // 得到当前数字对应的字母
    string s = m[digits[index]];
    for(int i=0; i<s.size(); i++) {
        tmpS.push_back(s[i]);
        letterCombinationsCore(res, digits, m, tmpS, index+1);
        tmpS.pop_back();
    }
}

vector<string> letterCombinations(string digits) {
    vector<string> res;
    if(digits.size() == 0)
        return res;
    
    unordered_map<char, string> m{
        {'2', "abc"},
        {'3', "def"},
        {'4', "ghi"},
        {'5', "jkl"},
        {'6', "mno"},
        {'7', "pqrs"},
        {'8', "tuv"},
        {'9', "wxyz"}
    };

    string tmpS;
    letterCombinationsCore(res, digits, m, tmpS, 0);
    return res;
}

131. 分割回文串

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

这道题可以使用回溯法解决。

  1. 路径：使用vector<string>记录当前所有回文子串
  2. 选择列表：从当前索引到 s.size()-1 均可以当做子串的结尾；若当前子串为回文子串，则继续进行回溯
  3. 结束条件：当前索引已经等于s.size()了，则将当前路径添加到最终结果中

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
bool judge(const string& s, int i, int j) {  // 使用递归+双指针的方式判断是否为回文子串，代码更加简洁
    if(i >= j) return true;
    if(s[i++] == s[j--]) return judge(s, i, j);
    return false;
}

void partitionCore(vector<vector<string>>& result, int begin, vector<string>& tmp, string& s) {
    if(begin == s.size()) {
        result.push_back(tmp);
        return;
    }

    for(int i=begin; i<s.size(); i++) {  // 每一个索引都可以作为当前子串的结尾索引
        if(judge(s, begin, i)) {  // 若为回文子串，则继续进行回溯；否则进行下一个循环
            tmp.push_back(s.substr(begin, i-begin+1));;
            partitionCore(result, i+1, tmp, s);
            tmp.pop_back();
        }
    }
}

vector<vector<string>> partition(string s) {
    vector<vector<string>> result;
    vector<string> tmp;
    partitionCore(result, 0, tmp, s);
    return result;
}

93. 复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。例如：”0.1.2.201” 和 “192.168.1.1” 是 有效的 IP 地址，但是 “0.011.255.245”、”192.168.1.312” 和 “192.168@1.1” 是 无效的 IP 地址。

这个题目比较复杂，借助这道题和大佬的讲解。这里详细讲解一下回溯算法的分析步骤。

回溯算法事实上就是在一个树形问题上做深度优先遍历，因此 首先需要把问题转换为树形问题。在画树形图的过程中，一定会发现有些枝叶是没有必要的，把没有必要的枝叶剪去的操作就是剪枝，在代码中一般通过 break 或者 contine 和 return （表示递归终止）实现。画出本题的树形图如下图所示：

「力扣」第 93 题：复原 IP 地址-1.png

  1. 路径：这个题目麻烦的地方是IP地址之间要用.进行分割，若用string存储路径，则比较麻烦，不如直接使用vector<string>进行记录，记录完毕之后若满足条件，则再拼接到一块
  2. 选择列表：因为已经遍历过的元素，以后不会在出现了，因为可以使用下标记录下一次访问的位置。每次回溯的时候，可遍历的子串长度在[1,3]之间。并且需要排除如下几种情况
    • 若子串长度+当前下标-1>=.size()
    • 0x、0xx都是非法的
    • 子串的数值不能大于255
  3. 结束条件：
    • 若遍历完所有的s，并且已经有四段合法字符串了，则记为有效结果，结束
    • 若没有遍历完s，并且已经有四段合法字符串了，则记为无效结果，结束

参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void DFS(vector<string>& res, vector<string>& tmp, string &s, int start) {
    if(start==s.size() && tmp.size()==4) { // tmp有四段，并且遍历完s了
        string str = tmp[0];  // 这样写可以保证最后不会多一个 .
        for(int i=1; i<tmp.size(); i++)
            str = str + '.' + tmp[i];
        res.push_back(str); // 其中一种可行方案
        return;
    }
    else if(start<s.size() && tmp.size()==4)  // tmp有四段，并且没有遍历完s
        return;
    
    for(int len=1; len<=3; len++) {
        if(len+start-1 >= s.size())
            return;
        if(len!=1 && s[start]=='0')  // 0x，00x非法
            return;
        string str = s.substr(start, len);
        if(len==3 && atoi(str.c_str())>255)
            return;
        tmp.push_back(str);
        DFS(res, tmp, s, start+len);
        tmp.pop_back();
    }
}

vector<string> restoreIpAddresses(string s) {
    vector<string> res;
    vector<string> tmp;
    DFS(res, tmp, s, 0);
    return res;
}

参考

回溯算法解题套路框架
C++ 双百回溯写法
回溯算法（画图分析剪枝条件）
『手画图解』DFS 回溯 细节

参考

Sort List （归并排序链表）
【LeetCode】代码模板，刷题必会
labuladong的算法小抄
algorithm-pattern

------ 本文结束------
坚持原创技术分享，您的支持将鼓励我继续创作！

欢迎关注我的其它发布渠道