LCR 101. 分割等和子集
Note: 可以用dp[j]
来表示容量为j
的背包能装下的数的最大和,但是有额外的计算,官解使用的是用dp[j]
来表示容量为j
的背包是否能被装满,那么放第i
个数字时,dp[j]
取决于上一层的dp[j]
(不放第i
个数),以及上一层的dp[j - nums[i]]
(放第i
个数),则dp[j] |= dp[j - nums[i]]
。注意dp[0] = true
。
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0, n = nums.size();
for (auto& num: nums) sum += num;
if (sum % 2 == 1) return false;
int capacity = sum / 2;
vector<int> dp(capacity + 1);
dp[0] = true;
for (int i = 0; i < n; ++i) {
for (int j = capacity; j >= nums[i]; --j) {
dp[j] |= dp[j - nums[i]];
}
}
return dp[capacity];
}
};
LCR 104. 组合总和 Ⅳ
Note: 回顾: 背包问题中,如果将二维dp
数组优化到一维,那么0-1背包问题
一定是物品在外,背包在内,并且背包的遍历必须是倒序的,原因是0-1背包
只使用左上和上方的值计算,因此必须从右到左;必须物品在外的原因是,如果背包在外,那么就相当于从最右列向左计算,此时左上是没有被计算的,一定是0,因此相当于每个背包只放入了一个物品;
而对于完全背包
,由于物品数量无限,因此依赖的值是左侧(同层)和上方,在使用一维dp
数组时必须从左到右。但物品和背包谁的循环在外面并无规定,因为背包在外时,相当于从最左列向右计算,所依赖的左侧和上方的值是可用的。但是也有细微的区别,因为物品在外时,类似于组合问题,一个物品在本层用完,就不会继续用,因此所得结果是组合结果;但背包在外时,每个背包会检查一遍所有的物品,到下一个背包时,会重新检查一遍所有的物品,这就导致最后的结果其实是一个排列结果。比如103. 零钱兑换
中,使用的就是物品在外的组合结果,而104. 组合总和 Ⅳ
中使用的是背包在外的排列结果。
LCR 106. 判断二分图
Note: 这个题使用的是dfs染色,当然bfs也可以。根据二分图的定义,所有边的两个点必须在不同集合中,因此同一个集合中的点不能有连接(否则它们分别在两个集合中),那么我们可以深度遍历整个图,然后对连续两条边染成不同颜色,实际上只需要两种颜色,交替染色就可以,例如红-蓝-红-蓝
,这里的深度遍历函数可以返回bool
,也可以用全局变量来记录,一旦当前遍历的点已被染色并且不是期望的颜色(比如当前点染了红色,但是期望是蓝色,因为其上一层的节点染红色),那么整个搜索过程结束,该图不是二部图,需要返回false
或者置全局变量为false
,也就是说,搜索结束的标志是某一条路径失败。如果搜索了整个图,没有路径失败,那么该图就是二部图。
class Solution {
public:
vector<int> color;
bool valid = true;
void dfs(int cur, int c, vector<vector<int>>& graph) {
color[cur] = c;
int next = !c;
for (auto& neighbor: graph[cur]) {
if (color[neighbor] == -1) {
dfs(neighbor, next, graph);
if (!valid) return;
} else if (color[neighbor] != next) {
valid = false;
return;
}
}
return;
}
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
color.assign(n, -1);
for (int i = 0; i < n; ++i) {
if (color[i] == -1) {
dfs(i, 0, graph);
if (!valid) return false;
}
}
return true;
}
};
LCR 107. 01 矩阵
Note: 由于0
到最近0
的距离都是0
,因此我们实际是找所有1
到其最近0
的距离。由于找最短距离,因此考虑广度优先搜索,一开始的考虑是对所有的1
来进行BFS,找到其与最近0的距离,但很明显这样有很多重复计算,假设只有一个0
,那么岂不是对于矩阵的每个位置,都要搜索整个矩阵,复杂度将达到O(n4)
,太高了!
反向思考,从所有的0
同时开始找1
,反正我只是要最近的0
,哪个位置0
又无所谓,为什么不能将所有的0
看成一个整体同时开始搜索呢?这是可以的,并且很合理,所有的0
一起进入队列,同时出发,每轮各走1
步,如果谁找到了1
,这个1
就归找到它的0
,当前0
也就是这个1
的最近0
,因为别的0
还没有到达这个1
,此时这个1
离最近0
的距离也就得出了,就是BFS到达这个1
时所走的距离。由于这个距离是逐步+1递增的,因此每一步走到的位置(如果是1)其与最近0的距离 = 上一步走到的位置与最近0的距离 + 1
,可以直接在答案数组中进行这一操作(因为这个距离就是我们要求的答案),注意所有0
离最近0
的距离是0
。其时间复杂度和空间复杂度均为O(mn)
,因为最坏情况下所有的节点都入队并出队一次。
class Solution {
public:
// int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
// 广度优先搜索
queue<pair<int, int>> que;
int row = mat.size(), col = mat[0].size();
vector<vector<bool>> vis(row, vector<bool>(col));
vector<vector<int>> ans(row, vector<int>(col));
// 所有0在初始时进入队列,视为一个整体
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
if (mat[i][j] == 0) {
vis[i][j] = true;
que.emplace(i, j);
}
}
}
while (!que.empty()) {
auto [x, y] = que.front(); que.pop();
for (int i = 0; i < 4; ++i) {
int nextx = x + dir[i][0], nexty = y + dir[i][1];
if (nextx < 0 || nextx >= row || nexty < 0 || nexty >= col || vis[nextx][nexty]) continue;
que.emplace(nextx, nexty);
// 离最近0的距离 = 上一步离最近0的距离 + 1
// 初始队列中所有0离最近0的距离是0,因此第一轮找到的1,离最近0的距离就是1,以此类推
ans[nextx][nexty] = ans[x][y] + 1;
// 注意在入队时标记访问,否则会造成节点重复入队
vis[nextx][nexty] = true;
}
}
return ans;
}
};
另外一种方法是使用动态规划,其主要思想和上面类似,但是方向相反,上面的方法是从0
出发找1
,而动态规划的思想是从1
找0
(上面说过如果使用BFS从1
找0
会造成大量重复计算,动态规划可以解决这个问题),对于矩阵中每一个1
,其只可能从上下左右四个方向去找最近0
,如果它4个方向位置到最近0
的距离都已知,那么我们不就可以从这四个距离中取最小,然后再+1(从这个1
迈出的第一步),不就算出了这个1
到最近0
的距离了?
因此可以考虑使用动态规划,dp[i][j]
表示位置(i, j)
到最近0
的距离,初始时所有0
位置的dp[i][j]
都为0
,对于每一个1
,其需要考虑左上、左下、右上、右下四个位置的全部0
,但其实不用考虑这么多,只需要考虑左上和右下位置,也就是递推时,先从左上推到右下,再从右下推到左上,对于某个位置(i, j)
右上的0
,其右边的某个位置(i, k) (k > j)
在考虑左上的0
时,已经考虑过这些0
,而在从右下推到左上的过程中,(i, j)
一定是考虑了其右边的位置(i, k)
,因此顺带也就考虑了这些0
;左下同理,(i, j)
下边的某个位置(m, k) (m > i)
在考虑左上0
时,也就相当于考虑了(i, j)
的左下0
,然后其之后被(i, j)
所考虑,因此也就相当于(i, j)
已经考虑了全部左下0
。
那么,这个方法是完备的,同样可以在答案数组上直接递推,初始时,所有0
的位置,dp[i][j]
都是0
,其他位置设置一个很大的数以便取最小值。时间和空间复杂度同样都是O(mn)
,因为dp
数组占用mn
的大小,并且计算需要mn
的时间。
class Solution {
public:
// int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
// 动态规划,从四个方向离最近0的距离取最小值+1
int row = mat.size(), col = mat[0].size();
vector<vector<int>> ans(row, vector<int>(col, INT_MAX / 2));
// 从左上推到右下
for (int i = 0; i < row; ++i) {
for (int j = 0; j < col; ++j) {
// 在从左上推到右下时,由于每个0只会被右下位置考虑,
// 而右下一定是在此位置之后才访问的,因此在这里初始化0也是可以的,避免了单独初始化的额外遍历开销
if (!mat[i][j]) {
ans[i][j] = 0;
continue;
}
// 考虑上方0
if (i > 0) ans[i][j] = min(ans[i][j], ans[i - 1][j] + 1);
// 考虑左侧0
if (j > 0) ans[i][j] = min(ans[i][j], ans[i][j - 1] + 1);
}
}
// 从右下推到左上
for (int i = row - 1; i >= 0; --i) {
for (int j = col - 1; j >= 0; --j) {
if (!mat[i][j]) continue;
// 考虑下方0
if (i + 1 < row) ans[i][j] = min(ans[i][j], ans[i + 1][j] + 1);
// 考虑右侧0
if (j + 1 < col) ans[i][j] = min(ans[i][j], ans[i][j + 1] + 1);
}
}
return ans;
}
};
LCR 108. 单词接龙
Note: 双向BFS经典题,由于从两边交替生长,因此大大减小了搜索空间。注意这里的时间复杂度,如果单词表长度N
,单词长度C
,那么对于每一个单词,其每一个位置可以突变出26
种突变体,忽略常数,也就是每个单词花O(C)
时间生成新节点,对于N
个单词,生成新节点的总时间是O(N * C)
。由于BFS
可能会访问每个节点,而对于每个节点进入哈希表等相关操作需要O(C)
时间(其长度为C
),因此总的时间复杂度和空间复杂度都在O(N * C2)
量级。但是双向BFS相比单向BFS,时间复杂度肯定低的多(实际生成更少的节点,而且我们每次都是选择节点数少的那一颗树来生长)。
LCR 109. 打开转盘锁
Note: 和上题一模一样,
LCR 110. 所有可能的路径
Note: 这题由于保证没有环,因此不需要visit
数组来记录访问。
LCR 111. 除法求值
Note: 方法一,建图并且使用DFS或BFS,这里以DFS为例,首先确定终止条件是当前访问的节点为终止节点,在这里的语义就是,从被除数出发到达了除数,DFS过程就终止,一路上不断积累各节点的乘积,最后的结果就是被除数/除数。在DFS的过程中,要注意可能有环的存在,因此需要visited
数组,但是不需要回溯,因为在一次查询中,我们只是需要找到一条从被除数到除数的路径,而不是全部的路径,因此一个节点如果已访问过,并且我们知道他能到达终点,那么一旦到达终点,DFS立即结束,然后递归向上结束;如果我们知道他不能到达节点,那么无论我在哪条路径上访问他,他都不能到达终点,因此没有必要对其进行回溯,直接保留visited
标志即可,否则将会多次访问无意义节点,造成时间浪费。
考虑到如果图特别大,每次查询都去深搜会导致重复操作,因此我们使用memory
来记忆搜索结果,此时递归函数参数是 递归起点start
,当前节点cur
和当前累计乘积res
(实际是开始节点到当前节点的商,也就是start / cur
),以及结束节点end
,和访问标记数组visited
。原因是我需要在DFS函数中去记录memory[start][cur] = res
(而不是memory[cur][end]
!因为我只是从start
搜到了cur
,要记录的是这条路径)以及memory[cur][start] = 1 / res
。在DFS的开始,需要访问memory
查看是否cur到end的路径(或反向路径)
已在记录中,已在则直接返回res
(cur之前的路径累乘) 和memory[cur][end]
(cur之后的路径累乘)的乘积。
class Solution {
public:
unordered_map<string,unordered_map<string,double>> edges{};
// unordered_map<string, unordered_map<string, double>> memory{};
double dfs(const string& start, const string& cur, const string& end, double res, unordered_set<string>& visited) {
// 记忆化DFS,可选,主要用于缓存计算结果避免重复计算
// 先检查是否已有未来路径(cur到end)结果,有则直接返回全路径结果
// if (memory.count(cur) && memory[cur].count(end)) return res * memory[cur][end];
// else if (memory.count(end) && memory[end].count(cur)) return res * 1 / memory[end][cur];
// 缓存的是历史路径(start到cur)的路径结果
// memory[start][cur] = res;
// memory[cur][start] = 1 / res;
if (cur == end) return res;
// 注意这里,因为只需要找一条路径,visited不需要回溯!
visited.emplace(cur);
for (auto& [next, value]: edges[cur]) {
if (!visited.count(next)) {
double gain = dfs(start, next, end, res * value, visited);
if (gain != -1.0) return gain;
}
}
return -1.0;
}
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
int n = equations.size();
for (int i = 0; i < n; ++i) {
string& s = equations[i][0], & u = equations[i][1];
edges[s][u] = values[i];
edges[u][s] = 1 / values[i];
}
unordered_set<string> visited;
int q = queries.size();
vector<double> ans(q);
for (int i = 0; i < q; ++i) {
visited.clear();
string &s = queries[i][0], &e = queries[i][1];
// if (s == e) {ans[i] = 1.0; continue;}
if (!edges.count(s) || !edges.count(e)) {ans[i] = -1.0; continue;}
ans[i] = dfs(s, s, e, 1.0, visited);
}
return ans;
}
};
方法二可以用Floyd-warshell
算法去计算任意两个节点之间的距离(商),查询时每次是O(1)
时间(不算字符串哈希时间的话)。但是吧,说实话有点浪费,因为预处理时间至少O(n3)
,不过在大量查询的情况下应该还是很有用的。
方法三使用的是带权并查集,这题一开始确实可以想到用并查集,但是由于并查集在路径压缩的过程中会丢失信息,因此要想办法保存边权信息,最好的解决办法就是使用一个w
数组来保存每个节点相对于父节点的权值(在本题意义下就是商),在路径压缩的过程中可以通过一些操作来维护每个节点的 w
值。具体而言就是,w[i]
表示i
与其父节点f[i]
的比值,在路径压缩时,由于压缩路径上的每个节点最终都连接到路径起点,因此需要在递归的过程中不断累计比值(商)的乘积。
由于在原本的写法f[x] = find(f[x])
中,原本的父亲节点会丢失,因此需要在递归前保存,而在递归过程中,原本离起点最近的节点(其父节点为起点)应该先将自己的w
值乘以父节点的w
值,从而其w
值变为相对于起点的比值,然后往上递推,由于递归回溯的时候,父节点已经完成该操作,也就是w[父] = 父 / 起点
,那么由于此时w[子] = 子 / 父
,因此w[子] * w[父] = 子 / 起点
,这样路径上全部节点的w
值都变为相对于起点的比值(商),然后再将其父节点设为起点,就完成了路径压缩的语义。综上,应该在递归前一句保留原本的父节点,然后在递归后一句来进行w
值的累计(因为越底层的递归越先进行这一操作)。
int find(int x) {
if (f[x] != x) {
// 保留原本父亲
int father = f[x];
// 递归路径压缩
f[x] = find(f[x]);
// 自底向上累积比值,乘以原本父亲的w值
// 最后w[x]变为相对于路径起点的比值
w[x] *= w[father];
}
return f[x];
}
而在合并节点时,先找到两个节点x
和y
的根节点fx
和fy
,然后合并根节点,注意这里如果原来的x
和y
的比值是val
的话,即x / y = val
,那么在通过find进行路径压缩后,w[x] = x / fx
,同时w[y] = y / fy
,因为要使得f[fx] = fy
(合并),那么很明显要更改w[fx]
的值为fx / fy
:
void merge(int x, int y, double val) {
int fx = find(x), fy = find(y);
f[fx] = fy;
w[fx] = val * w[y] / w[x];
}
这题还有一个注意是初始化,w
应该全部初始化为0
(对应f[i]
初始化为i
的语义,初始时w[i] = i / f[i] = i / i = 1
)。还有就是不能偷懒不把字符串映射成数字,不然太浪费空间(Hh)。
class Solution {
public:
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
// 带权并查集
int n = equations.size(), idx = 0;
unordered_map<string, int> vertices;
for (auto& equation: equations) {
string& s = equation[0], & e = equation[1];
if (!vertices.count(s)) vertices[s] = idx++;
if (!vertices.count(e)) vertices[e] = idx++;
}
UnionFind unionf(idx);
for (int i = 0; i < n; ++i) {
string& s = equations[i][0], & e = equations[i][1];
unionf.merge(vertices[s], vertices[e], values[i]);
}
int q = queries.size();
vector<double> ans(q);
for (int i = 0; i < q; ++i) {
string& s = queries[i][0], & e = queries[i][1];
if (!vertices.count(s) || !vertices.count(e)) {ans[i] = -1.0; continue;}
int& sv = vertices[s], & ev = vertices[e];
if (unionf.find(sv) == unionf.find(ev)) ans[i] = unionf.w[sv] / unionf.w[ev];
else ans[i] = -1.0;
}
return ans;
}
struct UnionFind {
vector<int> f;
vector<double> w;
UnionFind(int n): f(n), w(n, 1.0) {
for (int i = 0; i < n; ++i) f[i] = i;
}
int find(int x) {
if (f[x] != x) {
int father = f[x];
f[x] = find(f[x]);
w[x] *= w[father];
}
return f[x];
}
void merge(int x, int y, double val) {
int fx = find(x), fy = find(y);
f[fx] = fy;
w[fx] = val * w[y] / w[x];
}
};
};
当然不定义并查集结构也可以,函数和数组都设为类变量。
LCR 112. 矩阵中的最长递增路径
Note: 方法一,使用记忆化DFS,这里我们再次讨论一下DFS中visited
和memory
的使用,首先需要明确,这两个数组是用来干什么的,为什么要使用它们,什么时候使用它们,使用的时候有什么注意事项。
对于visited
数组,其作用是防止在一次DFS中重复访问相同节点,因此在递归进入下一层以前,需要置当前节点的访问位visited
为真,但是这个访问标志位是否需要回溯,是分情况的, 如果我当前是在寻找一条路径,那么实际上我并不需要回溯,前面已经说过,找到了就是找到了,找不到你换一条路还是找不到,因此回溯无意义;如果是在寻找全部路径,那就必须回溯,不然无法访问到全部路径;至于使用visited
的时机,应该是在单次BFS过程中存在回环可能得时候,比如走迷宫,有可能会走回来,但在本题中,已经严格规定是一条合法路径必须是递增
,那么这就意味着一旦我走过了一个格子,我不可能在这条路径上再次访问该格子,因此不会有回环,我也就根本不需要visited
,但是如果条件变为非递减
,就不一样了,如果一条路径上全是相等的值,我是有可能走回当前格子的,这个时候就需要visited
数组。
对于memory
数组,也就是所谓的记忆化回溯
,主要其实是为了解决多次DFS过程的重复计算而设置的,因为多次DFS意味着可能有很多起点,不同起点出发的路径整体虽然是不一样的,但是子路径可能是完全一样的,再次计算就是浪费,所以这时候就需要memory
来保存当前节点计算的结果,下次访问该节点时直接返回缓存的结果,这里保存的“结果”,实际上是当前节点到目标节点的路径信息,大概的语义就是,我走到了某个节点,并且想知道这个节点到目标节点的路径信息,如果我已经计算过了,那我就无需再计算一遍,直接返回我以前的计算结果就行。
class Solution {
public:
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
int dfs(int x, int y, vector<vector<int>>& matrix, vector<vector<int>>& memory) {
// 如果当前节点到目标节点的路径已经计算过,直接返回结果
if (memory[x][y]) return memory[x][y];
int row = matrix.size(), col = matrix[0].size(), maxLength = 1;
for (int i = 0; i < 4; ++i) {
int nextx = x + dir[i][0], nexty = y + dir[i][1];
if (nextx < 0 || nextx >= row || nexty < 0 || nexty >= col || matrix[nextx][nexty] <= matrix[x][y]) continue;
maxLength = max(maxLength, dfs(nextx, nexty, matrix, memory) + 1);
}
memory[x][y] = maxLength;
return maxLength;
}
int longestIncreasingPath(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
// memory初始化全为0,因为只要计算过就至少是1
vector<vector<int>> memory(m, vector<int>(n));
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
ans = max(ans, dfs(i, j, matrix, memory));
}
}
return ans;
}
};
由于DFS的时间复杂度为O(V + E)
,其中V
是顶点个数,E
是边数量,在这类上下左右扩展问题中,V = mn
(矩阵高乘宽),而每个顶点最多有4
条边,因此边数量最多为4mn
,因此总的时间和空间复杂度都为O(mn)
。
方法二是使用类似于拓扑排序的思想,最长递增路径的终点位置,其四周必定都是≤其的元素,否则该路径长度还可以增加,该路径也就不是最长递增路径,因此我们记矩阵中每个位置,其四周值>其的位置个数为其出度outdegrees
(也就是图中以该位置为起点的边数)。我们首先找所有出度为0
的位置,将其放入队列,开始广度优先搜索,但注意,这里的搜索是逆向搜索,也就是,是从递增路径的最后一个位置往前找,找比当前节点小的节点,然后对找到的节点,出度-1,当这个节点出度变为0
,我们将其加入队列,如此进行广度搜索直到队列为空,搜索的层数即为最长递增路径长度。
为什么只将出度为0
的节点加入队列呢?主要是为了防止节点重复加入队列,比如有路径1->5
1->4
和1->3->4->5
(假设这里的1
是同一位置),如果按照朴素的的BFS,那么1
将会被重复加入队列多次。在一个节点出度变为0
的时候,我们可以确定后面搜索的元素不会比其大了(只有已经搜索过的才比他大),这时我们才能放心地将此节点加入队列,否则后面搜索的节点有比当前节点大的,就会造成当前节点重复加入,可能造成超时。
class Solution {
public:
int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
int longestIncreasingPath(vector<vector<int>>& matrix) {
// 拓扑排序
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> outdegrees(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < 4; ++k) {
int nexti = i + dir[k][0], nextj = j + dir[k][1];
if (nexti < 0 || nexti >= m || nextj < 0 || nextj >= n) continue;
// 每有一条边,出度+1
if (matrix[nexti][nextj] > matrix[i][j]) ++outdegrees[i][j];
}
}
}
queue<pair<int, int>> que;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
// 出度为0,可以作为路径末尾节点,入队
if (!outdegrees[i][j]) que.emplace(i, j);
}
}
int ans = 0;
while (!que.empty()) {
++ans;
int size = que.size();
// 层序遍历,每层只选择合法元素,也就是到目前为止出度为0的元素
// 因为只有这样才能保证后来搜索的元素不会比当前元素大,从而不会重复入队
// 最后搜索的层数即为最大路径长度
for (int i = 0; i < size; ++i) {
auto [x, y] = que.front(); que.pop();
for (int k = 0; k < 4; ++k) {
int nextx = x + dir[k][0], nexty = y + dir[k][1];
if (nextx < 0 || nextx >= m || nexty < 0 || nexty >= n) continue;
if (matrix[nextx][nexty] < matrix[x][y]) {
--outdegrees[nextx][nexty];
if (!outdegrees[nextx][nexty]) que.emplace(nextx, nexty);
}
}
}
}
return ans;
}
};
由于拓扑排序的时间空间复杂度也是O(V + E)
,因此理论上两种方法的复杂度是一样的,但是其实这一方法明显要比DFS慢,因为出度的计算和初始化队列占用了较多的时间,但是避免了BFS带来的重复入队的问题,是BFS下的最优解。
官解的最后给出了几个思考题:
- 「方法一」中使用了记忆化存储和深度优先搜索,这里的深度优先搜索可以替换成广度优先搜索吗?
答:是不可以的,因为记忆化储存存的是从当前节点到终点的路径信息,这个路径信息是我要对从当前节点出发的所有路径全部搜索完毕之后才知道的,而在BFS中,节点是一层一层搜索的,我无法知道从当前节点出发的所有路径的信息,因此无法使用记忆化存储回溯(非要说记忆化的话,我可以存从起点到当前节点的路径信息,但是这和记忆化的原本思想背道而驰了,可以起到一点加速作用但不多) - 「方法二」中基于拓扑排序对排序后的有向无环图做了层次遍历,如果没有拓扑排序直接进行广度优先搜索会发生什么?
答:之前已经说过,拓扑排序的目的是保证后面搜索的节点不会比前面的大,避免前面的节点重复入队。因此不使用拓扑排序进行BFS的话就会造成超时。 - 「方法二」中如果不使用拓扑排序,而是直接按照矩阵中元素的值从大到小进行排序,并依此顺序进行状态转移,那么可以得到正确的答案吗?如果是从小到大进行排序呢?
答:为什么要进行拓扑排序,主要还是为了保证搜索元素是有序的,比如本题中的从大到小,那如果元素与已经按从大到小排列,我直接进行递减(当前>下一个)的BFS即可;反之就是递增的BFS,同样可以得到正确答案。 - 「变式」给定一个整数矩阵,找出符合以下条件的路径的数量:这个路径是严格递增的,且它的长度至少是 3。矩阵的边长最大为 103,答案对 109 + 7 取模。其他条件和题目相同。思考:是否可以借鉴这道题的方法?
答:应该是可以的,见 2328. 网格图中递增路径的数目 。只不过是本来的maxLength = max(maxLength, dfs(nextx, nexty, matrix, memory) + 1)
修改为paths = paths % mod + dfs(nextx, nexty, matrix, memory) % mod
。对于拓扑排序方法,类似,只不过不再需要层序遍历(这里使用层序遍历是因为要找的是路径长度,最大路径长度也就等于搜索的层数),而是同时使用dp
(实际上这里也相当于在使用dp
,maxLength[nextx][nexty] = max(maxLength[nextx][nexty], maxLength[x][y] + 1)
,maxLength[x][y]
表示从(x, y)
出发的最长递增路径长度,由于(nextx, nexty)
一定是在(x, y)
的正好下一层被遍历的,因此使用层序遍历更方便)。这里的dp
推导式是,paths[nextx][nexty] = paths[nextx][nexty] % mod + paths[x][y] % mod
,这就类似于dp
中的逆序推导,所谓的无后效性,因为这里(nextx, nexty)
位置的值一定比(x, y)
小,因此从(x, y)
出发的递增路径是不受(nextx, nexty)
影响的,相反,从(nextx, nexty)
出发的递增路径是受(x, y)
影响的并且由于他们是邻居((x, y)
一定是(nextx, nexty)
的下一位),存在如上的递推关系式。这里的拓扑排序就是将无序的矩阵变为了有序的矩阵,才能够按照dp
关系式递推。另外,值得注意的是,拓扑排序在存在环的时候是无法进行的,因为都不一定能找到入度为0
的节点,而方法一的DFS只是需要加一个visited
数组。
LCR 113. 课程表 II
Note: 经典拓扑排序,广度深度均可。不过一般广度比较好理解,也就是先将入度为0
的所有节点(这里是无依赖课程)入队,然后取出放入答案,再遍历其邻居节点,遍历到的邻居节点入度-1,如果产生了新的0
入度节点,就加入队列,重复上述过程直到队列为空。队列为空不意味着拓扑有效,还需要检查最后拓扑序(答案)中的元素个数是否等于元素总个数,不是就说明拓扑失败,是才说明成功。
当然也可以深度遍历拓扑,DFS拓扑的思想是,对每个节点遍历进行DFS,进入时置节点访问位为1
代表正在访问(0
代表未访问过,2
代表访问完毕),如果在DFS过程中遇到访问标志为0
的邻居节点,可以进入下一层访问该节点,但是如果遇到访问标志为1
的邻居节点,则说明有向环存在,拓扑失败,需要将全局合法标志置为false
,然后直接返回,上层发现该标志为false
也立即返回(相当于DFS返回值为bool,找到了一条不合法路径)。如果没有遇到环,那么当前节点在搜索完成后,置访问标志位为2
,即访问完毕,同时将当前节点放入答案末尾,由于这一步是在递归完成后进行的,因此答案的前面是底层元素,后面是上层元素,就相当于倒序,先是被依赖课程,后是依赖课程。
在对某个节点的DFS过程中,从这个节点出发可到达的节点(也就是依赖这个节点的节点,在正确答案中应该在该节点后面)都被放到了该节点之前,而从这个节点无法到达的节点(可能是前置节点,或者无关节点,总之在正确答案中都在该节点前面)将会在后续的遍历中放到该节点之后,那么因此我在完成上述的全部节点的DFS过程之后,将所得的答案翻转,也就得到了最终的正确答案。其实这里的答案也就类似于栈,后访问的先入栈。
class Solution {
public:
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
// DFS拓扑
visited.resize(numCourses);
edges.resize(numCourses);
for (auto& prerequisite: prerequisites) {
edges[prerequisite[1]].emplace_back(prerequisite[0]);
}
for (int i = 0; i < numCourses; ++i) {
if (!visited[i]) {
dfs(i);
if (!isValid) return {};
}
}
reverse(result.begin(), result.end());
return result;
}
// 深度优先搜索
vector<int> visited;
vector<vector<int>> edges;
bool isValid = true;
vector<int> result;
void dfs(int n) {
visited[n] = 1;
for (auto& next: edges[n]) {
if (!visited[next]) {
dfs(next);
if (!isValid) return;
// 成环,失败
} else if (visited[next] == 1) {
isValid = false;
return;
}
}
// 访问完毕
visited[n] = 2;
result.emplace_back(n);
}
};
如果是无环,那么不需要visited
,直接后递归入栈即可。
LCR 114. 火星词典
Note: 和上一题基本一致,主要是建图方面注意,这里的字母虽然都是小写,但是并不是每个字母都出现在单词表中,因此如果用长度为26*26
的数组来存边,在DFS/BFS时是不好搜索的,因为不知道有哪些字母实际出现了,最好还是使用哈希表。如果是无权图,map
套vector
即可,有权图需要map
套map
来储存边权。
LCR 115. 序列重建
Note: 还是拓扑。这里每个子序列内部元素的先后顺序就代表了有向边,我们在对图进行拓扑(BFS)时,每一次取队头元素实际上是在确定最短唯一超序列(也就是拓扑序)的每一位,那么就需要判断每个位置是否只有一个选择,如果不是,那么所给的原序列nums
明显不是超序列(这里有两种可能性,有可能是sequences
里面根本就没出现nums
的某些元素,此时nums
连最短超序列都不是;如果是sequences
包含了nums
的全部元素,但在某一次选择时有多个元素入度为0
,此时nums
是最短超序列,但当前位置有多个选择,nums
也就不是唯一最短超序列了)。
另外呢,本题实际上是在求能不能找到从nums
第一位到最后一位的一条连续路径,因为如果能找到,那么nums
中每一个有向关系都被sequences
满足(从连续两个元素关系可以推到全部元素),由于每一个sequences
中的序列都是nums
的子序列,这意味着sequences
中每一个有向关系本来就被nums
满足,这就意味着nums
和sequences
是完全等价的,nums
刚刚好包含了整个sequences
,而且任意两个连续元素不可交换,当然就是最短唯一超序列;反之,nums
有至少一对连续元素的有向关系在sequences
中找不到,那意味着这对元素在最短超序列中的位置可以交换,最短超序列不是唯一的,或者是sequences
中不包含nums
里的部分元素,nums
不是最短超序列,总之,这种情况下nums
必定不是最短唯一超序列。
那么我们用一个next
数组去保存nums
中每一个连续对的有向关系(i, j)
,记为next[i] = j
,然后去sequences
检查它们是否被满足,如果某个sequence
中的连续两数(m, n)
满足next[m] = n
,那么我们就找到了一对满足的有向关系,此时简易的方法是置next[m] = 0
,反正一旦该关系被满足,之后也不会用这个值了。最后我们检查是否所有的next
都是0
,如果是,那么nums
中所有的有向关系在sequences
中均被满足,反正则不是。
class Solution {
public:
bool sequenceReconstruction(vector<int>& nums, vector<vector<int>>& sequences) {
int n = nums.size();
vector<int> next(n + 1);
for (int i = 0; i < n - 1; ++i) {
next[nums[i]] = nums[i + 1];
}
for (auto& sequence: sequences) {
int size = sequence.size();
for (int i = 0; i < size - 1; ++i) {
if (next[sequence[i]] == sequence[i + 1]) next[sequence[i]] = 0;
}
}
return accumulate(next.begin(), next.end(), 0) == 0;
}
};
LCR 116. 省份数量
Note: 本题并查集或者DFS均可,DFS其实就类似于岛屿系列
,并查集的话,可以使用维护连通分量个数以及按秩合并来降低时间。这两操作都在merge
函数中进行。
// 维护连通分量个数,在合并时-1
int connect = n;
void merge(int m, int n) {
int fm = find(m), fn = find(n);
// 在一个Union不需要合并
if (fm == fn) return;
// 秩小的合并到秩大的,初始秩全为1
if (rank[fm] <= rank[fn]) father[fm] = fn;
else father[fn] = fm;
// 秩相等
fm] == rank[fn]) ++rank[fn];
--connect;
};
LCR 117. 相似字符串组
Note: 这题用并查集比DFS/BFS好很多,因为题目并没有给出明显的图,需要自己去建,然后再搜索。
总结一下:一些明显依赖节点顺序(拓扑)的题无法用并查集解决,因为并查集是给无向图准备的,有向图无法使用并查集,比如LCR112 - LCR115
,因为并查集只能表示连通,无法表示方向,这里注意拓扑排序在BFS和DFS的不同实现,在BFS中,需要使用indegrees
数组来记录节点入度,然后逐步解拓扑,把入度为0
的节点放入队列,按顺序出队;在DFS中,需要使用三状态visited
数组,在进入节点时设置访问位为访问中
,DFS时遇到访问中
的节点说明称呼那,拓扑失败,遇到未访问
的节点则进入访问,访问完所有邻居节点后,当前节点入栈,由于底层节点先入栈,因此最后底层节点都在栈底,上层节点都在栈顶,翻转即可得到拓扑序(BFS不需要翻转);相反,LCR116 - LCR117
是适合并查集的,都是无向图,但是LCR116
由于题目已经给好了邻接矩阵,再去建并查集反而浪费时间;LCR117
没有给出图,需要自己建立,因此采用并查集更合适。不过其实最后还是怎么方便怎么来,对于这种岛屿数量问题
,给了图就直接搜,没给图就并查集。但并查集的最差复杂度是O(VlogE)
LCR 119. 最长连续序列
Note: 这题如果排序做很简单,但如果要求时间O(n)
,需要用哈希表来记录每个数字的出现,之后从中枚举所有连续序列的起点,假设某个数字n
可以作为起点,那么n - 1
必不可以出现在哈希表中,否则n
一定不是起点。枚举所有可能作为连续序列起点的数,然后开始计数,一直检查下一个数是否在哈希表中(是否出现),是则当前序列长度+1,直到不再连续,记录此时连续序列长度,并维护一个最大值。
LCR 120. 寻找文件副本
Note: 这题除了基本的哈希做法,由于题目有限制,文件编号都在0 ~ n - 1
之间,因此根据鸽巢原理,必定有两个相同文件在不同位置,如果我们把所有文件都放在与其编号相同的位置,那么一定有编号和位置对不上的,否则的话就没有重复文件了,换句话说,一定有多个相同文件映射到同一位置。因此考虑基于交换的方法,我们需要将每个文件都放在正确的位置,那么对于位置i
的文件,如果documents[i] != i
,那么这里的文件并不在正确的地方,我们记documents[i]
为temp
,那么我们将temp
归位,也就是把temp
放到位置temp
处,具体做法是,将i
处文件(也就是temp
)与temp
处文件交换,这样temp
就被归位,重复上述操作,直到文件i
被放到位置i
,也就是documents[i] == i
为止,但在交换之前,如果发现temp
处的文件已经归位,也就是documents[temp] == temp
,那么temp
文件必定是出现了两份。
这种方法其实本质和哈希表是一样的,只是把原来的数组当成了哈希表,使得数组下标和所在数字一致,这样可以实现类似哈希表的O(1)
查找。
class Solution {
public:
int findRepeatDocument(vector<int>& documents) {
int i = 0;
while (i < n) {
if (documents[i] == i) ++i;
else {
int& temp = documents[i];
if (documents[temp] == temp) return temp;
swap(documents[i], documents[temp]);
}
}
return -1;
}
};
LCR 124. 推理二叉树
Note: 注意两个加速方式:一是用一个哈希表缓存inorder
数字与索引的映射,便于在O(1)
时间内在inorder
中找到根节点下标(对应preorder
中的首位数字);二是用全局的prel
来代替原来传入递归函数的prel
和prer
,因为prer
实际没什么用,我们需要的是prel
(preorder
中当前首个下标),并且prel
在递归过程中是逐步+1的,因此设为全局变量,每次进入递归就自增1。
class Solution {
public:
unordered_map<int, int> inPos;
int preIdx = 0;
TreeNode* buildTree(vector<int>& pre, vector<int>& in, int inl, int inr) {
if (inl > inr) return nullptr;
int rootVal = pre[preIdx];
TreeNode* root = new TreeNode(rootVal);
int inRootIdx = inPos[rootVal];
++preIdx;
root->left = buildTree(pre, in, inl, inRootIdx - 1);
root->right = buildTree(pre, in, inRootIdx + 1, inr);
return root;
}
TreeNode* deduceTree(vector<int>& preorder, vector<int>& inorder) {
int n = inorder.size();
for (int i = 0; i < n; ++i) inPos[inorder[i]] = i;
return buildTree(preorder, inorder, 0, n - 1);
}
};
LCR 128. 库存管理 I
Note: 二分,但是旋转数组二分,因此需要判断nums[mid]
和边界的关系,在这里我们是要找右半边的最小值,因此需要和右边边界也就是nums[r]
进行大小关系比较,这里要明确一点,r
始终在右半部分!如果nums[mid] < nums[r]
,那么此时mid
一定在右半边,mid
右侧应该被忽略(但是mid
自己可能是右半边最小值!),故r = mid
;如果nums[mid] > nums[r]
,那么此时mid
一定在左半边,mid
以及其左侧应该被忽略,l = mid + 1
;如果nums[mid] == nums[r]
,此时mid
无法确定在左边还是右边,但无论在哪边,mid
都必定<r
,因此无论nums[r]
是不是最小值,r
位置的左边都至少有一个有和其相同的值,我们将r
减去1
,最终还是可以找到最小值的,无非就是找到的位置不一定在右半边的最左侧,故此情况下--r
。
class Solution {
public:
int stockManagement(vector<int>& stock) {
int n = stock.size();
int l = 0, r = n - 1;
while (l < r) {
int mid = l + (r - l) / 2;
if (stock[mid] > stock[r]) l = mid + 1;
else if (stock[mid] < stock[r]) r = mid;
// 在l<r的语义下,mid是一定<r的,因此如果stock[mid]和stock[r]相等,那么r自减即可
// 因为右端点可以忽略,不需要被计入
else --r;
}
return stock[l];
}
};
LCR 129. 字母迷宫
Note: 本题不能用memory
数组,否则由于需要同时记录x``y``cur
(目标字符串当前下标)三个维度的数据,那太浪费空间而且鸡肋!因此只使用visited
数组记录访问位,而且必须回溯,因为有一个额外的维度cur
,这和无法使用memory
的道理相同,x``y
在某个cur
下搜索失败,但是在另一个cur
下可能就访问成功,因此每次搜索完后必须回溯以免错过正确答案,切记!
LCR 130. 衣橱整理
Note: 本题广搜或者递推均可,递推方法是通过左侧和上方格子能否到达来判断本格子是否能够到达。注意在条件被违反(digit(i) + digit(j) > cnt
)时,是continue
而不是break
,例如19
到20
,后者在前者右边,但是数位和更小。
LCR 131. 砍竹子 I
Note: 同343. 整数拆分,使用朴素的动态规划(dp[i] = max(j * dp[i - j], j * (i - j)), j < i
)或者优化的动态规划(通过数学证明得出只需要考虑j = 2, 3
的情况,证明略,但是只记个结论足够)。
还一个方法是直接拆分成最多的3
,最后剩下如果是1
就和一个3
一起拆成2
和2
,如果剩下是2
直接乘,这是用算术-几何平均值不等式来证明的,证明如下:首先根据上述不等式得出,一个数只有在被拆分为若干个相等的数的时候,其乘积才会最大,假设每个拆分数都是k
,原数为p
,则拆分数量是p/k
,这些k
的最大乘积是k(p/k)
,取对数是(p/k)*logk
,对k
求导,导数为p*(1 - logk)/k2
,令导数等于0
得k = e
,在k < e
时,导数为正,在k > e
时,导数为负,因此原函数先增后减,在k = e
处取得最大值,因此最适合的拆分是拆成若干个e
,但是由于必须拆分为整数,我们只能在3
和2
之间选择,考虑6
,2*2*2
显然不如3*3
大,因此选择3
来进行拆分。这里要注意最后的余数可能为0
1
或2
,如果为1
,考虑最后一个拆分出的3
,明显应该拆分为2
个2
比较合适,因此最后要留一个4
来乘,计算幂时可采用快速幂,时间复杂度O(logn)
。
LCR 132. 砍竹子 II
Note: 在上一题的基础上增加了数据范围,并且要求取余,因此不能够用动态规划做,因为动态规划中使用了max
,取余操作在max
计算中无法传导,会导致错误结果(其本身不是一个四则运算符)。因此只能使用数学方法,也就是上一题中提到的拆分成若干个3
(用快速幂计算),剩2
的话就变成4
,但是在此过程中需要取余。快速幂部分代码如下:
long res = 1, x = 3;
while (times) {
if (times % 2) res = (res * x) % mod;
x = (x * x) % mod;
times /= 2;
}
其中times
初始化为幂指数,x
初始化为底数。主要思想是检查当前times
是否为奇数,如果是,那么乘一个x
,之后x
合并(x
变为自身平方,times
变为一半),比如9
个8
,被乘了1
个,剩下8
个8
合并为4
个8 * 8 = 64
,直到times
为0
,if (times % 2) res = (res * x) % mod
是在合并过程中拿出多余的x
来乘,这些x
是不能被合并的。使用long
的原因是因为两个1e9 + 7
级别的数相乘会超出int
范围,但不会超出long
范围。
LCR 133. 位 1 的个数
Note: a & (-a)
得到的是a
中最后一个1
的位置,因为-a
也就等于a
取反再加1
,因此a
与-a
除了最后一个1
的位置处,其他都是相反的,因为最后一个1
(位置记为i
)后面一定是一串0
,取反之后就是一串1
,加1
之后又会变为0
,并且进位到位置i
处,由于此时i
处是0
(取反了),因此最终-a
的i
处是1
,后面一串0
,a
的i
处是1
,后面乙醇0
,而两个数在i
之前的数位都是相反的,因此最终a & (-a)
的结果就是a
中最后一个a
的位置。
而a = a & (a - 1)
则是将a
的最后一个1
翻转(变为0
),同样假设这个1
在位置i
处,其后面跟一串0
,a
减去1
后,i
处变为0
,后面跟一串1
,前面部分与a
相同,因此a & (a - 1)
就导致a
在i
之前的部分被保留,而i
以及之后的部分全部变为0
。本题计算二进制1
的个数便可以使用该方法,让a
不断地与a - 1
按位与,直到a
变为0
,计算的次数也就是a
的二进制表示中0
的个数。
LCR 138. 有效数字
Note: 官解给的自动机,但是有点太麻烦。可以考虑设置几个标志来标记特殊符号,比如.
e/E
,还需要标志位记录是否有数字(比如单独的空字符串""
就是不合法的)。因此设置3
个标志位,首先用双指针去除字符串首尾空格,然后从左到右依次遍历:
class Solution {
public:
bool validNumber(string s) {
int n = s.size(), start = 0, end = n - 1;
// 3个标志位,分别表示 "是否出现小数点" "是否包含数字" "是否包含e"
bool isDecimal = false, hasNum = false, isScience = false;
// 双指针去掉首尾空格
while (start < n && s[start] == ' ') ++start;
while (end >= 0 && s[end] == ' ') --end;
int i = start;
while (i <= end) {
char& temp = s[i];
// 遇到数字则"是否包含数字"为真
if (temp >= '0' && temp <= '9') hasNum = true;
// 遇到小数点,只有在"未遇到小数点"以及"当前不包含e"的情况下才正确,因为e后面必须是整数
else if (temp == '.' && !isDecimal && !isScience) isDecimal = true;
// 遇到e,只有在"当前不包含e"以及"包含数字"的情况下才正确,因为e前面必须有数字
else if ((temp == 'e' || temp == 'E') && !isScience && hasNum) {
isScience = true;
// 遇到e,后面必须有数字,因此重新开始计算数字
hasNum = false;
// 遇到正负号,则只有在数字开头或者前一位是e时才正确
} else if ((temp == '+' || temp == '-') && (i == start || s[i - 1] == 'e' || s[i - 1] == 'E')) {}
// 其他情况均不合法
else return false;
++i;
}
// 最后检查是否有数字(如果无数字,可能是没有数字,或者e后面没有跟数字,此时不合法)
return hasNum;
}
};
LCR 139. 训练计划 I
Note: 左右指针,快慢指针均可,但快慢指针会多出不必要的交换,
class Solution {
public:
vector<int> trainingPlan(vector<int>& actions) {
// 左右双指针
int left = 0, right = actions.size() - 1;
while (left < right) {
while (left < right && (actions[left] & 1) == 1) ++left;
while (left < right && (actions[right] & 1) == 0) --right;
if (left < right) swap(actions[left], actions[right]);
}
// 快慢双指针
int slow = 0, fast = 0, n = actions.size();
while (fast < n) {
if (actions[fast] & 1) {
if (fast > slow) swap(actions[slow], actions[fast]);
++slow;
}
++fast;
}
return actions;
}
};
LCR 143. 子结构判断
Note: 本题和 572. 另一棵树的子树 不太一样,572题是判断树B是否是树A的子树,因此树B必须从根节点开始与A的某颗子树完全匹配,每一个节点都匹配,因此双层递归解法应写成:
class Solution {
public:
bool check (TreeNode* s, TreeNode* t) {
if (!s && !t) return true;
if ((!s && t) || (s && !t) || (s->val != t->val)) return false;
return check(s->left, t->left) && check(s->right, t->right);
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
// 暴力递归解
if (!root) return false;
return check(root, subRoot) || isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
}
};
这里第一层递归的目的是找到原树s
中与子树t
根节点匹配的根结点(类似字符串匹配中的找起始位置),由于该递归是把子树t
传下去了,并且本题中子树t
一定不为空,因此如果s
为空直接返回false
。否则按照先序检查以s
为根节点的树与t
是否完全匹配,进入第二层递归,该层递归是按照先序来检查两颗树中每个节点是否都相同,检查完当前根节点若不匹配,再去检查左子节点和右子节点,最后返回检查结果。
本题主要的不同点在于,子结构不代表两颗树中每一个节点都要匹配,但是按题目要求,空树一定不是某树的子结构,故如果t
是s
的子结构,那么前提条件是s
和t
都不为空(如果s
为空,t
不为空,t
显然也不是s
子结构)。因此同样两层递归,第一层先检查是不是s
和t
都不为空,不是直接返回false
,否则同样按照先序,先检查t
是不是以s
为根节点的树的子结构,然后再去检查s->left
和s->right
,最后返回结果。
对于检查子结构的第二层递归,如果t
为空,那么可以返回true
,说明t
已经比较完了,这与572. 另一棵树的子树
不同,因为子结构意味着每一次的比较中,t
,也就是待比较子树为空是合法的;如果t
不为空,s
为空或者s
和t
节点值不相等,直接返回false
,此时与572. 另一棵树的子树
是相同的。之后的检查左子节点和右子节点也是完全一样的。
/**
* 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:
bool isSame(TreeNode* s, TreeNode* t) {
if (!t) return true;
if (!s || s->val != t->val) return false;
return isSame(s->left, t->left) && isSame(s->right, t->right);
}
bool isSubStructure(TreeNode* A, TreeNode* B) {
if (!A || !B) return false;
return isSame(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
}
};
另外,572. 另一棵树的子树
还可以用KMP来做,因为判断子树本质上可以转化为判断子串,但是判断子结构并不能等价于判断子序列,比如树[10,12,6,8,3,11]
,其先序序列为10 12 8 3 6 11
,10 12 3
是其子序列,但是[10,12,3]
并不是其子结构,反过来则是一定成立的,子结构的先序序列一定是子序列。因此本题无法用KMP
来做。
LCR 146. 螺旋遍历二维数组
Note: 除了原本的边界收缩,还可以用方向转移来做(类似搜索),注意使用visited
数组来标记走过的格子,实际上是盲走,只是遇到边界换方向,不像方法一边界收缩那样有方向的走。
class Solution {
public:
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
bool visited[100][100]{};
vector<int> spiralArray(vector<vector<int>>& array) {
// 到头就换方向
if (array.size() == 0) return {};
int row = array.size(), col = array[0].size(), total = row * col;
int x = 0, y = 0, dir = 0;
vector<int> ans;
for (int i = 0; i < total; ++i) {
ans.emplace_back(array[x][y]);
visited[x][y] = true;
int nextx = x + dx[dir], nexty = y + dy[dir];
if (nextx < 0 || nextx >= row || nexty < 0 || nexty >= col || visited[nextx][nexty]) {
dir = (dir + 1) % 4;
nextx = x + dx[dir]; nexty = y + dy[dir];
}
x = nextx; y = nexty;
}
return ans;
}
};
LCR 148. 验证图书取出顺序
Note: 可以用模拟的方法,设置两个指针分别指向输入数组和输出数组,遍历输入数组不断入栈,入栈后检查栈顶元素是否等于输出数组(指针指向的)当前元素,是则出栈,同时输出数组指针+1。直到输入数组遍历完成,检查栈是否空,是则出栈序列合法,否则不合法。
注意: 这里的入栈序列是无序的,假设入栈序列有序(以升序为例),实际上可以提前结束流程,因为栈内元素一定是升序的,栈顶元素一定是≤当前出栈元素,否则就意味着要出栈的元素在栈顶元素之下,很明显这不是一个合法的出栈序列,直接返回false
。而如果栈顶元素<当前出栈元素,就需要入栈输入数组直到栈顶元素=当前出栈元素,然后弹出栈顶元素。
PS: 至于如何获取所有合法出栈序列,请看 出栈序列遍历以及正确性检验。