题目来源:https://leetcode.com/problems/satisfiability-of-equality-equations/description/

标记难度:Medium

提交次数:1/1

代码效率:16ms

题意

给定一系列等式,每个等式形如a==ba!=b,变量名为单个英文小写字母,问这些等式组能否成立?

分析

这道题的思路很简单:首先将所有a==b等式转化成ab之间的连边,然后做并查集或DFS,然后再判断形如a!=b的等式中的两个变量是否在同一个连通集中。总之用并查集和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
29
30
31
32
33
34
35
class Solution {
private:
int _fa[26];

void init() {
for (int i = 0; i < 26; i++)
_fa[i] = i;
}

int fa(int x) {
if (_fa[x] == x) return x;
return _fa[x] = fa(_fa[x]);
}

void merge(int x, int y) {
x = fa(x);
y = fa(y);
_fa[x] = y;
}

public:
bool equationsPossible(vector<string>& equations) {
init();
for (string s: equations) {
if (s[1] == '=')
merge(s[0] - 'a', s[3] - 'a');
}
for (string s: equations) {
if (s[1] == '!')
if (fa(s[0] - 'a') == fa(s[3] - 'a'))
return false;
}
return true;
}
};

题意

洛谷 P1457 城堡 The Castle

有一个M*N的方格图(1 <= M,N <= 50),其中方格外侧有一整圈墙,有些方格线上有墙。问这些墙形成了多少个房间,以及去掉一堵墙能形成的最大房间的面积?

分析

应该可以说是标准的Floodfill算法了。算法流程如下:

  • 对于每一个格子,如果它还没有被访问到,则房间数+1,并从该格子开始DFS
  • 在DFS过程中,将访问到的每一个格子都标为当前房间数(于是立刻可以得到共有多少个房间)
  • 对于每一堵墙,判断它两侧的格子是否属于不同房间,如果是,则拆掉这面墙可以将这两个房间连起来,且新房间的面积是原来两个房间的和

Floodfill的时间复杂度是O(M*N),枚举墙的时间复杂度也是O(M*N),因此总复杂度为O(M*N)

代码

其他部分都没有什么难的,但是在答案去重这部分遇到了一点小问题。题目要求以某个格子北侧或东侧的形式打印需要的墙,且:

  • 选择拆除后得到的房间面积最大的墙
  • 如果面积相同,则选择最靠西的格子
  • 如果同样靠西,则选择最靠北的格子
  • 如果同样靠北,则优先选择格子东侧的墙

这可真是复杂的要求……

所以我也写了一堆复杂的判断条件……

顺带一提,我终于意识到现在USACO题目左边(可能会出现)的数字是你已经通过了多少个样例了……

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

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

using namespace std;
typedef long long int LL;

int M, N;

// west, north, east, south
int mx[4] = { 0, -1, 0, 1};
int my[4] = {-1, 0, 1, 0};
int module[50][50];
int visited[50][50];
int cnt[2501];
int n;

void dfs(int x, int y) {
for (int i = 0; i < 4; i++) {
if (module[x][y] & (1 << i)) continue;
int nx = x + mx[i], ny = y + my[i];
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
if (visited[nx][ny]) continue;
visited[nx][ny] = n;
cnt[n]++;
dfs(nx, ny);
}
}

int main() {
ofstream fout("castle.out");
ifstream fin("castle.in");

fin >> M >> N;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
fin >> module[i][j];

for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++) {
if (!visited[i][j]) {
n++;
visited[i][j] = n;
cnt[n]++;
dfs(i, j);
}
}
fout << n << endl;
int maxn = -1;
for (int i = 1; i <= n; i++)
maxn = max(maxn, cnt[i]);
fout << maxn << endl;
maxn = -1;
char ch;
int x, y;
// 事实证明光靠顺序去重不太可行
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (j < M - 1 && visited[i][j] != visited[i][j+1]) {
int sum = cnt[visited[i][j]] + cnt[visited[i][j+1]];
if (sum > maxn || (sum == maxn && (j < y || (j == y && i > x)))) {
maxn = sum;
ch = 'E';
x = i + 1;
y = j + 1;
}
}
if (i > 0 && visited[i-1][j] != visited[i][j]) {
int sum = cnt[visited[i][j]] + cnt[visited[i-1][j]];
if (sum > maxn || (sum == maxn && (j < y || (j == y && i > x)))) {
maxn = sum;
ch = 'N';
x = i + 1;
y = j + 1;
}
}
}
}
fout << maxn << endl;
fout << x << ' ' << y << ' ' << ch << endl;
return 0;
}

题目来源:https://leetcode.com/problems/unique-paths-iii/description/

标记难度:Hard

提交次数:2/8

代码效率:

  • DP:16ms
  • DFS:4ms

题意

有一个二维的方格图,每个格子里有一个值:

  • 1表示起始格子
  • 2表示终止格子
  • 0表示其他可以走的格子
  • -1表示障碍物

问从起始格子走到终止格子,且把其他可以走的格子都不重不漏地走完一遍的方法总数。

分析

第一个想法就是状态压缩DP啦……但是这次我写好之后却发现f[20][1 << 20]这么大的数组会MLE!!!虽然Leetcode经常只会报RE就是了……然后我稍微试了一下,发现静态数组定义在类私有变量里一定会MLE,定义在函数里则不会MLE,但是也非常靠近MLE的边缘(再来几个栈帧大概也就爆了);如果动态分配数组,Run Code时可以正常运行,但提交时也会MLE。交了八次主要就是在试验这些,最后也没试出来Memory Limit是多少。

总之Leetcode这一点非常烦。结论:用递归写法,用map当数组。

除此之外,这道题还有一点需要注意,就是障碍格子的处理。其他就没有什么了。复杂度是O(N * 2^N),其中N是格子总数。

我之前的非递归写法需要保证已访问格子数少的状态先被计算出来,所以会多出来一个N的常数项,不过因为N一般很小,所以也不是什么大问题。不过递归写法就不需要专门操心格子的计算顺序问题……而且还可以省空间,唉。

另一种方法是DFS……或者说直接暴力。我本来以为这种方法肯定不能过的,结果发现在适当的剪枝下完全可以。但是这个复杂度我就不会估计了。

代码

DP

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
class Solution {
private:
int n, m, N;
map<pair<int, int>, int> f;
int obsMask;
int obsCnt;
int start, end;
int mx[4] = {0, 0, 1, -1}, my[4] = {1, -1, 0, 0};

// state里是包括自己的
int calc(int x, int y, int state, vector<vector<int>>& grid) {
int g = x * m + y;
pair<int, int> p(g, state);
if (f.find(p) != f.end()) return f[p];
// 障碍代表的格子一直都处于visited状态
if (__builtin_popcount(state) == obsCnt + 1) {
if (state == (obsMask | (1 << start)))
f[p] = 1;
else
f[p] = 0;
return f[p];
}
int f1 = 0;
for (int i = 0; i < 4; i++) {
int nx = x + mx[i], ny = y + my[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (grid[nx][ny] == -1) continue;
int ng = nx * m + ny;
if (!(state & (1 << ng))) continue;
f1 += calc(nx, ny, state ^ (1 << g), grid);
}
f[p] = f1;
return f1;
}

public:
int uniquePathsIII(vector<vector<int>>& grid) {
n = grid.size();
m = grid[0].size();
N = m * n;
obsCnt = 0;
for (int i = 0; i < N; i++) {
int x = i / m, y = i % m;
if (grid[x][y] == 2) end = i;
else if (grid[x][y] == 1) start = i;
else if (grid[x][y] == -1) {
obsMask |= 1 << i;
obsCnt++;
}
}
return calc(end / m, end % m, (1 << N) - 1, grid);
}
};

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
private:
bool visited[20][20];
int mx[4] = {0, 0, 1, -1}, my[4] = {1, -1, 0, 0};
int n, m;
int tot;
int ans;

void dfs(int x, int y, int depth, vector<vector<int>>& grid) {
if (depth == tot - 1) {
if (grid[x][y] == 2) ans++;
return;
}
if (grid[x][y] == 2) return; // 一个小的剪枝
for (int i = 0; i < 4; i++) {
int nx = x + mx[i], ny = y + my[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (visited[nx][ny] || grid[nx][ny] == -1) continue;
visited[nx][ny] = true;
dfs(nx, ny, depth + 1, grid);
visited[nx][ny] = false;
}
}

public:
int uniquePathsIII(vector<vector<int>>& grid) {
n = grid.size();
m = grid[0].size();
tot = 0;
int startx, starty;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] != -1) tot++;
if (grid[i][j] == 1) startx = i, starty = j;
}
}
ans = 0;
memset(visited, 0, sizeof(visited));
visited[startx][starty] = true;
dfs(startx, starty, 0, grid);
return ans;
}
};

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

标记难度:Medium

提交次数:1/1

代码效率:8ms

题意

有一颗二叉树,共有N个结点,每个结点上有若干枚硬币,硬币总数为N。每次操作可以把一枚硬币移动到相邻的结点。问最少进行几次操作,才能使每个结点上恰好有一枚硬币?

分析

我觉得这道题挺简单的……

我的思路很简单:先DFS,到达最底层之后判断每个叶结点上的硬币数量node->val是否恰好为1,如果大于1则把多出来的硬币向父结点移动,总移动数量+=node->val-1,如果小于1则把少的硬币向父结点移动,也就是移动-(1-node->val)枚硬币,总移动数量+=1-node->val。对于其他的结点,因为它们的子结点都已经递归处理完了,所以有多出来的硬币的时候,只能向上移动若干枚硬币或者负的若干枚硬币,也就是和叶结点差不多。

这里面比较好的是移动负数枚硬币这个想法,否则可能还得做第二次递归。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
private:
int ans;

int dfs(TreeNode* root) {
if (root == NULL) return 0;
int x = dfs(root->left) + dfs(root->right);
x += root->val;
ans += abs(x - 1);
root->val = 1;
return x - 1;
}

public:
int distributeCoins(TreeNode* root) {
ans = 0;
dfs(root);
return ans;
}
};

题目来源:https://leetcode.com/problems/flip-binary-tree-to-match-preorder-traversal/description/

标记难度:Medium

提交次数:1/1

代码效率:12ms

题意

给定一棵二叉树(每个结点对应的值都是唯一的)和一个前序遍历序列,问,能否通过交换其中一些结点左右子树,使得这棵树的前序遍历结果和给定的相同?

分析

既然是前序遍历,那么接下来的遍历序列中的第一个值必然需要和根结点相同,如果不等,则肯定不能实现。

接下来的问题就是要不要翻转。如果有左子结点,那么下一个值必然是左子结点的值;否则,如果有右子结点,下一个值必然是右子结点的值;否则(也就是说没有子结点),下一个值和之前的遍历相关,可能是父节点的右子结点之类的。

所以做出翻转的决策就很简单:如果左子结点有值,且这个值和遍历序列中预期的下一个值不等,那么就交换左右子树(显然不交换肯定不行了)。判断是否可行的方法也很简单,在上述翻转的基础上,每次都判断当前根结点的值和遍历序列中预期的值是否相等。


事实上,这个判断左子结点的方法是题解[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
class Solution {
vector<int> ans;
int index;
int n;

bool pre(TreeNode* root, vector<int>& voyage) {
if (root == NULL) return true;
if (root->val != voyage[index]) return false;
if (index == n - 1 && (root->left != NULL || root->right != NULL)) return false;
// cout << root->val << endl;
if (root->left != NULL && root->right != NULL && voyage[index + 1] == root->right->val) {
swap(root->left, root->right);
ans.push_back(root->val);
}
index++;
if (!pre(root->left, voyage)) return false;
if (!pre(root->right, voyage)) return false;
return true;
}

public:
vector<int> flipMatchVoyage(TreeNode* root, vector<int>& voyage) {
index = 0;
n = voyage.size();
bool ok = pre(root, voyage);
if (!ok) return {-1};
return ans;
}
};

  1. Leetcode Official Solution - 971. Flip Binary Tree To Match Preorder Traversal

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

标记难度:Easy

提交次数:1/1

代码效率:4ms(100.00%)

题意

判断一棵二叉树中结点的值是否都相同。

分析

直接DFS判断即可。用其他遍历方法当然也行。总之是道很简单的题。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
private:
int univalue;

bool dfs(TreeNode* root) {
if (root == NULL) return true;
if (root->val != univalue)
return false;
return dfs(root->left) && dfs(root->right);
}

public:
bool isUnivalTree(TreeNode* root) {
univalue = root->val;
return dfs(root);
}
};

题目来源:https://leetcode.com/problems/regions-cut-by-slashes/description/

标记难度:Medium

提交次数:2/5

代码效率:

  • 并查集:12ms
  • DFS:28ms

题意

用字符画的形式给定一个N*N的格子里的分割线,如:

1
2
\/
/\

问图中共有多少个连通区域。

分析

比赛的时候我就想到了把每个格子分成四个三角形的方法。但是我当时尝试在类里开一个3600*3600的静态数组,所以RE了。不过它只会RE而不会报MLE,这令人很难调试……反正直接用邻接矩阵肯定是不行的。


一种方法是直接绕开邻接矩阵和邻接表,用并查集来解决。

另一种看起来很神奇的方法[1]是,直接用upscale的思路把每个格子分成9块,然后令线的方格为障碍物,其他方格为可通过,这样也可以做DFS(或者说floodfill)。事实上这种建模的思路是隐式地建了每个小方格和周围的4个方格之间的图。

最后,当然用邻接表+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
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
class Solution {
private:
int _fa[3600];
int N, M;
void init() {
for (int i = 0; i < M; i++)
_fa[i] = i;
}

int fa(int x) {
return x == _fa[x] ? x : _fa[x] = fa(_fa[x]);
}

void merge(int x, int y) {
x = fa(x);
y = fa(y);
_fa[x] = y;
}

public:
int regionsBySlashes(vector<string>& grid) {
// 4N^2 small triangles
N = grid.size();
M = 4*N*N;
init();
// initial merge
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
int n = 4*(i*N + j);
if (i < N - 1) {
int n1 = 4*((i+1)*N + j);
merge(n+2, n1);
}
if (j < N - 1) {
int n1 = 4*(i*N + j+1);
merge(n+1, n1+3);
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int n = 4*(i*N + j);
if (grid[i][j] != '/') {
merge(n, n+1);
merge(n+2, n+3);
}
if (grid[i][j] != '\\') {
merge(n, n+3);
merge(n+1, n+2);
}
}
}
int ans = 0;
for (int i = 0; i < M; i++) {
if (fa(i) == i)
ans++;
}
return ans;
}
};

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
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
class Solution {
private:
int N;
vector<int> G[3600];
void connect(int x, int y) {
G[x].push_back(y);
G[y].push_back(x);
}
bool visited[3600];

void dfs(int x) {
for (auto const& y: G[x])
if (!visited[y]) {
visited[y] = true;
dfs(y);
}
}

public:
int regionsBySlashes(vector<string>& grid) {
N = grid.size();
// initial links
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
int n = 4*(i*N + j);
if (i < N - 1) {
int n1 = 4*((i+1)*N + j);
connect(n+1, n1+3);
}
if (j < N - 1) {
int n1 = 4*(i*N + j+1);
connect(n+2, n1);
}
}
// grid picture
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
int n = 4*(i*N + j);
if (grid[i][j] != '\\') {
connect(n, n+3);
connect(n+1, n+2);
}
if (grid[i][j] != '/') {
connect(n, n+1);
connect(n+2, n+3);
}
}
}

int ans = 0;
memset(visited, 0, sizeof(visited));
for (int i = 0; i < 4*N*N; i++) {
if (!visited[i]) {
visited[i] = true;
ans++;
dfs(i);
}
}
return ans;
}
};

  1. vortrubac's Solution for Leetcode 959 - C++ with picture, DFS on upscaled grid