题目描述
一只青蛙想要过河。假定河流被等分为 x
个单元格,并且在每一个单元格内都有可能放有一石子(也有可能没有)。 青蛙可以跳上石头,但是不可以跳入水中。
给定石子的位置列表(用单元格序号升序表示),请判定青蛙能否成功过河(即能否在最后一步跳至最后一个石子上)。开始时,青蛙默认已站在第一个石子上,并可以假定它第一步只能跳跃一个单位(即只能从单元格 1 跳至单元格 2)。
如果青蛙上一步跳跃了 k
个单位,那么它接下来的跳跃距离只能选择为 k - 1
、k
或 k + 1
个单位。另请注意,青蛙只能向前方(终点的方向)跳跃。
请注意:
- 石子的数量 $\ge 2$ 且 $< 1100$;
- 每一个石子的位置序号都是一个非负整数,且其 $< 2^{31}$;
- 第一个石子的位置永远是
0
。
样例
[0,1,3,5,6,8,12,17]
总共有 8 个石子。
第一个石子处于序号为 0 的单元格的位置, 第二个石子处于序号为 1 的单元格的位置,
第三个石子在序号为 3 的单元格的位置,以此定义整个数组...
最后一个石子处于序号为 17 的单元格的位置。
返回 true。即青蛙可以成功过河,按照如下方案跳跃:
跳 1 个单位到第2块石子, 然后跳 2 个单位到第 3 块石子, 接着
跳 2 个单位到第4块石子, 然后跳 3 个单位到第 6 块石子,
跳 4 个单位到第7块石子, 最后,跳 5 个单位到第 8 个石子(即最后一块石子)。
[0,1,2,3,4,8,9,11]
返回 false。青蛙没有办法过河。
这是因为第 5 和第 6 个石子之间的间距太大,没有可选的方案供青蛙跳跃过去。
算法
(宽度优先搜索) $O(n^2)$
- 我们可以利用宽度优先搜索判定是否能到达终点。
- 设状态 $(p, k)$ 表示在单元格 $p$ 时,上一步跳跃了 $k$ 个单位。
- 每次我们可以从 $(p, k)$ 跳到 $(h[stones[p] + k - 1], k - 1)$、$(h[stones[p] + k], k)$,或 $(h[stones[p] + k + 1], k + 1)$ 的状态(要求 $k + i$ 不能小于等于 0,且哈希表中存在跳过去的状态)。$h$ 为位置到单元格的映射。
- 初始时,$(0, 0)$ 状态入队。
时间复杂度
- 最多有 $O(n^2)$ 个状态,每次只有 3 种转移,故时间复杂度为 $O(n^2)$。
空间复杂度
- 哈希表需要 $O(n)$ 的空间,队列和访问记录表需要 $O(n^2)$ 的空间,故空间复杂度为 $O(n^2)$。
C++ 代码
class Solution {
public:
bool canCross(vector<int>& stones) {
int n = stones.size();
unordered_map<int, int> h;
for (int i = 0; i < n; i++)
h[stones[i]] = i;
vector<vector<bool>> vis(n, vector<bool>(n, false));
queue<pair<int, int>> q;
vis[0][0] = true;
q.push(make_pair(0, 0));
while (!q.empty()) {
auto sta = q.front();
q.pop();
int cur_x = sta.first, cur_k = sta.second;
if (cur_x == n - 1)
return true;
for (int i = -1; i <= 1; i++) {
if (cur_k + i <= 0)
continue;
int next_k = cur_k + i;
int next_p = stones[cur_x] + next_k;
if (h.find(next_p) != h.end()) {
int next_x = h[next_p];
if (!vis[next_x][next_k]) {
vis[next_x][next_k] = true;
q.push(make_pair(next_x, next_k));
}
}
}
}
return false;
}
};
有个疑问,如果青蛙跳跃步数依次是1, 2, 3, …, 1000,总共跳跃了1000次,最终的位置500500。vis数组会不会越界啊?
不会的,位置都经过 hash 了
这里的next_k是指的步数,还是hash过后的位置呢?
next_k
是上一次跳跃的步数多谢解答,是我自己看错了😫
如果不能使用库函数map,怎样能快速知道下个落脚点有没有石头?
map 不是库函数,是 STL 模板类,用来做 hash 的。如果不能用,那就手写 hash 咯
好像可以离散化,但没必要。。。