LYL's Blog
0%

leetcode刷题系列之队列和栈

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

这篇文章是leetcode刷题系列的第5部分——队列和栈。这里把有代表性的题目发出来，共计22道。主要涉及BFS算法、DFS算法、单调栈以及单调队列技巧的应用。

leetcode刷题系列其它文章组织如下：

1. 数组

2. 链表

3. 字符串

4. 二叉树

5. 队列和栈

6. 动态规划

7. 数据结构设计

8. 刷题小知识点

1660. Correct a Binary Tree

你有一棵二叉树，这棵二叉树有个小问题，其中有且只有一个无效节点，它的右子节点错误地指向了与其在同一层且在其右侧的一个其他节点。

给定一棵这样的问题二叉树的根节点root，将该无效节点及其所有子节点移除（不移除被错误指向的节点），然后返回新二叉树的根结点。

示例:

img 
1
2
3
输入: root = [8,3,1,7,null,9,4,2,null,null,null,5,6], fromNode = 7, toNode = 4
输出: [8,3,1,null,null,9,4,null,null,5,6]
解释: 值为 7 的节点是无效的，所以移除这个节点及其子节点 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
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
// 借助层序遍历的思想
// 如果遍历到某一个节点, 发现其右孩子已经访问过了
// 就说明当前节点就是无效节点
// 但此时需要记录已经访问过的节点
// 如果要把此无效节点删除, 还要知道当前节点的父节点
// 因此, 使用一个哈希表记录所有访问过的节点以及这些节点的父节点
// 哈希表的映射有点特殊, 因为我们想达到这样的效果 mapping[node] == node's parent
// 因此, 每次访问一个节点 node 时
// 以 node 为值, 分别以其左右孩子(如果存在的话)为键加入哈希表
TreeNode* correctBinaryTree(TreeNode* root)
{
    // 队列仅仅用于完成层序遍历
    queue<TreeNode*> q;
    // 当前节点和其父亲的映射的哈希表
    unordered_map<TreeNode*, TreeNode*> mapping;
    if(root) q.push(root);
    // 标记是否找到了无效节点, 可用于提前结束遍历
    bool flag = false;
    while(!q.empty() && !flag)
    {
        int sz = q.size();
        for(int i = 0; i < sz; i++)
        {
            TreeNode* node = q.front();
            q.pop();
            // 以上都是标准的层序遍历迭代实现的固定框架
            
            // 如果当前节点的右孩子已经遍历过了
            // 说明找到无效节点
            if(mapping.count(node->right))
            {
                if(mapping[node]->left == node)
                    // 如果当前节点是其父节点的左孩子
                    mapping[node]->left = nullptr;
                else
                    // 否则是右孩子
                    mapping[node]->right = nullptr;
                flag = true;
                break;
            }
            else
            {
                // 否则继续遍历就是了
                if(node->left) 
                {
                    mapping[node->left] = node;
                    q.push(node->left);
                }
                if(node->right)
                {
                    mapping[node->right] = node;
                    q.push(node->right);
                }
            }
        }
    }
    
    return root;
}
394. Decode String

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的encoded_string正好重复k次。注意k保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数k ，例如不会出现像3a或2[4]的输入。

Constraints:

  • 1 <= s.size() <= 30
  • s consists of lowercase English letters, digits, and square brackets '[]'.
  • s is guaranteed to be a valid input.
  • All the integers in s are in the range [1, 300].

Example 1:

1
2
Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Example 2:

1
2
Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
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
void repeatString(string& str, int count)
{
    string s = str;
    while(--count) str = s + str;
}

string decodeString(string str)
{
    unordered_set<string> isdigits{"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"};
    stack<string> s;

    for(char c : str)
    {
        if(c == ']')
        {
            string substr;
            
            while(!s.empty() && s.top() != "[")
            {
                substr = s.top() + substr;
                s.pop();
            }
            s.pop(); // pop 掉相匹配的那个 '['
            // 获取 [] 前面的那个数字, 注意可能是多位数
            string numstr;
            while (!s.empty() && isdigits.count(s.top()))
            {
                numstr = s.top() + numstr;
                s.pop();
            }
            // 将 [] 中的字串重复指定次
            repeatString(substr, stoi(numstr));
            // 新串再次入栈
            s.push(substr);
        }
        else s.push(string(1, c));

    }
    // 这时从栈底到栈顶的所有串连在一起其实就是答案了
    // 但是要转为 string 返回
    string res;
    while(!s.empty())
    {
        res = s.top() + res;
        s.pop();
    }
    return res;
}
752. Open the Lock

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'。每个拨轮可以自由旋转：例如把'9'变为'0'，'0'变为'9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为'0000' ，一个代表四个拨轮的数字的字符串。

列表deadends包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串target代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回-1。

Example 1:

1
2
3
4
5
6
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
Explanation:
A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end "0102".

Example 2:

1
2
3
4
5
Input: deadends = ["8888"], target = "0009"
Output: 1
Explanation:
We can turn the last wheel in reverse to move from "0000" -> "0009".

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
// 宽度优先遍历 BFS 通常用来解决最小(距离)、最短(路径)、最少(步数)等问题
// 先给出 BFS 算法框架
// 计算从 [开始状态] 到 [目标状态]的最近距离
int BFS(STATE startState, STATE targetState)
{
    queue<STATE> q; // 核心数据结构
    unordered_map<STATE> visited; // 避免走回头路

    q.push(startState); // 将起点加入队列
    visited.insert(startState);
    int step = 0; // 记录扩散的步数
    
    while(!q.empty())
    {
        int sz = q.size();
        /* 将当前队列中的所有状态分别向其所有相邻状态转换 */
        for (int i = 0; i < sz; i++)
        {
            STATE curState = q.front();
            q.pop();
            // 下面代码是需要你根据实际问题的逻辑做调整的
            /***************************************/
            /* 划重点: 这里判断是否到达终点 */
            if (curState is targetState) return step;
            /* 将 cur 的所有相邻状态加入队列 */
            for (STATE state : all adjacent states of curState )
            {
                if (state not in visited)
                {
                    q.push(state);
                    visited.insert(state);
                }
            }
            /***************************************/
        }
        /* 划重点: 更新步数在这里 */
        step++;
    }
    return step;
}

// 对于我们这题打开密码锁的问题
// 就是穷举所有的密码组合, 直到到达目标密码
// 密码锁初始值(开始状态)为 "0000", 一共四个位置, 每个位置可以向上或向下拨动, 也就是有 8 个相邻状态
int openLock(vector<string>& deadends, string target)
{
    queue<string> q;
    unordered_set<string> visited;
    unordered_set<string> deads;
    // 将死亡密码加入哈希集合
    // 其实这里是可以直接用 visited, 就是说直接把死亡密码看作已经被访问过了, 一样的
    for(auto elem : deadends)
        deads.insert(elem);

    q.push("0000");
    visited.insert("0000");

    int step = 0;

    while(!q.empty())
    {
        int qSize = q.size();
        for(int i = 0; i < qSize; i++)
        {
            // 从队列中取出一个状态访问
            string curLock = q.front();
            q.pop();
            // 如果当前状态在死亡状态里面
            // 说明我们不能够到达这个状态
            // 因此也就不可能从这个状态向其它相邻状态转换
            // 继续取出队列中的下一个状态
            if(deads.count(curLock)) continue;
            // 如果当前状态是目标状态了
            if(curLock == target) return step;
            // 否则, 向相邻的 8 个状态转换
            for(int j = 0; j < 4; j++)
            {
                // 将第 j 个字符向上拨动
                string upRotate = rotate(curLock, j, 1);
                if(!visited.count(upRotate))
                {
                    q.push(upRotate);
                    visited.insert(upRotate);
                }
                // 将第 j 个字符向下拨动
                string downRotate = rotate(curLock, j, 0);
                if(!visited.count(downRotate))
                {
                    q.push(downRotate);
                    visited.insert(downRotate);
                }
            }
        }
        step++;
    }
    return -1;
}

// direction 为 1 向上拨动, 为 0 则向下拨动
string rotate(string theLock, int position, bool direction)
{
    if(direction)
    {
        if(theLock[position] == '9')
        {
            theLock[position] = '0';
            return theLock;
        }
        theLock[position]++;
        return theLock;
    }
    else
    {
        if(theLock[position] == '0')
        {
            theLock[position] = '9';
            return theLock;
        }
        theLock[position]--;
        return theLock;
    }
}
37. Sudoku Solver

编写一个程序，通过填充空格来解决数独问题。

一个数独的解法需遵循如下规则：

  1. 数字1-9在每一行只能出现一次。
  2. 数字1-9在每一列只能出现一次。
  3. 数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。空白格用'.'表示。
一个数独 红色为答案
img img 
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
// 这是深度优先搜索算法应用的典型题目
// 
void solveSudoku(vector<vector<char>>& board)
{
    dfs(board, 0, 0);
}

bool dfs(vector<vector<char>>& board, int row, int col)
{
    // 如果当前行填写完了, 就到下一行
    if(col == board.size()) return dfs(board, row + 1, 0);
    // 如果最后一行也填完了, 就说明找到了数独的一个解
    if(row == board.size()) return true;
    // 如果当前格子中已经有数了就跳过这个格子
    if(board[row][col] != '.') return dfs(board, row, col + 1);
    // 针对当前格子
    // 从数字 1 到 9 依次尝试
    for(char c = '1'; c <= '9'; c++)
    {
        // 如果当前格子放置这个数字不符合那 3 条规则就跳过
        if(!isValid(board, row, col, c)) continue;
        // 做选择
        board[row][col] = c;
        // 这里的 if 语句可以在找到一组解的时候立即返回
        // 不至于找到所有可能的解
        if(dfs(board, row, col + 1)) return true;
        // 撤销选择
        board[row][col] = '.';
    }

    return false;
}

bool isValid(vector<vector<char>>& board, int row, int col, char c)
{
    for(int i = 0; i < board.size(); i++)
    {
        // 当前行不能有数字重复
        if(board[row][i] == c) return false;
        // 当前列不能有数字重复
        if(board[i][col] == c) return false;
        // 当前格子所在的九宫格不能有数字重复
        // 这特么还真不好写, 看不懂就背下吧
        if(board[(row / 3) * 3 + i / 3][(col / 3) * 3 + i % 3] == c) return false;
    }

    return true;
}
279. Perfect Squares

给定正整数n，找到若干个完全平方数（比如1, 4, 9, 16, ...）使得它们的和等于n。你需要让组成和的完全平方数的个数最少。

给你一个整数n ，返回和为n的完全平方数的最少数量。

Example 1:

1
2
3
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

1
2
3
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
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
// DP 递推式: numSquares(n) = min(numSquares(n - k)) + 1
// 有点 找零钱 那题的那味儿
int numSquares(int n)
{
    vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;

    vector<int> squares;
    // 先计算出所有符合条件的完全平方数
    for(int i = 1; i * i <= n; i++)
        squares.push_back(i * i);

    for(int i = 1; i <= n; i++)
    {
        for(int square : squares)
        {
            if(i - square < 0) break;
            dp[i] = min(dp[i], dp[i - square]);
        }
        dp[i]++;
    }

    return dp[n];
}

// 穷举所有完全平方数相加的组合, 直到一组的和等于目标数
// 因为要找用到的 [最少的] 完全平方数, 所以使用 BFS
// 第 1 轮: 搜索所有 1 位数字判断是否满足
// 将 0 + (1, 2, 4, 9, ...) 的数字依次放进队列中
// 第 2 轮: 搜索所有 2 位数字的和并判断是否满足
// 将 1 + (1, 2, 4, 9, ...) 的数字依次放进队列中
// 将 2 + (1, 2, 4, 0, ...) 的数字依次放进队列中
// ...
// 第 3 轮: 搜索所有 3 位数字和并判断是否满足
// ...
// 你会发现我们穷举的时候遇到了大量同样的数字组合, 因此使用一个哈希集合来跳过它们
int numSquares(int n)
{
    queue<int> q;
    unordered_set<int> visited;

    q.push(0);
    int step = 0;
    
    while(!q.empty())
    {
        int sz = q.size();
        for(int i = 0; i < sz; i++)
        {
            int cur = q.front();
            q.pop();

            if(cur == n) return step;
            // 直到完全平方数大于目标数
            // 这里的循环相当于是找当前值的所有可能的邻居
            for(int j = 1; j * j <= n; j++)
            {
                int temp = cur + j * j;
                // 如果完全平方数的和还小于目标数
                // 或者这个和没有被访问, 才加入队列
                if(temp <= n && !visited.count(temp))
                {
                    q.push(temp);
                    visited.insert(temp);
                }
            }
        }
        step++;
    }
    return -1;
}
155. Min Stack

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

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

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
class MinStack
{
public:
    /** initialize your data structure here. */
    MinStack() : _minVal(INT_MIN) {}
    
    void push(int x)
    {
        if(x < _minVal || _data.empty()) _minVal = x;
        _data.push_back(x);
    }
    
    void pop()
    {
        if(_data.empty()) return;
        if(_data.back() == _minVal)
            _minVal = *min_element(_data.begin(), _data.end() - 1);
        
        _data.pop_back();
    }
    
    int top()
    {
        return _data.back();
    }
    
    int getMin()
    {
        return _minVal;
    }

private:
    vector<int> _data;
    int _minVal;
};
739. Daily Temperatures

请根据每日气温列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用0来代替。

例如，给定一个列表temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是[1, 1, 4, 2, 1, 1, 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
// 这题本质上就是找到当前元素的下一个比它大的元素
// 然后两者的索引相减即可
// 像这样和下一个更大元素有关的问题都需要使用一种单调栈的技巧
// 就是说维护一个栈, 使其中的元素保持单调的次序
// 下面的代码就是单调栈的模板
// 这里维护着从栈底到栈顶递减的次序
vector<int> dailyTemperatures(vector<int>& T)
{
    // 存放答案的数组
    vector<int> res(T.size());
    stack<int> s;
    // 倒着遍历入栈, 因此也就是正着出栈
    for(int i = T.size() - 1; i >= 0; i--)
    {
        // 如果当前元素比栈首元素大
        // 那么栈的首元素出栈让出位子
        // 直到首元素比当前元素大了才把当前元素压入栈
        // 注意这里栈内放的是索引
        while(!s.empty() && T[s.top()] <= T[i])
            s.pop();
        // 更新数组中第 i 个元素的下一个更大的元素
        // 就在栈首
        res[i] = s.empty() ? 0 : (s.top() - i);
        s.push(i);
    }
    return res;
}
496. Next Greater Element I

给你两个没有重复元素的数组nums1和nums2，其中nums1是nums2的子集。

请你找出nums1中每个元素在nums2中的下一个比其大的值。

nums1中数字x的下一个更大元素是指x在nums2中对应位置的右边的第一个比x大的元素。如果不存在，对应位置输出-1 。

Example:

1
2
3
4
5
6
Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation:
For number 4 in the first array, you cannot find the next greater number for it in the second array, so output -1.
For number 1 in the first array, the next greater number for it in the second array is 3.
For number 2 in the first array, there is no next greater number for it in the second array, so output -1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 直接套用单调栈的模板
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2)
{
    // 这里用哈希表来存放答案
    // 记录着 nums2 数组中的每个元素与其下一个更大的元素之间的映射
    unordered_map<int, int> mapping;
    stack<int> s;
    for(int i = nums2.size() - 1; i >= 0; i--)
    {
        while(!s.empty() && s.top() <= nums2[i])
            s.pop();
        mapping[nums2[i]] = s.empty() ? -1 : s.top();
        s.push(nums2[i]);
    }
    vector<int> res(nums1.size());
    // 直接从哈希表中获取 nums1 数组中元素的下一个更大元素即可
    for(int i = 0; i < nums1.size(); i++)
        res[i] = mapping[nums1[i]];
    return res;
}
503. Next Greater Element II

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字x的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出-1。

2

Example:

1
2
3
>Input: [1,2,1]
>Output: [2,-1,2]
>Explanation: The first 1's next greater number is 2; The number 2 can't find next greater number; The second 1's next greater number needs to search circularly, which is also 2.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 这里和 I 题的区别是, 数组可以循环
// 也就是说从当前位置一直向后看去, 直到找到下一个更大元素为止
// 如果找到了尾元素则从首元素开始继续找
// 可以看作在原始数组后面又接了一段原始数组(见上图)
// 你当然可以申请一段两倍的数组空间来这放元素
// 但是, 下面来学习一个循环遍历数组的技巧

// 先直接套用单调栈的模板
// 其中改动的地方就是能够循环遍历数组的技巧
vector<int> nextGreaterElements(vector<int>& nums)
{
    vector<int> res(nums.size());
    stack<int> s;
    int n = nums.size();
    for(int i = 2 * n - 1; i >= 0; i--)
    {
        while(!s.empty() && s.top() <= nums[i % n])
            s.pop();
        res[i % n] = s.empty() ? -1 : s.top();
        s.push(nums[i % n]);
    }
    return res;
}
556. Next Greater Element III

给你一个正整数n，请你找出符合条件的最小整数，其由重新排列n中存在的每位数字组成，并且其值大于n。如果不存在这样的正整数，则返回-1。

Example 1:

1
2
Input: n = 320241
Output: 320412

Example 2:

1
2
Input: n = 321
Output: -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
34
35
36
37
// 首先要想到的是先把数字转成字符串, 方便处理
// 然后再试想一下, 影响数值前后发生大小变化的决定因素什么
// 不知道你脑子里有没有蹦出 [逆序对] 三个字
// 注意我这里的 [逆序对] 是指, 原本降序排列的数, 其中相邻的一对数字是升序
// 如果你想到了这个, 那问题就很简单了
// 对于数字其中的一个逆序对
// 如果你把这两个数字交换, 值是不是就变大了？
// 但这题要找变大之后的数中最小的数
// 那就只需要对最后边的一个逆序对操作嘛
// 但是还是不能简单的将逆序对的数字交换
// 需要将逆序对的前一个元素和它后面的最后一个比它大的数交换才行
// 交换完之后还要将逆序对后面的所有元素进行一次反转
// 因为此时后面的那些元素必定是降序排列的, 反转之后值会进一步变小
// 说起来太抽象了, 下面直接看代码
int nextGreaterElement(int n)
{
    string s(to_string(n));
    // 从后往前走
    // 定位到第一个逆序对, pivot 指向逆序对的第一个元素
    int pivot = s.size() - 2;
    for(; pivot >= 0; pivot--)
        if(s[pivot] < s[pivot + 1]) break;
    // 如果没有逆序对, 说明不可能组合成比原来大的数
    if(pivot == -1) return -1;
    // 从后往前走, 定位到第一个比 pivot 指向元素大的元素
    int larger = s.size() - 1;
    for(; larger > pivot; larger--)
        if(s[pivot] < s[larger]) break;
    // 交换二者
    swap(s[pivot], s[larger]);
    // 这时候 pivot 之后的所有元素肯定是降序排列的
    // 反转它们, 以求数值最小
    reverse(s.begin() + pivot + 1, s.end());
    // 如果这个数比 int 类型数值范围, 就不符合题目要求了
    if(stol(s) > INT_MAX) return -1;
    return stoi(s);
}
133. Clone Graph

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

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

1
2
3
4
5
6
7
8
9
10
11
// Definition for a Node.
struct Node
{
   int val;
   vector<Node *> neighbors;
   Node(int _val)
   {
       val = _val;
       neighbors = vector<Node *>();
   }
};

Example:

img 
1
2
3
4
5
6
7
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 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
// 直接深度优先搜索即可
// 只是需要使用一个哈希表来记录已经 new 过的节点
// 哈希表中记录的是原节点和拷贝节点之间的映射
// 下次通过某节点的邻居遍历到相同的节点直接从哈希表中取就可以了
Node* cloneGraph(Node* node)
{
    if(!node) return nullptr;

    unordered_map<Node*, Node*> visited;
    return dfs(node, visited);
}

Node* dfs(Node* node, unordered_map<Node*, Node*>& visited)
{
    // 如果这个节点已经 被克隆过了
    // 直接从哈希表中返回其映射
    if(visited.count(node)) return visited[node];
    // 克隆当前节点
    Node* res = new Node(node->val);
    // 记录映射
    visited[node] = res;
    // 深度遍历其所有邻居
    vector<Node*> neighbors = node->neighbors;
    for(int i = 0; i < neighbors.size(); i++)
        // 将其一一添加进拷贝节点的邻居中
        res->neighbors.push_back(dfs(neighbors[i], visited));

    return res;
}
494. Target Sum

给定一个非负整数数组，a1, a2, ..., an和一个目标数S。现在你有两个符号+和-。对于数组中的任意一个整数，你都可以从+或-中选择一个符号添加在前面。

返回可以使最终数组和为目标数S的所有添加符号的方法数。

Example:

1
2
3
4
5
6
7
8
9
10
11
Input: nums is [1, 1, 1, 1, 1], S is 3. 
Output: 5
Explanation: 

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

There are 5 ways to assign symbols to make the sum of nums be target 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// 先上暴力搜索 (dfs) 穷举所有添加方法的结果
// 时间复杂度为 O(2^n), n 为数组长度
// 空间复杂度为 O(n) 递归调用栈的空间
int count = 0;
int findTargetSumWays(vector<int>& nums, int S)
{
    dfs(nums, 0, S);
    return count;
}
// 注意这里用到的一个技巧是
// 等式左边的数相加或相减起来 = S, 等价于 S + 等式左边的那些数相加或相减 = 0
// 它们的个数肯定相等嘛
void dfs(vector<int>& nums, int pos, long S)
{
    if(pos == nums.size())
    {
        if(S == 0) count++;
        return;
    }

    // S += nums[pos]; // 做选择
    // dfs(nums, pos + 1, S);
    // S -= nums[pos]; // 撤销选择
    dfs(nums, pos + 1, S + nums[pos]); // 函数进入自动做选择, 返回自动撤销选择

    // S -= nums[pos]; // 做选择
    // dfs(nums, pos + 1, S);
    // S += nums[pos]; // 撤销选择
    dfs(nums, pos + 1, S - nums[pos]); // 函数进入自动做选择, 返回自动撤销选择
}

// 我们从上面可以注意到递归过程中出现了许多的重复计算
// 比如, nums[pos] == 0 的时候, dfs(num, pos + 1, S) 要计算 2 次
// 除了这种特殊情况还有许多
// 这里我们就使用备忘录来消除重叠子问题
unordered_map<string, int> memo;
int findTargetSumWays(vector<int>& nums, int S)
{
    return dfs(nums, 0, S);
}
// 需要修改一下递归函数的定义
// int dfs(vector<int>& nums, pos, int S)
// 表示在 pos 位置加正负号使其和等于 S 有多少种方法
// 这样递推式就是 dfs(.., pos, S) = 
// dfs(.., pos + 1, S + nums[pos]) /* pos 位置加正号的话 */
//  + dfs(.., pos + 1, S - nums[pos]) /* pos 位置加负号的话 */
int dfs(vector<int>& nums, int pos, int S)
{
    if(pos == nums.size())
    {
        if(S == 0) return 1;
        return 0;
    }
    // 需要将这两个参数转为字符串作为哈希表的键
    // 把 [状态] 转化为字符串作为键是一种小技巧
    string key = to_string(pos) + "," + to_string(S);
    if(memo.count(key)) return memo[key];
    int res = dfs(nums, pos + 1, S + nums[pos]) + dfs(nums, pos + 1, S - nums[pos]);
    memo[key] = res;
    return res;
}

// 从上面使用的优化方法来看
// 似乎有 [动态规划] 的影子
// 现在让我们再转化一下思路
232. Implement Queue using Stacks

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作：

实现MyQueue类：

void push(int x)：将元素x推到队列的末尾；
int pop()：从队列的开头移除并返回元素；
int peek()：返回队列开头的元素；
bool empty()：如果队列为空，返回true；否则，返回false。

img 
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
// 如上图, 将两个栈这样放
class MyQueue
{
public:
    /* Initialize your data structure here. */
    MyQueue() {}
    
    /* Push element x to the back of queue. */
    void push(int x)
    {
        // 入栈的时候直接放进右边的栈即可
        _back.push(x);
    }
    
    /* Removes the element from in front of queue and returns that element. */
    int pop()
    {
        // 出栈的时候从左边出
        // 如果为空, 需要把右边栈的元素搬过来
        if(_front.empty()) moveData();
        // 搬过来之后直接 pop 左边的栈即可
        int res = _front.top();
        _front.pop();
        return res;
    }
    
    /* Get the front element. */
    int peek()
    {
        // 取的时候和 pop 的情况一样
        if(_front.empty()) moveData();
        // 只是不出栈, 只取元素
        return _front.top();
    }
    
    /* Returns whether the queue is empty. */
    bool empty()
    {
        return _front.empty() && _back.empty();
    }
    
private:
    stack<int> _front;
    stack<int> _back;
    
    void moveData()
    {
        // 搬移数据就是简单的将右边栈出栈
        // 左边栈接收元素压入栈
        while(!_back.empty())
        {
            _front.push(_back.top());
            _back.pop();
        }
    }
};
225. Implement Stack using Queues

请你仅使用两个队列实现一个后入先出的栈，并支持普通队列的全部四种操作。

实现MyStack类：

void push(int x)：将元素x压入栈顶；
int pop()：移除并返回栈顶元素；
int top()：返回栈顶元素；
bool empty()：如果栈是空的，返回true；否则，返回false。

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
// 队列实现栈
// 入栈操作很简单, 调用队列的 push 即可
// 出栈麻烦点, 因为队列只能从对头出列, 对头相当于栈的栈底
// 但我们是想 pop 掉队尾元素
// 这时很暴力, 直接把队列中除了队尾之外的所有元素依次出队并依次入队即可
// 这时对头就是原队尾元素了, 再出队就行
// 获取栈顶元素的话, 为了实现 O(1) 复杂度
// 使用一个变量实时记录队尾 (栈顶) 元素
class MyStack
{
public:
    /* Initialize your data structure here. */
    MyStack() {}
    
    /* Push element x onto stack. */
    void push(int x)
    {
        // 入队的时候要更新栈顶变量
        _top = x;
        _queue.push(x);
    }
    
    /* Removes the element on top of the stack and returns that element. */
    int pop()
    {
        int sz = _queue.size();
        while(sz-- > 1)
        {
            _top = _queue.front();
            _queue.pop();
            _queue.push(_top);
        }
        
        int res = _queue.front();
        _queue.pop();
        return res;
    }
    
    /* Get the top element. */
    int top()
    {
        return _top;
    }
    
    /* Returns whether the stack is empty. */
    bool empty()
    {
        return _queue.empty();
    }

private:
    queue<int> _queue;
    int _top;
};
200. Number of Islands

给定一个m x n字符栅格网格，该栅格网格表示'1'（土地）和'0'（水）的地图，请返回岛的数量。

一个岛屿被水包围，是通过水平或垂直连接相邻的土地而形成的。 您可以假设网格的所有四个边缘都被水包围。

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'

Example 1:

1
2
3
4
5
6
7
Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

1
2
3
4
5
6
7
Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 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
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// 思想是
// 1. 依次遍历网格中的每一个字符
// 2. 如果当前字符是 '1' 说明踏上了一座岛, 进行下一步, 如果为 '0'，回到步骤 1
// 3. 然后骚操作来了, 将当前字符赋值为 '0'
// 4. 然后遍历当前字符的上下左右四个邻居
// 5. 每到一个邻居重复对当前字符的操作
// 6. 直到某一个邻居 (可以是邻居的邻居) 的四个邻居都为'0'
// 7. 说明这座岛的每一个陆地都走过了, 此时岛数量 +1
// 8. 接下来再到下一个字符, 回到步骤 1
// 遍历邻居的时候有两种方法, dfs 和 bfs

// dfs
int numIslands(vector<vector<char>>& grid)
{
    int count = 0;
    for(int i = 0; i < grid.size(); i++)
    {
        for(int j = 0; j < grid[0].size(); j++)
        {
            if(grid[i][j] == '1')
            {
                // 踏上了一座岛
                count++;
                // 递归函数的目的把这座岛的所有陆地变成水 (淹没)
                dfs(grid, i, j);
            }
        }
    }
    return count;
}

void dfs(vector<vector<char>>& grid, int r, int c)
{
    if(r < 0 || c < 0 || r == grid.size() || c == grid[0].size() || grid[r][c] != '1')
        return;
    // 淹没陆地
    grid[r][c] = '0';
    // 判断左邻居
    dfs(grid, r - 1, c);
    // 判断右邻居
    dfs(grid, r + 1, c);
    // 判断上邻居
    dfs(grid, r, c - 1);
    // 判断下邻居
    dfs(grid, r, c + 1);
}

// bfs 借助队列的迭代实现
int numIslands(vector<vector<char>>& grid)
{
    if(grid.empty()) return 0;

    // 队列中保存的是当前陆地的坐标
    queue<pair<int, int>> q;
    int count = 0;
    for(int i = 0; i < grid.size(); i++)
    {
        for(int j = 0; j < grid[0].size(); j++)
        {
            if(grid[i][j] == '1')
            {
                // 踏上了一座岛
                count++;
                q.push({i, j});
                // while 循环的目的是把这座岛的所有陆地变成水 (淹没)
                while(!q.empty())
                {
                    int r = q.front().first;
                    int c = q.front().second;
                    q.pop();
                    
                    if(r < 0 || c < 0 || r == grid.size()
                       	|| c == grid[0].size() || grid[r][c] != '1')
                        continue;
                    
                    // 淹没陆地
                    grid[r][c] = '0';
                    // 判断左邻居
                    q.push({r - 1, c});
                    // 判断右邻居
                    q.push({r + 1, c});
                    // 判断上邻居
                    q.push({r, c - 1});
                    // 判断下邻居
                    q.push({r, c + 1});
                }
            }
        }
    }
    return count;
}
694. Number of Distinct Islands

给定一个非空01二维数组表示的网格，一个岛屿由四连通（上、下、左、右四个方向）的1组成，你可以认为网格的四周被海水包围。

请你计算这个网格中共有多少个形状不同的岛屿。两个岛屿被认为是相同的，当且仅当一个岛屿可以通过平移变换（不可以旋转、翻转）和另一个岛屿重合。

示例 1：

1
2
3
4
5
11000
11000
00011
00011
给定上图，返回结果 1 。

示例 2：

1
2
3
4
5
11011
10000
00001
11011
给定上图，返回结果 3 。

注意：

11
1

和

1
11
是不同的岛屿，因为我们不考虑旋转、翻转操作。

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
int x = 0, y = 0;
int numDistinctIslands(vector<vector<int>>& grid)
{
    set<vector<pair<int, int>>> setting;
    for(int i = 0; i < grid.size(); i++)
    {
        for(int j = 0; j < grid[0].size(); j++)
        {
            if(grid[i][j] == 1)
            {
                // 踏上了一座岛
                // isLand 用于记录这座岛的所有陆地坐标
                // 实际记录的是相对陆地坐标, 即其他陆地相对于左上角的那块陆地
                vector<pair<int, int>> isLand;
                // 更新当前岛屿的相对坐标
                x = i;
                y = j;
                // 递归函数的目的把这座岛的所有陆地变成水 (淹没)
                dfs(grid, isLand, i, j);
                // set 有自动排序和去重的功能
                setting.insert(isLand);
            }
        }
    }
    return setting.size();
}

void dfs(vector<vector<int>>& grid, vector<pair<int, int>>& isLand, int r, int c)
{
    if(r < 0 || c < 0 || r == grid.size() || c == grid[0].size() || grid[r][c] != 1)
        return;
    
    isLand.push_back({r - x, c - y});
    // 淹没陆地
    grid[r][c] = 0;
    // 判断左邻居
    dfs(grid, isLand, r - 1, c);
    // 判断右邻居
    dfs(grid, isLand, r + 1, c);
    // 判断上邻居
    dfs(grid, isLand, r, c - 1);
    // 判断下邻居
    dfs(grid, isLand, r, c + 1);
}
1254. Number of Closed Islands

有一个二维矩阵grid，每个位置要么是陆地（记号为0）要么是水域（记号为1）。

我们从一块陆地出发，每次可以往上下左右4个方向相邻区域走，能走到的所有陆地区域，我们将其称为一座「岛屿」。

如果一座岛屿完全由水域包围，即陆地边缘上下左右所有相邻区域都是水域，那么我们将其称为 「封闭岛屿」。

请返回封闭岛屿的数目。

Example 1:

img

1
2
3
4
Input: grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
Output: 2
Explanation: 
Islands in gray are closed because they are completely surrounded by water (group of 1s).

Example 2:

img

1
2
Input: grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
Output: 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// 注意这题 1 代表水域而 0 代表陆地
// 和岛屿数量 I 题的区别在于边界上的岛屿不算岛屿
// 所以如果搜索出来的岛屿在边界上就不更新岛屿数
bool flag; // 是否是封闭岛的标志
int closedIsland(vector<vector<int>>& grid)
{
    int rowLength = grid.size();
    int colLength = grid[0].size();
    int count = 0;
    for(int i = 0; i < rowLength; i++)
    {
        for(int j = 0; j < colLength; j++)
        {
            if(grid[i][j] == 0)
            {
                // 踏上了一座岛
                // 看它是否是边界岛
                flag = true;
                // 递归函数的目的把这座岛的所有陆地变成水 (淹没)
                dfs(grid, i, j);
                if(flag) count++;
            }
        }
    }
    return count;
}

void dfs(vector<vector<int>>& grid, int r, int c)
{
    if(r < 0 || c < 0 || r == grid.size() || c == grid[0].size())
    {
        // 能到达边界, 说明不是封闭岛
        flag = false;
        return;
    }
    
    if(grid[r][c] != 0) return;
    
    // 淹没陆地
    grid[r][c] = 1;
    // 判断左邻居
    dfs(grid, r - 1, c);
    // 判断右邻居
    dfs(grid, r + 1, c);
    // 判断上邻居
    dfs(grid, r, c - 1);
    // 判断下邻居
    dfs(grid, r, c + 1);
}
695. Max Area of Island

给定一个包含了一些0和1的非 空二维数组grid。

一个岛屿是由一些相邻的1(代表土地) 构成的组合，这里的「相邻」要求两个1必须在水平或者竖直方向上相邻。你可以假设grid的四个边缘都被0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0 )

Example 1:

1
2
3
4
5
6
7
8
9
10
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]

Given the above grid, return `6`. Note the answer is not 11, because the island must be connected 4-directionally.

Example 2:

1
2
3
[[0,0,0,0,0,0,0,0]]

Given the above grid, return `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
35
36
37
38
// dfs
int area; // 用于记录每个岛的面积
int maxAreaOfIsland(vector<vector<int>>& grid)
{
    int res = 0;
    for(int i = 0; i < grid.size(); i++)
    {
        for(int j = 0; j < grid[0].size(); j++)
        {
            if(grid[i][j] == 1)
            {
                // 踏上了一座岛就把先前岛屿面积清零
                area = 0;
                // 递归函数的目的把这座岛的所有陆地变成水 (淹没)
                dfs(grid, i, j);
                res = max(res, area);
            }
        }
    }
    return res;
}

void dfs(vector<vector<int>>& grid, int r, int c)
{
    if(r < 0 || c < 0 || r == grid.size() || c == grid[0].size() || grid[r][c] != 1)
        return;
    // 淹没陆地
    grid[r][c] = 0;
    area++;
    // 判断左邻居
    dfs(grid, r - 1, c);
    // 判断右邻居
    dfs(grid, r + 1, c);
    // 判断上邻居
    dfs(grid, r, c - 1);
    // 判断下邻居
    dfs(grid, r, c + 1);
}
733. Flood Fill

有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在0到65535之间。

给你一个坐标(sr, sc)表示图像渲染开始的像素值（行 ，列）和一个新的颜色值newColor，让你重新上色这幅图像。

为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。

最后返回经过上色渲染后的图像。

Example:

1
2
3
4
5
6
7
8
9
Input: 
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
Output: [[2,2,2],[2,2,0],[2,0,1]]
Explanation: 
From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected 
by a path of the same color as the starting pixel are colored with the new color.
Note the bottom corner is not colored 2, because it is not 4-directionally connected
to the starting pixel.
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
// 和前面那个岛屿数量 I 的题思路差不多
// DFS
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor)
{
    if(image[sr][sc] != newColor)
        dfs(image, sr, sc, image[sr][sc], newColor);
    return image;
}

void dfs(vector<vector<int>>& image, int r, int c, int srcColor, int newColor)
{
    if(r < 0 || c < 0 || r == image.size() || c == image[0].size() || image[r][c] != srcColor)
        return;

    image[r][c] = newColor;
    dfs(image, r + 1, c, srcColor, newColor);
    dfs(image, r - 1, c, srcColor, newColor);
    dfs(image, r, c + 1, srcColor, newColor);
    dfs(image, r, c - 1, srcColor, newColor);
}

// BFS
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor)
{
    if(image[sr][sc] == newColor) return image;

    int srcColor = image[sr][sc];
    
    queue<pair<int, int>> q;
    q.push({sr, sc});

    while(!q.empty())
    {
        int sz = q.size();
        for(int i = 0; i < sz; i++)
        {
            int r = q.front().first;
            int c = q.front().second;
            q.pop();
            
            if(r < 0 || c < 0 || r == image.size() || c == image[0].size() || image[r][c] != srcColor)
                continue;
            
            image[r][c] = newColor;
            q.push({r + 1, c});
            q.push({r - 1, c});
            q.push({r, c + 1});
            q.push({r, c - 1});
        }
    }
    return image;
}
542. 01 Matrix

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

两个相邻元素间的距离为1。矩阵中的元素只在四个方向上相邻：上、下、左、右。

Example 1:

1
2
3
4
5
6
7
8
9
>Input:
>[[0,0,0],
>[0,1,0],
>[0,0,0]]

>Output:
>[[0,0,0],
>[0,1,0],
>[0,0,0]]

Example 2:

1
2
3
4
5
6
7
8
9
>Input:
>[[0,0,0],
>[0,1,0],
>[1,1,1]]

>Output:
>[[0,0,0],
>[0,1,0],
>[1,2,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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// 因为要寻找 [最近] 距离, 所以显然使用 BFS
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix)
{
    int rSize = matrix.size();
    int cSize = matrix[0].size();

    vector<vector<int>> res(rSize, vector<int>(cSize));
    queue<pair<int, int>> q;

    int step = 0;
    // 因为要对矩阵中的所有元素进行寻找最近的 0
    // 所以外面的两层循环实际上是处理这个问题的
    // 如果只需要对一个元素进行寻找就不需要这两层循环, 和传统的 BFS 模板一样
    for(int i = 0; i < rSize; i++)
    {
        for(int j = 0; j < cSize; j++)
        {
            step = 0;
            q.push({i, j});
            while(!q.empty())
            {
                int sz = q.size();
                while(sz--)
                {
                    // 从当前位置出发, 遍历其所有邻居
                    int r = q.front().first;
                    int c = q.front().second;
                    q.pop();
                    // 如果 走到了 0, 那么它离 0 的最近距离就是已经走的 step
                    if(matrix[r][c] == 0)
                    {
                        res[i][j] = step;
                        // 更新完 step 之后还要将队列清空方便对下一位置进行搜索时使用
                        while(!q.empty()) q.pop();
                        break;
                    }
                    // 将其上下左右四个邻居入栈等待搜索
                    if(r + 1 < rSize) q.push({r + 1, c});
                    if(r - 1 >= 0) q.push({r - 1, c});
                    if(c + 1 < cSize) mq.push({r, c + 1});
                    if(c - 1 >= 0) q.push({r, c - 1});
                }
                step++;
            }
        }
    }
    return res;
}
841. Keys and Rooms

有N个房间，开始时你位于0号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。

在形式上，对于每个房间i都有一个钥匙列表rooms[i]，每个钥匙rooms[i][j]由[0,1，...，N-1]中的一个整数表示，其中N = rooms.length。 钥匙rooms[i][j] = v可以打开编号为v的房间。

最初，除0号房间外的其余所有房间都被锁住。

你可以自由地在房间之间来回走动。

如果能进入每个房间返回true，否则返回false。

Note:

  1. 1 <= rooms.length <= 1000
  2. 0 <= rooms[i].length <= 1000
  3. The number of keys in all rooms combined is at most 3000.

Example 1:

1
2
3
4
5
6
7
Input: [[1],[2],[3],[]]
Output: true
Explanation:  
We start in room 0, and pick up key 1.
We then go to room 1, and pick up key 2.
We then go to room 2, and pick up key 3.
We then go to room 3.  Since we were able to go to every room, we return true.

Example 2:

1
2
3
Input: [[1,3],[3,0,1],[2],[0]]
Output: false
Explanation: We can't enter the room with number 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
// 因为最多就 1000 个房间
// 需要对已经访问过的房间进行标记
// 所以这里我们使用一个 bitset
bool canVisitAllRooms(vector<vector<int>>& rooms)
{
    // 所有房间初始化全未被访问
    bitset<1000> bits;
    // 从 0 号房间开始
    return dfs(rooms, 0, bits);
}
// 因为我们是想要搜索到一种可能满足的访问次序就可以
// 所以这里的 dfs 函数有 bool 返回值来提前结束搜索
bool dfs(vector<vector<int>>& rooms, int room, bitset<1000>& bits)
{
    // 访问当前房间, 标记为已访问
    bits.set(room);
    // 如果访问的房间总数等于所有房间数
    if(bits.count() == rooms.size()) return true;
    // 否则, 从当前房间获取其它房间钥匙, 依次进行访问
    vector<int> curRoom = rooms[room];
    for(int key : curRoom)
    {
        // 如果这把钥匙对应的房间已经被访问过, 就不过去了
        if(bits.test(key)) continue;
        // 否则去访问
        if(dfs(rooms, key, bits)) return true;
    }

    return false;
}