【LeetCode】Explore：Queue & Stack 队列 & 栈

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

参考自LeetCode上Explore模块的Queue & Stack，作为笔记记录。

Overview 综述

主要了解两种不同的元素处理顺序：先入先出（FIFO）和后入先出（LIFO）；以及两个相应的线性数据结构：队列（Queue）和栈（Stack）。

主要内容：

  1. 了解 FIFO 和 LIFO 处理顺序的原理；
  2. 实现这两个数据结构；
  3. 熟悉内置的队列和栈结构；
  4. 解决基本的队列相关问题，尤其是 BFS；
  5. 解决基本的栈相关问题；
  6. 理解当你使用 DFS 和其他递归算法来解决问题时，系统栈是如何帮助你的。

Queue: First-in-first-out Data Structure 队列：先入先出的数据结构

先入先出的数据结构

FIFO数据结构：首先处理添加到队列中的第一个元素。

队列是典型的FIFO数据结构，插入删除操作被称为入队出队，新元素始终添加在队列末尾，只能移除第一个元素。

循环队列

简单的使用动态数组和指向队列头部的索引来实现队列，会导致空间的浪费。

更有效的方法是使用循环队列，即使用固定大小的数组和两个指针来指示起始位置和结束位置，目的是重用被浪费的存储空间。

示例如图：

练习：设计循环队列

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

  • MyCircularQueue(k): 构造器，设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空，返回 -1 。
  • Rear: 获取队尾元素。如果队列为空，返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
MyCircularQueue circularQueue = new MycircularQueue(3); // 设置长度为 3

circularQueue.enQueue(1);  // 返回 true

circularQueue.enQueue(2);  // 返回 true

circularQueue.enQueue(3);  // 返回 true

circularQueue.enQueue(4);  // 返回 false，队列已满

circularQueue.Rear();  // 返回 3

circularQueue.isFull();  // 返回 true

circularQueue.deQueue();  // 返回 true

circularQueue.enQueue(4);  // 返回 true

circularQueue.Rear();  // 返回 4

提示：

  • 所有的值都在 0 至 1000 的范围内；
  • 操作数将在 1 至 1000 的范围内；
  • 请不要使用内置的队列库。

解答：设计循环队列

使用一个数组和两个指针（tail和head）表示队列的结束和起始位置。

代码如下：

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
class MyCircularQueue {
private:
    vector<int> data;
    int head;
    int tail;
    int size;
    
public:
    /** Initialize your data structure here. Set the size of the queue to be k. */
    MyCircularQueue(int k) {
        data.resize(k);
        size = k;
        head = -1;
        tail = -1;
    }
    
    /** Insert an element into the circular queue. Return true if the operation is successful. */
    bool enQueue(int value) {
        if (isFull()) {
            return false;
        }
        if (isEmpty()) {
            head = 0;
        }
        tail = (tail+1) % size;
        data[tail] = value;
        return true;
        
    }
    
    /** Delete an element from the circular queue. Return true if the operation is successful. */
    bool deQueue() {
        if (isEmpty()) {
            return false;
        }
        if (head == tail) {
            head = -1;
            tail = -1;
            return true;
        }
        head = (head+1) % size;
        return true;
    }
    
    /** Get the front item from the queue. */
    int Front() {
        if (isEmpty()) {
            return -1;
        }
        return data[head];
    }
    
    /** Get the last item from the queue. */
    int Rear() {
        if (isEmpty()) {
            return -1;
        }
        return data[tail];
    }
    
    /** Checks whether the circular queue is empty or not. */
    bool isEmpty() {
        return head == -1;
    }
    
    /** Checks whether the circular queue is full or not. */
    bool isFull() {
        return (tail+1) % size == head;
    }
};

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue* obj = new MyCircularQueue(k);
 * bool param_1 = obj->enQueue(value);
 * bool param_2 = obj->deQueue();
 * int param_3 = obj->Front();
 * int param_4 = obj->Rear();
 * bool param_5 = obj->isEmpty();
 * bool param_6 = obj->isFull();
 */

队列：用法

大多数语言都提供内置的队列库，无需重复造轮子。

以C++内置队列库使用为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>

int main() {
    // 1. Initialize a queue.
    queue<int> q;
    // 2. Push new element.
    q.push(5);
    q.push(13);
    q.push(8);
    q.push(6);
    // 3. Check if queue is empty.
    if (q.empty()) {
        cout << "Queue is empty!" << endl;
        return 0;
    }
    // 4. Pop an element.
    q.pop();
    // 5. Get the first element.
    cout << "The first element is: " << q.front() << endl;
    // 6. Get the last element.
    cout << "The last element is: " << q.back() << endl;
    // 7. Get the size of the queue.
    cout << "The size is: " << q.size() << endl;
}

当想要按顺序处理元素时，使用队列可能是一个很好的选择。

练习：Moving Average from Data Stream

【LeetCode】346

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

For example,

1
2
3
4
5
MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 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
class MovingAverage {
private:
    queue<int> que;
    int size;
    double sum;

public:
    /** Initialize your data structure here. */
    MovingAverage(int size): size(size), sum(0) {
    }
    
    double next(int val) {
        if(que.size() >= size)
        {
            sum -= que.front();
            que.pop();
        }
        sum += val;
        que.push(val);
        return sum/que.size();
    }
};
 
/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */

Queue and BFS 队列和广度优先搜索

广度优先搜索（BFS）是一种遍历或搜索数据结构的算法。

可以用BFS执行树的层序遍历，可以遍历图并找到从起始节点到目标节点的路径（特别是最短路径）。

队列和BFS

BFS的一个常见应用是找从根节点到目标节点的最短路径。

下图展示用BFS找出节点A到目标节点G的最短路径。

上述过程中：

节点处理顺序：越是接近根节点的节点将越早被遍历，所以第一次找到目标节点时，即为最短路径。

入队出队顺序：首先根节点入队，之后每轮处理已经在队列中的点，并将所有邻居入队，新加入的节点将在下轮处理，节点处理顺序与入队的顺序相同，即FIFO，所以BFS过程中可以使用队列处理问题。

广度优先搜索——模板

使用BFS的两个主要场景：遍历或找出最短路径。

BFS也可以用于更抽象的场景中，在特定问题中执行BFS之前确定节点和边缘非常重要。通常，节点是实际节点或状态，而边缘是实际边缘或可能的转换。

伪代码模板（Java）：

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
/**
 * Return the length of the shortest path between root and target node.
 * 返回root和target之间的最短路径
 */
int BFS(Node root, Node target) {
    Queue<Node> queue;  // store all nodes which are waiting to be processed，存储所有待处理的节点
    int step = 0;       // number of steps neeeded from root to current node，根节点到正在访问的当前节点的距离
    
    // initialize
    add root to queue;
    // BFS
    // 每循环一层，距离根节点更远一步
    while (queue is not empty) {
        step = step + 1;
        // iterate the nodes which are already in the queue
        // 每轮中，队列中的节点是等待处理的节点
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            Node cur = the first node in queue;
            return step if cur is target;
            for (Node next : the neighbors of cur) {
                add next to queue;
            }
            remove the first node from queue;
        }
    }
    return -1;          // there is no path from root to target
}

如果需要确保不会访问一个节点两次，可以在上述代码中加入一个set来记录访问过的节点，如下所示：

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
/**
 * Return the length of the shortest path between root and target node.
 */
int BFS(Node root, Node target) {
    Queue<Node> queue;  // store all nodes which are waiting to be processed
    Set<Node> used;     // store all the used nodes
    int step = 0;       // number of steps neeeded from root to current node
    // initialize
    add root to queue;
    add root to used;
    // BFS
    while (queue is not empty) {
        step = step + 1;
        // iterate the nodes which are already in the queue
        int size = queue.size();
        for (int i = 0; i < size; ++i) {
            Node cur = the first node in queue;
            return step if cur is target;
            for (Node next : the neighbors of cur) {
                if (next is not in used) {
                    add next to queue;
                    add next to used;
                }
            }
            remove the first node from queue;
        }
    }
    return -1;          // there is no path from root to target
}

练习：walls and gates

【LeetCode】286

You are given a $m*n$ 2D grid initialized with these three possible values.

给定一个的用如下三个可能值初始化的$m*n$的2D网格。

  1. -1 - A wall or an obstacle. 墙壁或障碍物。
  2. 0 - A gate. 门。
  3. INF - Infinity means an empty room. We use the value $2^{31}-1=2147483647$ to represent INF as you may assume that the distance to a gate is less than 2147483647. Infinity是一个空房间，使用值$2^{31}-1=2147483647$来表示INF，可以假设到门的距离小于2147483647。

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF. 在每个代表空房间的网格中填充其距离最进门的距离，如果不可能到达门，则填充INF。

For example, given the 2D grid:

1
2
3
4
INF  -1  0  INF
INF INF INF  -1
INF  -1 INF  -1
  0  -1 INF INF

After running your function, the 2D grid should be:

1
2
3
4
3  -1   0   1
2   2   1  -1
1  -1   2  -1
0  -1   3   4

代码如下：

要注意节点的判断；

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
class Solution {
public:
    static const int INF = 2147483647;
    
    void wallsAndGates(vector<vector<int>>& room) {
        if (room.size() == 0)
            return;
        int row = room.size();
        int col = room[0].size();
        
        int dx[] = {0, 1, 0, -1};
        int dy[] = {1, 0, -1, 0};
        
        queue<pair<int, int>> q;
        
        // 遍历输入，将所有门的位置入队
        for (int i=0; i<row; i++) {
            for (int j=0; j<col; j++) {
                if (room[i][j] == 0) {
                    q.push([i, j]);
                }
            }
        }
        
        while (!q.empty()) {
            // 首元素出队，并获取其坐标
            auto head = q.front();
            q.pop();
            int ox = head.first;
            int oy = head.second;
            
            // 遍历门的四个相邻点
            for (int i=0; i<4; i++) {
                int nx = ox + dx[i];
                int ny = oy + dy[i];
                // 如果该位置在矩阵范围内，且该位置为INF，则进行填充及入队操作，这样，等queue中所有元素都遍历完了，则矩阵所有非墙的位置就都被正确更新了
                if (0 <= nx && nx < row && 0 <= ny && ny < col && room[nx][ny] == INF) {
                    q.push({nx, ny});
                    room[nx][ny] = room[ox][oy] + 1;
                }
            }
        }
    }
}

练习：岛屿的个数

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

1
2
3
4
5
6
7
输入:
11110
11010
11000
00000

输出: 1

示例 2:

1
2
3
4
5
6
7
输入:
11000
11000
00100
00011

输出: 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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int count = 0;
        int row = grid.size();
        int col = row > 0 ? grid[0].size() : 0;
        if (row == 0 || col == 0) {
            return count;
        }
        
        // 记录访问过的节点
        vector<vector<bool>> visited(row, vector<bool>(col, false));
        // 遍历与当前节点相连的所有节点
        queue<pair<int, int>> q;
        // 查看周围上下左右的节点
        int dx[] = {0, 1, 0, -1};
        int dy[] = {1, 0, -1, 0};
        // 遍历所有为1的节点
        for (int i=0; i<row; i++) {
            for (int j=0; j<col; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    // 节点为1，且没有被访问过，即为发现新的小岛
                    count++; // 小岛数加1
                    q.push({i, j}); // 节点入队
                    visited[i][j] = true; // 修改节点访问标记
                    
                    // 遍历与当前节点相连的其他节点
                    while (!q.empty()) {
                        auto head = q.front(); // 获取首元素及其坐标
                        q.pop();
                        int ox = head.first;
                        int oy = head.second;
                        
                        // 遍历上下左右的四个节点
                        for (int k=0; k<4; k++) {
                            int nx = ox + dx[k];
                            int ny = oy + dy[k];
                            // 如果该节点在矩阵范围内，且值为1，则入队，并修改节点访问标记，这样等队列元素遍历结束后，则当前相连区域内的节点已遍历结束，可继续寻找下一个不相连的值为1的节点，即新的岛屿
                            if (0 <= nx && nx < row && 0 <= ny && ny < col && grid[nx][ny] == '1' && !visited[nx][ny]) {
                                visited[nx][ny] = true;
                                q.push({nx, ny});
                            }
                        }
                    }
                }
            }
        }
        return count;
    }
};

void test(vector<vector<char> > grid) {
    int rows = grid.size(), cols = rows > 0 ? grid[0].size() : 0;
    if (rows == 0 || cols == 0)
        cout << "Empty datas." << endl;
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j)
            cout << grid[i][j];
        cout << endl;
    }
    Solution s;
    int count = s.numIslands(grid);
    if (count <= 1)
        cout << "There is " << count << " island." << endl;
    else
        cout << "There are " << count << " islands." << endl;
}
int main() {
    vector<vector<char> > grid;
    vector<char> tmp;
    tmp.push_back('1'); tmp.push_back('1'); tmp.push_back('1'); tmp.push_back('1'); tmp.push_back('0');
    grid.push_back(tmp);
    tmp.clear();
    tmp.push_back('1'); tmp.push_back('1'); tmp.push_back('0'); tmp.push_back('1'); tmp.push_back('0');
    grid.push_back(tmp);
    tmp.clear();
    tmp.push_back('1'); tmp.push_back('1'); tmp.push_back('0'); tmp.push_back('0'); tmp.push_back('0');
    grid.push_back(tmp);
    tmp.clear();
    tmp.push_back('0'); tmp.push_back('0'); tmp.push_back('0'); tmp.push_back('0'); tmp.push_back('0');
    grid.push_back(tmp);
    test(grid);

    grid.clear();
    tmp.clear();
    tmp.push_back('1'); tmp.push_back('1'); tmp.push_back('0'); tmp.push_back('0'); tmp.push_back('0');
    grid.push_back(tmp);
    tmp.clear();
    tmp.push_back('1'); tmp.push_back('1'); tmp.push_back('0'); tmp.push_back('0'); tmp.push_back('0');
    grid.push_back(tmp);
    tmp.clear();
    tmp.push_back('0'); tmp.push_back('0'); tmp.push_back('1'); tmp.push_back('0'); tmp.push_back('0');
    grid.push_back(tmp);
    tmp.clear();
    tmp.push_back('0'); tmp.push_back('0'); tmp.push_back('0'); tmp.push_back('1'); tmp.push_back('1');
    grid.push_back(tmp);
    test(grid);

    return 0;
}

练习：打开转盘锁

【LeetCode】752

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

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

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

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

示例 1:

1
2
3
4
5
6
输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。

示例 2:

1
2
3
4
输入: deadends = ["8888"], target = "0009"
输出：1
解释：
把最后一位反向旋转一次即可 "0000" -> "0009"。

示例 3:

1
2
3
4
输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：
无法旋转到目标数字且不被锁定。

示例 4:

1
2
输入: deadends = ["0000"], target = "8888"
输出：-1

提示：

  1. 死亡列表 deadends 的长度范围为 [1, 500]。
  2. 目标数字 target 不会在 deadends 之中。
  3. 每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 '0000' 到 '9999' 中产生。

解题思路

找最短路径问题，考虑用BFS，将问题建图。

每个字符串对应一个状态，可以转换到相邻的8个状态（每位加1减1，共4位），从“0000”开始进行BFS，最后得到总步骤数。

类似用BFS遍历图，找最短路径，所以第一次到达目标节点时的路径一定是最短路径（之一）。

  • 注意向相邻节点转换时的操作，“0”->“9”，“9”->“0”，加1，减1；
  • 用unordered_set存储访问标记和死亡节点，节省查找过程的时间消耗；
  • 首先对deadends进行去重，看讨论区有说会有重复的情况；
  • BFS：从头结点”0000”开始，遍历所有子节点，初次访问且不在deadends中的则入队；已访问过或在deadends中的则跳过；遍历到下一层时，层数step加1，且更新size为下一层的节点数量；
  • 每访问一个节点，先判断是否target，若是则返回当前的step；如果队列已空但仍未返回，则说明无路可通。

代码如下：

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
class Solution {
public:
	int openLock(vector<string>& deadends, string target) {
		if (find(deadends.begin(), deadends.end(), "0000") != deadends.end()) {
			return -1;
		}

		// deadends去重
		sort(deadends.begin(), deadends.end());
		deadends.erase(unique(deadends.begin(), deadends.end()), deadends.end());
		unordered_set<string> deadset(deadends.begin(), deadends.end());

		// 存储当前节点及其可转换的其他节点，以及对应的步数
		queue<string> q;
		int step = 0;
        // 存储当前队列中可访问元素数量（每层的数量）
		int size = 0;
		unordered_set<string> visited;
        
		visited.insert("0000");
		q.push("0000");
		while (!q.empty()) {
			size = q.size();
            // 层数加1
			step++;
            // 遍历当前层所有节点
			for (int i = 0; i < size; i++) {
				string cur = q.front();
				q.pop();
                // 逐个遍历可转换的节点（共8个，每位加1减1）
				for (int j = 0; j < cur.size(); j++) {
					string temp = cur;
					if (temp[j] == '9')
						temp[j] = '0';
					else
						temp[j] += 1;
                    // 找到target，返回层数
					if (temp == target)
						return step;
                    // 没找到target，且不是死亡数字也没有访问过，则入队
					if (!deadset.count(temp) && !visited.count(temp)) {
						q.push(temp);
						visited.insert(temp);
					}

					temp = cur;
					if (temp[j] == '0')
						temp[j] = '9';
					else
						temp[j] -= 1;
					if (temp == target)
						return step;
					if (!deadset.count(temp) && !visited.count(temp)) {
						q.push(temp);
						visited.insert(temp);
					}
				}
			}
		}
		return -1;
	}
};

练习：完全平方数

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

示例 1:

1
2
3
输入: n = 12
输出: 3 
解释: 12 = 4 + 4 + 4.

示例 2:

1
2
3
输入: n = 13
输出: 2
解释: 13 = 4 + 9.

解题思路

参考网上的思路，转换为最短路径问题。

从$0$到$n$共有$n+1$个节点，如果从$i , i\in[0,n]$到$j , j\in[0,n]$相差一个完全平方数，就可以将两个节点连接起来，这样所有的点就转化成无向图，问题转化为求从$0$到$n$的最短路径。

如图所示：

无权最短路径问题，可以采用BFS求解。

也就是说，先遍历从$[1,ii],ii\leq n$，每一步将$n$缩为$n-i*i$，广度优先搜索，直至找到第一条将$n$缩为$0$的路径，即为最短路径。如下所示：

1
2
3
4
5
6
7
8
9
10
11
//将num不断用完全平方数代表，直至其成为0，其中1是完全平方数所以总会有解
for(int i = 1;i*i<=num;i++)
{
     int temp = num - i*i;
     if(visit[temp] == 0)
     {
         //将其中没有访问过的点标记，以及将改点所到达的路径录入
         queue.add(new numpairs(temp,step+1));
         visit[temp] = 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
class Solution {
public:
    int numSquares(int n) {
        if (n==0 || n==1) {
            return n;
        }
        // 从大到小初始化路径序列，如16、9、4、1
        vector<int> square;
        for (int i=1; i*i<=n; i++) {
            square.insert(square.begin(), i*i);
        }
        // 去掉某个平方数后剩余的n，步骤数
        queue<pair<int,int>> q;
        q.push(make_pair(n,0));
        while(!q.empty()) {
            int num = q.front().first;
            int step = q.front().second;
            q.pop();
            for (auto it: square) {
                if (it == num)
                    return step+1;
                if (it < num) {
                    q.push(make_pair(num-it, step+1)); // num-it>0,入队
                    continue;
                }
                // it<num/2,重新从头遍历（从最大的开始）
                if (it < num/2)
                    break;
            }
        }
    }
};

Stack: Last-in-first-out Data Structure 栈：后入先出的数据结构

后入先出的数据结构

LIFO数据结构：首先处理添加到队列中的最新元素。

栈是典型的LIFO数据结构，插入删除操作称为入栈(push)出栈(pop)，新元素始终添加在堆栈的末尾，只能移除堆栈中的最后一个元素。

动态数组可用来实现堆栈结构。

栈：用法

大部分语言都有内置的栈库，无需重复造轮子。

以C++内置库的使用为例：

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

int main() {
    // 1. Initialize a stack.
    stack<int> s;
    // 2. Push new element.
    s.push(5);
    s.push(13);
    s.push(8);
    s.push(6);
    // 3. Check if stack is empty.
    if (s.empty()) {
        cout << "Stack is empty!" << endl;
        return 0;
    }
    // 4. Pop an element.
    s.pop();
    // 5. Get the top element.
    cout << "The top element is: " << s.top() << endl;
    // 6. Get the size of the stack.
    cout << "The size is: " << s.size() << endl;
}

当想要首先处理最后一个元素时，栈将是最合适的数据结构。

练习：最小栈

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

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

示例:

1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

解题思路

方法一，可以用两个栈，一个是题意要求的栈，另一个用来存储每次push后的当前最小值，push或pop时，同时修改两个栈的内容，存最小值的栈的top即为当前全栈最小值。

方法二，只用一个栈，再用一个额外的变量存储当前最小值。每次push时，如果要入栈的值比当前最小值小，则将当前最小值和要入栈的值同时入栈（注意先后顺序），每次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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class MinStack {
private:
        int minVal;
        stack<int> minStack;
public:
    /** initialize your data structure here. */
    MinStack() {
        minVal = INT_MAX;
    }
    
    void push(int x) {
        if (x <= minVal) // 需要更新最小值，并将之前的最小值先入栈
        {
            minStack.push(minVal);
            minVal = x;
        }
        minStack.push(x);
    }
    
    void pop() {
        if (minStack.top() == minVal) // 需要更新最小值
        {
            minStack.pop();
            minVal = minStack.top();
            minStack.pop();
        }
        else
            minStack.pop();
    }
    
    int top() {
        return minStack.top();
    }
    
    int getMin() {
        return minVal;
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

练习：有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

示例 1:

1
2
输入: "()"
输出: true

示例 2:

1
2
输入: "()[]{}"
输出: true

示例 3:

1
2
输入: "(]"
输出: false

示例 4:

1
2
输入: "([)]"
输出: false

示例 5:

1
2
输入: "{[]}"
输出: true

解题思路

用栈结构，遍历字符串，如果是左括号就入栈，如果是右括号就看是否和栈顶元素是一对，如果是则出栈并继续，如果不是一对则返回false，如果遍历结束时栈为空则返回true，如果遍历结束时栈不为空则返回false（如”((“的情况）。

需要判断一些特殊情况，如s长度为0则直接返回true，如果s长度为奇数则直接返回false，同时top时要先确认栈非空。

代码如下：

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
class Solution {
public:
    bool isValid(string s) {
        if (s.size() == 0)
            return true;
        if (s.size() % 2 != 0)
            return false;
        
        stack<char> temp;
        for (auto c: s)
        {
            if (c == '(' || c == '[' || c == '{')
                temp.push(c);
            else if (c == ')' && !temp.empty() && temp.top() == '(')
                temp.pop();
            else if (c == ']' && !temp.empty() && temp.top() == '[')
                temp.pop();
            else if (c == '}' && !temp.empty() && temp.top() == '{')
                temp.pop();
            else
                return false;
        }
        if (temp.empty())
            return true;
        else
            return false;
    }
};

练习：每日温度

根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高的天数。如果之后都不会升高，请输入 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的都是 [30, 100] 范围内的整数。

解题思路

维护一个递减栈，存储元素下标。

遍历温度列表，如果栈为空则直接入栈，如果栈非空，则比较栈顶元素与当前温度，如果当前元素小于等于栈顶元素则直接入栈，如果当前元素大于栈顶元素，则表明已经找到第一次升温的位置，则直接计算下标差并修改result，之后将栈顶元素出栈，并继续比较下一个栈顶元素与当前温度值，直至当前元素小于等于栈顶元素，将当前值入栈，继续上述流程直至遍历结束。

实际做的时候，result直接初始化全0，所以遍历结束直接返回result即可。否则需要将栈内剩余元素对应result中的位置全部置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
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        vector<int> result(T.size(), 0);
        if (T.size() <= 1)
        {
            return result;
        }
        
        stack<int> indexStack;
        for (int i=0; i<T.size(); i++)
        {
            while (!indexStack.empty() && T[i] > T[indexStack.top()])
            {
                result[indexStack.top()] = i-indexStack.top();
                indexStack.pop();
            }
            
            indexStack.push(i);
        }
        
        return result; // result初始化全为0，所以不用再看栈中剩余元素去更新result
    }
};

练习：逆波兰表达式求值

根据逆波兰表示法，求表达式的值。

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

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

示例 1：

1
2
3
输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: ((2 + 1) * 3) = 9

示例 2：

1
2
3
输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: (4 + (13 / 5)) = 6

示例 3：

1
2
3
4
5
6
7
8
9
10
输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
输出: 22
解释: 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

解题思路

典型用栈解决问题，计算的中间结果需要入栈。

代码如下：

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 Solution {
public:
    int evalRPN(vector<string>& tokens) {
        if(tokens.size() == 1)
            return stoi(tokens[0]);
        
        set<string> tag{"+", "-", "*", "/"};
        stack<int> s;
        for(auto item: tokens)
        {
            if (tag.find(item) == tag.end()) // 是数字
            {
                s.push(stoi(item));
            }
            else
            {
                int temp;
                int a = s.top();
                s.pop();
                int b = s.top();
                s.pop();
                if (item == "+")
                    temp = a+b;
                if (item == "-")
                    temp = b-a;
                if (item == "*")
                    temp = a*b;
                if (item == "/")
                    temp = b/a;
                s.push(temp);
            }
        }
        return s.top();
    }
};

Stack and DFS 栈和深度优先搜索

深度优先搜索（DFS）是用于在树/图中进行遍历/搜索的另一种算法。

在树的遍历中，可以用DFS进行前序遍历、中序遍历和后序遍历，这三种遍历的共同特点是除非到达最深的节点，否则不会回溯。

DFS和BFS的区别：BFS永远不会深入探索，除非已经遍历过当前层级的所有节点。

通常使用递归来实现DFS。

栈和DFS

DFS也可以用于查找从根节点到目标节点的路径。

（BFS是可以直接找到最短路径。）

如图所示：

在上述例子中：

首先选择节点B的路径，到达E后无法深入，故回溯到A；再次选择节点C的路径，从C开始首先到达E，但E访问过，故回到C，并尝试F，最后找到了G。

DFS中找到的第一条路径不一定是最短的路径。

节点的处理和回溯过程是后进先出的处理顺序，和栈相同，故在DFS中多用栈来实现。

DFS-模板1

大多可以使用BFS的情况也可以使用DFS，区别主要在遍历顺序。

BFS找到的第一条路径为最短路径，而DFS不一定。

有两种实现DFS的方法，第一种为递归。

伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
/*
 * Return true if there is a path from cur to target.
 */
boolean DFS(Node cur, Node target, Set<Node> visited) {
    return true if cur is target;
    for (next : each neighbor of cur) {
        if (next is not in visited) {
            add next to visted;
            return true if DFS(next, target, visited) == true;
        }
    }
    return false;
}

使用递归实现DFS时，使用的是系统提供的隐式栈，也称为call stack。

在每个堆栈元素中，都有一个当前值，一个目标值，一个访问过的数组的引用，和一个对数组边界的引用，这些就是DFS函数中的参数。栈的大小是DFS的深度，所以最坏情况下，维护系统占需要$O(h)$，其中$h$是DFS的最大深度。

在计算空间复杂度时，要记得考虑系统栈。

练习：岛屿的个数

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

1
2
3
4
5
6
7
输入:
11110
11010
11000
00000

输出: 1

示例 2:

1
2
3
4
5
6
7
输入:
11000
11000
00100
00011

输出: 3

解题思路

之前用BFS方法做过该题，主要是先遍历当前节点相邻的所有节点，之后继续查找下一个为’1’的点，重复上述过程。

此处用DFS方法递归遍历。

首先建立visited数组来记录某个位置是否访问过，对于为’1’且未曾访问过的位置，递归进入其上下左右位置上为’1’且未访问过的点，将其visited置为true，并继续进入其相连的相邻位置，直至周围没有为’1’的点，如此可将整个连通区域中所有的数都找到，将count数加一。之后再寻找下一个为’1’且未访问过的点，重复上述过程，直至遍历完整个grid数组。

代码如下：

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
// DFS
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int count = 0;
        if (grid.size() == 0 || grid[0].size() == 0) {
            return count;
        }
        
        // 记录访问过的节点
        vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
        // 遍历grid中所有节点，遇到为1且为访问过的点，则递归遍历其所有相邻点
        for (int i=0; i<grid.size(); i++) {
            for (int j=0; j<grid[0].size(); j++) {
                if (grid[i][j] == '1' && !visited[i][j])
                {
                    helper(grid, visited, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    
    // 递归遍历x,y所有相邻的点
    void helper(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
        if (0 <= x && x < grid.size() && 0 <= y && y < grid[0].size() && grid[x][y] == '1' && !visited[x][y]) {
            visited[x][y] = true;
            helper(grid, visited, x-1, y);
            helper(grid, visited, x+1, y);
            helper(grid, visited, x, y-1);
            helper(grid, visited, x, y+1);
        }
    }
};

练习：克隆图

给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（Int） 和其邻居的列表（list[Node]）。

示例：

1
2
3
4
5
6
7
8
输入：
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}

解释：
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

提示：

  1. 节点数介于 1 到 100 之间。
  2. 无向图是一个简单图，这意味着图中没有重复的边，也没有自环。
  3. 由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。
  4. 必须将给定节点的拷贝作为对克隆图的引用返回。

解题思路

基本是图的遍历问题，使用DFS方法解答，要注意深度拷贝每个节点后，还要将其neighbors放到一个vector中，要注意避免重复拷贝。题意明确所有节点值不同，所以可使用map来存储已经拷贝过的节点（原节点和新的克隆节点一一对应）。

在递归函数中，首先判断节点是否为空，再看当前节点是否已经克隆过，若在map中存在则已经克隆过，直接返回其映射节点。否则就克隆当前节点，并在map中建立映射，并遍历该节点的所有neighbor节点，递归调用并实时更新map即可。

代码如下：

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;

    Node() {}

    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
public:
    Node* cloneGraph(Node* node) {
        // 用于存储原节点和新的克隆节点的对应，避免重复拷贝
        unordered_map<Node*, Node*> m;
        return helper(node, m);
    }
    
    Node* helper(Node* node, unordered_map<Node*, Node*>& m) {
        if (!node)
            return NULL;
        // 当前节点已经克隆过，则返回其对应的克隆节点
        if (m.count(node))
            return m[node];
        // 当前节点没有克隆过：
        // 首先克隆当前节点，更新map
        Node* clone = new Node(node->val);
        m[node] = clone;
        // 克隆当前节点的所有neighbor节点，并实时更新map
        for (Node* neighbor : node->neighbors) {
            clone->neighbors.push_back(helper(neighbor, m));
        }
        // 返回克隆后的节点
        return clone;
    }
};

练习：目标和

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

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

示例 1:

1
2
3
4
5
6
7
8
9
10
11
输入: nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释: 

-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

一共有5种方法让最终目标和为3。

注意:

  1. 数组的长度不会超过20，并且数组中的值全为正数。
  2. 初始的数组的和不会超过1000。
  3. 保证返回的最终结果为32位整数。

解题思路

从第一个数字开始，调用递归函数，分别计算加当前值和减当前值之后的和，到数组结束时，比较当前和和目标值是否相等。（开始看网上的方法用目标和加/减当前值做递归的目标值来计算，结果在某个测试用例时提示超过int范围，，，）

参考测试用例：

1
2
3
4
5
6
[1,1,1,1,1]
3
[2,107,109,113,127,131,137,3,2,3,5,7,11,13,17,19,23,29,47,53]
2147483647
[5,40,23,47,43,19,36,10,28,46,14,11,5,0,5,22,39,30,50,41]
48

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        return dfs(nums, S, 0, 0);
    }
    
    int dfs(vector<int>& nums, int S, int index, int curSum)
    {
        int res = 0;
        int size = nums.size();
        if(index == size)
            return curSum==S ? 1 : 0;
        res += dfs(nums, S, index+1, curSum+nums[index]);
        res += dfs(nums, S, index+1, curSum-nums[index]);
        return res;     
    }
};

中文版LeetCode提交上述代码时提示在上面第三个测试用例下超时，，，

使用数组记录中间值以减少重复计算。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int n = nums.size();
        // 记录中间值，map内容  当前可得到的中间结果，得到该结果的方法数
        vector<unordered_map<int, int>> dp(n + 1);
        // 初始dp的首值
        dp[0][0] = 1;
        // 遍历数组
        for (int i = 0; i < n; ++i) {
            // 修改加减当前值之后可得到的中间结果及其方法数
            for (auto &a : dp[i]) {
                int sum = a.first, cnt = a.second;
                dp[i + 1][sum + nums[i]] += cnt;
                dp[i + 1][sum - nums[i]] += cnt;
            }
        }
        // 从最终的总方法数中，找到目标值对应的方法数
        return dp[n][S];
    }
};

DFS-模板2

递归虽然容易实现，但如果深度太高，容易栈溢出。这时可能希望使用BFS，或者用显式栈来实现DFS。

显式栈模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
 * Return true if there is a path from cur to target.
 */
boolean DFS(int root, int target) {
    Set<Node> visited;
    Stack<Node> s;
    add root to s;
    while (s is not empty) {
        Node cur = the top element in s;
        return true if cur is target;
        for (Node next : the neighbors of cur) {
            if (next is not in visited) {
                add next to s;
                add next to visited;
            }
        }
        remove cur from s;
    }
    return false;
}

这种方法使用while和栈来模拟递归时的系统调用栈。

练习：二叉树的中序遍历

给定一个二叉树，返回它的中序 遍历。

示例:

1
2
3
4
5
6
7
8
输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> temp;
        
        while(root != NULL || !temp.empty()) {
            // 递归直至最左，将所有左节点入栈
            while(root != NULL) {
                temp.push(root);
                root = root->left;
            }
            
            // 栈顶节点是最左节点
            // 开始出栈，且输出栈顶节点
            if (!temp.empty()) {
                root = temp.top();
                result.push_back(root->val);
                temp.pop();
                root = root->right;
            }
        }
        return result;
    }
};

小结

  • 队列

    队列是FIFO的数据结构，首先处理第一个元素；

    队列两个重要操作：入队和出队；

    可以用带有两个指针的动态数组来实现队列；

    BFS方法常使用队列结构；

  • 栈

    栈是LIFO的数据结构，首先处理最后一个元素；

    栈两个重要操作：push和pop；

    使用动态数组可以实现栈；

    DFS是栈的一个重要应用。

练习：用栈实现队列

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

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

示例:

1
2
3
4
5
6
7
MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);  
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明:

  • 你只能使用标准的栈操作 — 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
  • 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

解题思路

栈后进先出，队列先进先出。所以，在push的时候，借用一个额外的临时栈，首先将队列内原有元素挨个pop到临时栈（临时栈的顺序和构造的队列内顺序相反），再将新值push到临时栈，此时临时栈和要构造的队列元素顺序相反，新值在尾端。最后将临时栈再挨个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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class MyQueue {
public:
    /** Initialize your data structure here. */
    MyQueue() {
        
    }
    stack<int> _stk;
    
    /** Push element x to the back of queue. */
    void push(int x) {
        stack<int> temp;
        while(!_stk.empty()) {
            temp.push(_stk.top());
            _stk.pop();
        }
        temp.push(x);
        while(!temp.empty()) {
            _stk.push(temp.top());
            temp.pop();
        }
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        int r = _stk.top();
        _stk.pop();
        return r;
    }
    
    /** Get the front element. */
    int peek() {
        return _stk.top();
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return _stk.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

练习：用队列实现栈

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

  • push(x) — 元素 x 入栈
  • pop() — 移除栈顶元素
  • top() — 获取栈顶元素
  • empty() — 返回栈是否为空

注意:

  • 你只能使用队列的基本操作— 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
  • 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
  • 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

解题思路

和用栈实现队列的思路类似，push过程借用一个临时队列。需要注意的是，队列先入先出，所以此处要实现栈后入先出的目的，push的新值需要先插入临时队列，以保证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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class MyStack {
public:
    /** Initialize your data structure here. */
    MyStack() {
        
    }
    queue<int> _que;
    
    /** Push element x onto stack. */
    void push(int x) {
        queue<int> temp;
        temp.push(x); // 新值先插入到临时队列中
        while(!_que.empty()) {
            temp.push(_que.front());
            _que.pop();
        }
        while(!temp.empty()) {
            _que.push(temp.front());
            temp.pop();
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    int pop() {
        int r = _que.front();
        _que.pop();
        return r;
    }
    
    /** Get the top element. */
    int top() {
        return _que.front();
    }
    
    /** Returns whether the stack is empty. */
    bool empty() {
        return _que.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

练习：字符串解码

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

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

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

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

示例:

1
2
3
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

解题思路

用栈，类似括号匹配，发现右括号时，开始出栈直至发现左括号，获取括号中要重复的内容，再出栈一次获取重复次数，之后将该字段重复指定次数后再入栈，直至遍历结束。将栈内容出栈，并按照指定顺序拼接成结果字符串返回即可。

注意的是，重复次数可能不是一位数字，所以在入栈时，对于连续的数字要拼接到一起再入栈。

使用的几个测试用例：

1
2
3
4
5
"3[a]2[bc]"
"100[leetcode]"
"3[a2[c]]"
"2[abc]3[cd]ef"
"2[abc]30[cd]ef"

代码如下：

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
class Solution {
public:
	string decodeString(string s) {
		stack<string> stk;

		for (int idx = 0; idx < s.size(); idx++) {
			if (s[idx] != ']') {
				if (isdigit(s[idx])) { // 发现数字
					int begin = idx;
					idx++;
                    // 找到下一个不为数字的位置
					while (isdigit(s[idx])) {
						idx++;
					}
                    // 插入多位数字
					stk.push(s.substr(begin, idx - begin));
				}
				stk.push(string(1, s[idx]));
			}
			else
			{
                // 获取要重复的内容
				string temp = "";
				while (stk.top() != "[") {
					temp = stk.top() + temp;
					stk.pop();
				}
				// "[" 出栈
				stk.pop();
                // 获取重复次数
				int num = stoi(stk.top());
				stk.pop();
                // 重复内容，并将结果再次入栈
				string cur = "";
				for (int i = 0; i < num; i++) {
					cur += temp;
				}
				stk.push(cur);
			}
		}
		string result = "";
		while (!stk.empty()) {
			result = stk.top() + result;
			stk.pop();
		}
		return result;
	}
};

练习：图像渲染

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

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

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

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

示例 1:

1
2
3
4
5
6
7
8
9
输入: 
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析: 
在图像的正中间，(坐标(sr,sc)=(1,1)),
在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，
因为它不是在上下左右四个方向上与初始点相连的像素点。

注意:

  • image 和 image[0] 的长度在范围 [1, 50] 内。
  • 给出的初始点将满足 0 <= sr < image.length 和 0 <= sc < image[0].length。
  • image[i][j] 和 newColor 表示的颜色值在范围 [0, 65535]内。

解题思路

和前面岛屿的个数类似，主要找到与初始点颜色相同且相连的节点，将其着色返回即可。

采用BFS或DFS递归均可，此处使用BFS，首先初始点标记访问、修改颜色、入队，后遍历其相邻节点，将颜色相同的相邻点标记访问、修改颜色、入队。直至队列为空，说明与初始点相连接的所有点均遍历结束，则返回。

代码如下：

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
class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        // int row = image.size();
        // int col = row > 0 ? image[0].size() : 0;
        // if (row == 0 || col == 0)
        //     return image;
        
        // 题设row col长度范围在[1,50]，所以省掉额外判断
        int row = image.size();
        int col = image[0].size();
        
        // 记录访问过的节点
        vector<vector<bool>> visited(row, vector<bool>(col,false));
        // 记录相邻且相连的节点
        queue<pair<int,int>> q;
        // 查看上下左右的节点用
        int dx[] = {0, 1, 0, -1};
        int dy[] = {1, 0, -1, 0};
        // 记录初始点颜色
        int tag = image[sr][sc];
        
        // 初始点入队，标记访问，修改初始点颜色
        q.push({sr, sc});
        visited[sr][sc] = true;
        image[sr][sc] = newColor;
        
        // 遍历相邻且颜色相同的点
        while(!q.empty()) {
            auto head = q.front(); // 获取首元素及坐标
            q.pop();
            int ox = head.first;
            int oy = head.second;
            
            // 遍历上下左右的点
            for (int i=0; i<4; i++) {
                int nx = ox + dx[i];
                int ny = oy + dy[i];
                // 如果该节点在矩阵范围内，且颜色和初始点相同，则修改其颜色为newcolor，并标记访问，入队
                if (0 <= nx && nx < row && 0 <= ny && ny < col && image[nx][ny] == tag && !visited[nx][ny]) {
                    image[nx][ny] = newColor;
                    visited[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
        return image;
    }
};

练习：01矩阵

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

两个相邻元素间的距离为 1 。

示例 1:
输入:

1
2
3
0 0 0
0 1 0
0 0 0

输出:

1
2
3
0 0 0
0 1 0
0 0 0

示例 2:
输入:

1
2
3
0 0 0
0 1 0
1 1 1

输出:

1
2
3
0 0 0
0 1 0
1 2 1

注意:

  1. 给定矩阵的元素个数不超过 10000。
  2. 给定矩阵中至少有一个元素是 0。
  3. 矩阵中的元素只在四个方向上相邻: 上、下、左、右。

解题思路

找到最近的0的距离，是最短路径问题，用BFS。

类比前面 walls and gates ，首先将原矩阵中所有值为0的点入队，值为1的点设为无限大INT_MAX（为了后续比较最小距离）。

遍历queue中节点的相邻节点，若该相邻节点的值大于当前节点值加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
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
	vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
		int row = matrix.size();
		int col = row > 0 ? matrix[0].size() : 0;
		if (row == 0 || col == 0) {
			return matrix;
		}

		// 遍历当前节点相邻的节点
		queue<pair<int, int>> q;
		// 上下左右节点
		int dx[] = { 0, 1, 0, -1 };
		int dy[] = { 1, 0, -1, 0 };

		// 修改原矩阵，值为0的入队，值为1的将距离设为无限大INT_MAX
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {
				if (matrix[i][j] == 0)
					q.push({ i,j });
				else
					matrix[i][j] = INT_MAX;
			}
		}

		// 遍历队列内值，即所有为0的点，从相邻节点中找非零点，如果值比当前点值加一大，则修改为当前值加一，且该相邻节点入队
		while (!q.empty()) {
			auto head = q.front();
			q.pop();
			// 遍历周围节点
			int ox = head.first;
			int oy = head.second;
			for (int k = 0; k < 4; k++) {
				int nx = ox + dx[k];
				int ny = oy + dy[k];
				if (0 <= nx && nx < row && 0 <= ny && ny<col && matrix[nx][ny]>matrix[ox][oy] + 1) {
					matrix[nx][ny] = matrix[ox][oy] + 1;
					q.push({ nx, ny });
				}
			}
		}
		return matrix;
	}
};

练习：钥匙和房间

有 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。

示例 1：

1
2
3
4
5
6
7
8
输入: [[1],[2],[3],[]]
输出: true
解释:  
我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。

示例 2：

1
2
3
输入：[[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入 2 号房间。

提示：

  1. 1 <= rooms.length <= 1000
  2. 0 <= rooms[i].length <= 1000
  3. 所有房间中的钥匙数量总计不超过 3000。

解题思路

用栈实现，并且维护一个长度N的数组标记房间是否能够打开。

首先将0号房间的钥匙全部入栈，之后挨个出栈，并且判断当前的钥匙对应的房间是否已经打开，如果已经打开就跳过，如果是第一次打开，就将该房间的钥匙入栈，并标记该房间。

到栈为空时，如果标记房间的数组值全为true，则返回true，否则返回false。

同样的思路，用队列也可以，队列是BFS，栈的话就是DFS。

代码如下：

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
class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        vector<int> visited(rooms.size(), 0);
        visited[0] = 1;
        stack<int> keys;
        
        // 0号房间的钥匙入栈
        for (auto key : rooms[0]) {
            keys.push(key);
        }
        
        // 遍历栈中所有钥匙，标记可打开的房间
        while (!keys.empty()) {
            int key = keys.top();
            keys.pop();
            if (visited[key] == 0) { // 该房间之前没有打开过
                visited[key] = 1;
                for (auto temp : rooms[key]) {
                    keys.push(temp);
                }
            }
        }
        
        // 所有钥匙遍历结束，看visited中是否有没有打开的房间
        return find(visited.begin(), visited.end(), 0) == visited.end();
    }
};
-------------本文结束感谢您的阅读-------------
0%