Leetcode Weekly Contest #134 (1033-1036) 思路与题解
昨晚劲爆法国跑酷没有睡好
这周的 Leetcode 题解，思路上基本都想出来了但是因为泰菜了写出来就 WA 了，于是观摩了一下大佬们的写法再自己写了一遍。
链接在这里说起来这周 uwi 大佬居然被第一名拉了 10min 飞机
1033. Moving Stones Until Consecutive
题目大意
有 3 个数 a, b, c，假设它们按从小到大重新排列后是 x, y, z，每次可以将 x 或者 z 移动到 (x, z) 区间中的任意一个位置（不能和 y 相等），问要把这三个数从原始顺序移动到连续的三个数字排列时所需要的最小和最大移动步数。
Three stones are on a number line at positions a, b, and c.
Each turn, let's say the stones are currently at positionsx, y, zwithx < y < z. You pick up the stone at either position x or position z, and move that stone to an integer positionk, withx < k < zandk != y.
The game ends when you cannot make any more moves, ie. the stones are in consecutive positions.
When the game ends, what is the minimum and maximum number of moves that you could have made? Return the answer as an length 2 array:answer = [minimum_moves, maximum_moves]
思路
直接写。
先排序，然后如果有任意两个数中间刚好隔了一个数的话，那最小移动次数一定是 1，如果已经相邻了，那就是 0，否则就是 2。
设排序后三个数的间隔分别是 d1, d2，则最大移动次数就是 d1 + d2 - 2。
代码
class Solution {
public:
vector<int> numMovesStones(int a, int b, int c) {
if (a > b) swap(a, b);
if (b > c) swap(b, c);
if (a > b) swap(a, b);
auto mn = 0, mx = 0;
if (b - a > 1) {
mx += b - a - 1;
mn += 1;
}
if (c - b > 1) {
mx += c - b - 1;
mn += 1;
}
if (b - a == 2 || c - b == 2)
mn = 1;
return vector<int>({mn, mx});
}
};1034. Coloring A Border
题目大意
输入一个矩阵，对于任意一个位置，与其上下左右相邻且值相同的部分，以及由这些部分以相同的方法所拓展能够到达的所有元素称为一个 "区域"，输入一个初始坐标 (r0, c0)，要求将这个坐标所在的区域边界（严格定义为：边界元素或其四个相邻的元素中有任意一个值与其不相同）全部设置为输入的值。
思路
直接 bfs 或者 dfs 区域拓展，然后把边界设置了就行。
代码
代码写得比较丑... 见笑。
class Solution {
public:
int origin;
int t;
vector<vector<bool>> visited;
bool judge(vector<vector<int>> &grid, int r, int c) {
if (r < 0 || c < 0 || r >= grid.size() || c >= grid[0].size()) return false;
if (visited[r][c]) return false;
if (grid[r][c] != origin) return true;
return false;
}
vector<vector<int>> colorBorder(vector<vector<int>>& grid, int r0, int c0, int color) {
origin = grid[r0][c0];
t = color;
visited = vector<vector<bool>>(grid.size());
for (int i = 0; i < grid.size(); ++i)
visited[i] = vector<bool>(grid[0].size());
paint(grid, r0, c0);
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if ((i == 0 || j == 0 || i == grid.size() - 1 || j == grid[0].size() - 1) && visited[i][j]) {
grid[i][j] = color;
continue;
}
if (visited[i][j] && (judge(grid, i-1, j) || judge(grid, i+1, j) || judge(grid, i, j+1) || judge(grid, i, j-1))) {
grid[i][j] = color;
continue;
}
}
}
return grid;
}
void paint(vector<vector<int>> &grid, int r, int c) {
if (r < 0 || c < 0 || r >= grid.size() || c >= grid[0].size()) return;
if (visited[r][c]) return;
if (grid[r][c] != origin) return;
visited[r][c] = true;
paint(grid, r + 1, c);
paint(grid, r - 1, c);
paint(grid, r, c - 1);
paint(grid, r, c + 1);
}
};1035. Uncrossed Lines
题目大意
输入两个一维向量，想象它们左侧对其分布在两行。现将上下的相同的元素连线，每个元素只能连一次，且不能有交叉，问最多能连多少个线出来？
例：
1 2 4
| /
1 4 2
输出：
2
思路
朴素dp。
我一开始还觉得是背包问题... swtcl，下面是 dp 的严格证明
对于两个数组 A, B，设
dp[i][j]代表A[i...]和B[j...]的最多能连的线的数量，则有：
显然若
A[i] == B[j]，即两个数组（A[i...], B[j...]）的第一个元素相同，那么这两个元素一定能连线
- 此时
dp[i][j] = 1 + dp[i+1][j+1]若
A[i] != B[j]，则有
dp[i][j] = max(dp[i+1][j], dp[i][j+1])- 若
A[i...]或B[j...]为空数组，则dp[i][j] = 0
可以很容易发现 dp 数组只依赖其右侧和下侧的值，因此从右下往左上扫描一次即可得出答案，答案为dp[0][0]
代码
class Solution {
public:
int dp[501][501];
int n, m;
int maxUncrossedLines(vector<int>& A, vector<int>& B) {
memset(dp, 0, sizeof(dp));
for (int j = B.size() - 1; j >= 0; --j)
for (int i = A.size() - 1; i >= 0; --i)
if (A[i] == B[j])
dp[i][j] = 1 + dp[i+1][j+1];
else
dp[i][j] = max(dp[i+1][j], dp[i][j+1]);
return dp[0][0];
}
};1036. Escape a Large Maze
题目大意
固定一个 10^6 x 10^6 大的方形地图，输入一个 blocked 数组表示不能走的坐标，输入起点和终点，问能否从起点走到终点？取值范围如下：
0 <= blocked.length <= 200
blocked[i].length == 2
0 <= blocked[i][j] < 10^6
source.length == target.length == 2
0 <= source[i][j], target[i][j] < 10^6
source != target思路
由于地图太大，从而导致路径很长，而且因为地图相对很空，所以直接 bfs 或者 dfs 会炸内存... 考虑到 blocked 的元素数量并不多，因此只有以下情况迷宫无解：
- 起点被包了一圈走不出去
- 终点被包了一圈走不出去
起点和终点之间被完全隔开了（不可能）
- 因为
blocked的长度并不够长，因此只可能是 1 和 2 的情况。
- 因为
所以，只需要从起点开始进行 bfs 或者 dfs 搜索，搜索的路径长度限制为 blocked 的数量，如果在这个限制范围内发现走不出去，那么输出 false，如果路径长度限制达到了而前面还有没访问过的位置，说明这个搜索起始点没有被围住。
另外路径长度限制为
blocked是因为：要将一个点围住，即使利用边界，其构成的图形大概是一个等腰直角三角形，从这个三角形内任意一点出发，最远所需要的离开区域的路径长度是blocked的长度。
（粗略估计，我还没有严格在纸上证明，但可以看一下题目的 discuss 区域，似乎有人给出了证明）
Disscuss-带图形的几种情况演示
代码
class Solution {
public:
set<pair<int,int>> block;
bool f(vector<int> s, vector<int> t) {
set<pair<int,int>> visited;
queue<pair<int,int>> q, q2;
q.push({s[0], s[1]});
int n = block.size();
while (n-- > 0) {
while (!q.empty()) {
auto i = q.front();
q.pop();
if (block.find(i) != block.end()) continue;
if (visited.find(i) != visited.end()) continue;
if (i.first < 0 || i.second < 0 || i.first >= 1000000 || i.second >= 1000000) continue;
if (i.first == t[0] && i.second == t[1]) return true;
visited.insert(i);
q2.push({i.first+1, i.second});
q2.push({i.first-1, i.second});
q2.push({i.first, i.second+1});
q2.push({i.first, i.second-1});
}
swap(q, q2);
}
// q 是空的话说明所有元素都被访问过处理完了，非空说明还有没走过的地方
return !q.empty();
}
bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
for (auto it: blocked)
block.insert({it[0], it[1]});
return f(source, target) && f(target, source);
}
};