题目来源:https://leetcode.com/problems/cousins-in-binary-tree/description/

标记难度:Easy

提交次数:1/1

代码效率:12ms

题意

在一个四连通图上有若干个橘子,其中有一些是烂的,烂橘子每秒都会向四连通的橘子扩散,问经过多少秒,所有的橘子会烂掉?

分析

前几天在CF上做过一道有点类似的题(1105D,也是BFS分次扩展,当时虽然过了pretest,却因为每次扩展的结点过多且queue初始化过慢超时了。所以我就学到了一个道理:在这种情况下注意到底应该扩展哪些结点。不过这道题其实没有这个必要……

考虑到这一点,不如直接用vector代替queue

代码

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
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
vector<pair<int, int>> q;
int orangeCnt = 0;
int n = grid.size(), m = grid[0].size();
int mx[4] = {0, 0, 1, -1};
int my[4] = {1, -1, 0, 0};

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] != 0) orangeCnt++;
if (grid[i][j] == 2) q.emplace_back(i, j);
}
}

if (q.size() == orangeCnt) return 0; // 全都烂了
if (q.size() == 0) return -1; // 根本没有烂的
// [lastEnd, lastSize)这部分是本次需要扩展的
// 之前的已经扩展过了,没有再扩展一次的必要
int lastEnd = 0, lastSize = q.size();
for (int i = 1; ; i++) {
for (int j = lastEnd; j < lastSize; j++) {
int x = q[j].first, y = q[j].second;
for (int k = 0; k < 4; k++) {
int nx = x + mx[k], ny = y + my[k];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (grid[nx][ny] == 1) {
grid[nx][ny] = 2;
q.emplace_back(nx, ny);
}
}
}
// 本次没有扩展出新的烂橘子,且还有橘子没烂,说明扩展不到那边了
if (lastSize == q.size()) return -1;
// 所有橘子都烂了
if (q.size() == orangeCnt) return i;
lastEnd = lastSize;
lastSize = q.size();
}
return 0;
}
};

题意

P1215 [USACO1.4]母亲的牛奶 Mother's Milk

有三个容量分别是A,B,C的桶,A,B,C是1到20的整数。初始状态下A和B都是空的,C是满的。可以从一个桶向另一个桶内倒牛奶,直到倒满或者倒空为止。问A为空时C中所有可能的牛奶体积。

分析

非常基础的搜索题。用DFS和BFS都可以。搜就是了……

一种简化存储状态的方法是,只存两个桶内的牛奶数量,因为牛奶总数是不变的。(不过这个简化看起来没什么意思。)

我看了看题解里所谓的动态规划方法,发现它做的事情与其说是“动态规划”,还不如说是类似于Bellman-Ford的不断松弛,发现一次松弛就继续更新……

代码

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
/*
ID: zhanghu15
TASK: milk3
LANG: C++14
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int A, B, C;
int limit[3];
bool states[21][21][21];
bool ans[21];

void dfs(int s[3]) {
if (s[0] == 0) ans[s[2]] = true;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (i == j) continue;
// pour from i to j
if (s[i] == 0 || s[j] == limit[j]) continue;
int ns[3];
if (s[i] <= limit[j] - s[j]) {
ns[i] = 0;
ns[j] = s[j] + s[i];
ns[3-i-j] = s[3-i-j];
}
else {
ns[i] = s[i] - (limit[j] - s[j]);
ns[j] = limit[j];
ns[3-i-j] = s[3-i-j];
}
if (states[ns[0]][ns[1]][ns[2]]) continue;
states[ns[0]][ns[1]][ns[2]] = true;
dfs(ns);
}
}
}

int main() {
ofstream fout("milk3.out");
ifstream fin("milk3.in");
fin >> limit[0] >> limit[1] >> limit[2];
int s[3] = {0, 0, limit[2]};
dfs(s);
for (int i = 0; i < limit[2]; i++)
if (ans[i])
fout << i << ' ';
fout << limit[2] << endl;
return 0;
}

题目来源:https://leetcode.com/problems/number-of-recent-calls/description/

标记难度:Medium

提交次数:3/6

代码效率:

  • treeSet+Dijstra:140ms
  • 优先队列+Dijstra:120ms
  • BFS:24ms

题意

在一个四连通图上有两个互不连通的子图,求这两个子图之间的最短距离。

分析

刚看到这道题的时候我很晕,不知道该怎么做。遂上网谷歌一下……找到了正确的做法之后,我却把set给写挂了。事实证明,std::set中判断相等的方式是!(a < b) && !(b < a)而非!(a == b)。这一点是值得注意的。[1]


单就一般的图来说,这道题也不算很难:把子图A的所有结点都作为Dijstra算法的起始结点,然后在子图B的所有结点中取距离最短的。如果没有负权边,则直接在找到第一个子图B结点时结束算法即可。

然后这道题并不是一般的图,而是四连通的方格图,所以BFS就可以了。BFS的常数果然还是小啊……

代码

用Dijstra的代码太过智障所以就不贴了……

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 Solution {
private:
int N;
int color[105][105];
int dist[105][105];
int mx[4] = {-1, 1, 0, 0};
int my[4] = {0, 0, -1, 1};

void dfs(int curx, int cury, int c, vector<vector<int>>& A) {
for (int i = 0; i < 4; i++) {
int x = curx + mx[i];
int y = cury + my[i];
if (x < 0 || x >= N || y < 0 || y >= N || A[x][y] != 1 || color[x][y] != -1) continue;
color[x][y] = c;
dfs(x, y, c, A);
}
}

public:
int shortestBridge(vector<vector<int>>& A) {
N = A.size();
memset(color, -1, sizeof(color));
int colorCnt = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
if (A[i][j] == 1 && color[i][j] == -1) {
color[i][j] = colorCnt;
dfs(i, j, colorCnt, A);
colorCnt++;
}
}

queue<pair<int, int>> q;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
if (color[i][j] == 0) {
dist[i][j] = 0;
q.push(make_pair(i, j));
}
else
dist[i][j] = 1e9;
}
while (!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop();
if (color[x][y] == 1) return dist[x][y] - 1;
for (int i = 0; i < 4; i++) {
int nx = x + mx[i], ny = y + my[i];
if (nx < 0 || nx >= N || ny < 0 || ny >= N || dist[nx][ny] <= dist[x][y] +1) continue;
dist[nx][ny] = dist[x][y] + 1;
q.push(make_pair(nx, ny));
}
}
return -1;
}
};

  1. stackoverflow - std::set with user defined type, how to ensure no duplicates

题目来源:https://leetcode.com/problems/snakes-and-ladders/description/

标记难度:Medium

提交次数:2/3

代码效率:

  • 比赛时的BFS:32ms
  • 优化过的BFS:16ms

题意

一个变种的BFS题。简单来说,就是可以以某种方式在棋盘上向前走1~6个格子;如果走到的格子中的值不是-1,则可以跳到该值对应的格子。

分析

数据量很小,所以不论怎么处理坐标问题都能做。但是在这个问题中,visited数组就不能那么简单地定义了。走到一个格子之后继续尝试向前走,和中途跳过这个格子显然是不一样的。所以我定义了两种visited数组,分别处理两种情况。不过题解里好像就没有管中途跳过这种情况了,只记录了实际走过的格子。

我中间因为没有处理好visited数组的问题MLE了一次,说明必须要处理这个问题,否则会出现循环跳的情况。

仔细想了一下,我觉得处理中途跳过的情形的数组确实没什么用,因为下一个要跳到的格子是确定的。以及实时计算格子对应的坐标其实也是比较简单的,不过我更喜欢不想那么多,直接全部存起来……[1]

代码

比赛时的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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution {
struct Pair {
int x, y; // 事实上没什么必要
int boardNum;
int steps;

Pair(int num, int x1, int y1, int s) {
boardNum = num;
x = x1;
y = y1;
steps = s;
}
};

public:
int snakesAndLadders(vector<vector<int>>& board) {
int N = board.size();
map<int, pair<int, int>> numToCoordMap;
map<pair<int, int>, int> coordToNumMap;
bool startFrom = true;
int cnt = 1;
for (int i = N - 1; i >= 0; i--) {
if (startFrom) {
for (int j = 0; j < N; j++) {
numToCoordMap[cnt] = make_pair(i, j);
coordToNumMap[make_pair(i, j)] = cnt;
cnt++;
}
}
else
for (int j = N - 1; j >= 0; j--) {
numToCoordMap[cnt] = make_pair(i, j);
coordToNumMap[make_pair(i, j)] = cnt;
cnt++;
}
startFrom = !startFrom;
}
queue<Pair> q;
bool visited[N*N + 1], jumped[N*N + 1];
memset(visited, 0, sizeof(visited));
memset(jumped, 0, sizeof(jumped));

q.emplace(1, N-1, 0, 0);
visited[1] = true;
while (!q.empty()) {
Pair p = q.front();
q.pop();
if (p.boardNum == N * N)
return p.steps;
for (int i = 1; i <= 6; i++) {
if (p.boardNum + i > N * N) break;

// jumped[x]: this point has been jumped through
// visited[x]: this point has been x+1...x+6
int next = p.boardNum + i;
if (jumped[next]) continue;
pair<int, int> nc = numToCoordMap[next];
if (board[nc.first][nc.second] != -1) {
jumped[next] = true;

next = board[nc.first][nc.second];
if (visited[next]) continue;
nc = numToCoordMap[next];
visited[next] = true;
}
else
jumped[next] = true;
q.emplace(next, nc.first, nc.second, p.steps + 1);
}
}
return -1;
}
};

优化过的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
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
class Solution {
struct Pair {
int x, y;
int boardNum;
int steps;

Pair(int num, int x1, int y1, int s) {
boardNum = num;
x = x1;
y = y1;
steps = s;
}
};

public:
int snakesAndLadders(vector<vector<int>>& board) {
int N = board.size();
// 分别存储number->坐标和坐标->number的映射
// 虽然可以即时计算,但我觉得这样比较直观好写……
vector<pair<int, int>> numberToCord;
vector<vector<int>> cordToNumber(N, vector<int>(N, 0));
bool startFrom = true;
numberToCord.emplace_back(-1, -1); // board number starts from 1
int cnt = 1;
for (int i = N - 1; i >= 0; i--) {
if (startFrom)
for (int j = 0; j < N; j++) {
numberToCord.emplace_back(i, j);
cordToNumber[i][j] = cnt++;
}
else
for (int j = N - 1; j >= 0; j--) {
numberToCord.emplace_back(i, j);
cordToNumber[i][j] = cnt++;
}
startFrom = !startFrom;
}

// number和坐标表示存储一种即可
queue<pair<int, int>> q; // (boardNum, steps)
bool visited[N*N + 1], jumped[N*N + 1];
memset(visited, 0, sizeof(visited));
memset(jumped, 0, sizeof(jumped));

q.emplace(1, 0);
visited[1] = true;
while (!q.empty()) {
pair<int, int> p = q.front();
q.pop();
int curNum = p.first, curStep = p.second;
if (curNum == N * N) return curStep;

for (int i = 1; i <= 6 && curNum + i <= N*N; i++) {
// jumped[x]: this point has been jumped through
// visited[x]: this point has been x+1...x+6
int nextNum = curNum + i;
// 事实上jumped没什么用。即使不维护这个访问数组,从当前nextNum
// 所能跳到的格子是确定的,所以下一步就可以确定是否已经访问过那个格子了。
if (jumped[nextNum]) continue;
int nx = numberToCord[nextNum].first, ny = numberToCord[nextNum].second;
if (board[nx][ny] != -1) {
jumped[nextNum] = true;
nextNum = board[nx][ny];
if (visited[nextNum]) continue;
visited[nextNum] = true;
}
else
jumped[nextNum] = true;

q.emplace(nextNum, curStep + 1);
}
}
return -1;
}
};

  1. Leetcode 909 Solution

题目来源:https://leetcode.com/problems/find-bottom-left-tree-value/description/

标记难度:Medium

提交次数:1/1

代码效率:98.56%

题意

给定一棵二叉树,找到最底层最靠左的结点的值。

分析

这道题看起来像是Leetcode 199的反过来的超简化版,因为只需要最底层的最左边的结点。我是用BFS直接做的——逐层访问,记录每层最左侧的结点,最后找到最底层最左侧的结点——不过这个思路可以再简化一些:对于每一层都从右往左访问,这样我们就不需要记录每层最左侧的结点,只需要返回最后一个访问的结点就可以了。[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
class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> q;
TreeNode* bottomLeft = nullptr;
q.push(root);
while (!q.empty()) {
TreeNode* left = nullptr;
// 这个代码实际上复用了Leetcode 199的BFS代码
// 同理,仍然可以不新开一个queue的
queue<TreeNode*> q2;
while (!q.empty()) {
TreeNode* x = q.front();
q.pop();
if (left == nullptr)
left = x;
if (x->left != nullptr)
q2.push(x->left);
if (x->right != nullptr)
q2.push(x->right);
}
q = q2;
bottomLeft = left;
}
return bottomLeft->val;
}
};

  1. Right-to-Left BFS (Python + Java)

题目来源:https://leetcode.com/problems/binary-tree-right-side-view/description/

标记难度:Medium

提交次数:2/2

代码效率:

  • BFS:100.00%
  • DFS:100.00%

题意

给定一棵二叉树,求每一层最右侧的结点的值。

分析

显然,一种最直接的想法是用BFS对树进行分层遍历,然后就可以立刻得出每一层最右侧的结点的值了。

另一种方法和Leetcode 102的其中一种解题思路很像:使用DFS,然后按照深度把结点放到对应的层里面。但此处的问题是,每一层只需要放最右侧的结点。解决这一问题的方法是,访问子树时,先访问右子结点,再访问左子结点,这样每一层最先被访问到的结点都是最右侧的结点,我们只要在该层为空时才插入结点就可以了。[1]

代码

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
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
if (root == NULL)
return {};

queue<TreeNode*> q;
vector<int> rightSide;
q.push(root);
while (!q.empty()) {
int right = -1;
// 此处新开了一个队列作为记录,事实上没有必要
// 只要记录本层结点的个数就可以了
queue<TreeNode*> q2;
while (!q.empty()) {
TreeNode* x = q.front();
q.pop();
right = x->val;
if (x->left != nullptr)
q2.push(x->left);
if (x->right != nullptr)
q2.push(x->right);
}
q = q2;
rightSide.push_back(right);
}
return rightSide;
}
};

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
private:
void dfs(TreeNode* root, int depth, vector<int>& views) {
if (root == nullptr) return;
// 事实上写的时候是自顶向下的,所以是逐渐push_back
if (depth >= views.size()) views.push_back(root->val);
dfs(root->right, depth+1, views);
dfs(root->left, depth+1, views);
}

public:
vector<int> rightSideView(TreeNode* root) {
vector<int> views;
dfs(root, 0, views);
return views;
}
};

  1. Simple C++ solution (BTW: I like clean codes)

题目来源:https://leetcode.com/problems/minimum-depth-of-binary-tree/description/

标记难度:Easy

提交次数:2/2

代码效率:

  • BFS:100.00%
  • 递推:100.00%

题意

找出二叉树中深度最小的结点的深度。

分析

显然用BFS可以做,DFS也可以。另一种可能的做法是递推,从子结点的最小深度推出当前子树的最小深度。[1]事实上,我现在觉得,递推是把代码写得简短且不需要额外函数的一种好方法。

代码

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int minDepth(TreeNode* root) {
if (root == nullptr) return 0;
queue<pair<int, TreeNode*>> q;
q.emplace(1, root);
while (!q.empty()) {
TreeNode* x = q.front().second;
int depth = q.front().first;
q.pop();

if (x->left == nullptr && x->right == nullptr) return depth;
if (x->left != nullptr) q.emplace(depth+1, x->left); // 居然写成了root……
if (x->right != nullptr) q.emplace(depth+1, x->right);
}
return -1;
}
};

递推

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int minDepth(TreeNode* root) {
if (root == nullptr) return 0;
int L = minDepth(root->left), R = minDepth(root->right);
// 如果L,R>0,说明两棵子树都不为空,最浅的叶结点可能在两棵子树中,所以取min
// 如果L,R中至少有一个数为0,说明至少有一棵子树为空,最浅的叶结点只能在另一棵子树中,所以取max
// 如果L==R==0,说明root就是叶结点,这种情况包含在上一种里
// 因为是子树所以深度要+1
return 1 + ((L > 0 && R > 0) ? min(L, R) : max(L, R));
}
};

  1. 3 lines in Every Language