青蛙过河问题

发表于 阅读次数：

LeetCode:403. Frog Jump

版本一

深度优先搜索：
从头至尾遍历石头，从每个石头上分别以k-1,k,k+1的力量向前跳一下，如果这三个力量范围内没有石头，则返回；否则继续先前跳一下……直至到达最后一个石头。

没有记忆功能，每次遍历需全盘重新计算，时间复杂度O(3^n),石头多了会超时。于是加入记忆搜索，有了版本二。

版本二

迭代+记忆搜索：
加入记忆搜索，为每块石头建立一个力量表，每到达一块石头，就把这一跳所用的力度记录在这块石头的力量表中。这样一来，一块石头是否可以到达，取决于这块石头的力量表是否为空。

  • 题目要求第一跳力度为k=1，则在石头1上记录力量k=1，然后从第二块石头开始遍历：
  • 对于第i个被遍历的石头，判断从石头1到石头(i-1)范围内的每一个石头上，是否存在跳到石头i上的力量，如果存在(代表能跳到石头i上)，则在石头i的力量表中添加这个力量值。
  • 所有石头遍历完，判断最后一块石头的力量表是否为空，则得出是否能到达最后。
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
public class Solution {
	HashMap<Integer, Boolean> mapTable = new HashMap<Integer, Boolean>();
	int[] stones;

	public boolean canCross(int[] stones) {

		int len = stones.length;
		if (len < 2)
			return true;
		if (stones[1] != 1)
			return false;
		if (len == 2)
			return true;

		this.stones = stones;

		mapTable.put(0 | 1 << 11, true);
		mapTable.put(1 | 1 << 11, true);

		return solve(len);
	}

	private boolean solve(int endPos) {
		// 枚举前面所有点，看是否能到这里，如果能，记录跨度k
		for (int nowPos = 2; nowPos < endPos; nowPos++)
			for (int j = 1; j < nowPos; j++) {
				int k = canArriveByK(j, nowPos);
				if (k != 0) {
					// 在当前位置，记录当前跨度k
					if (nowPos == endPos - 1)
						return true;
					mapTable.put(nowPos | k << 11, true);
				}
			}
		return false;
	}

	private int canArriveByK(int j, int nowPos) {
		int begin = stones[j];
		int end = stones[nowPos];
		int k = end - begin;

		if (mapTable.get(j | k << 11) != null)
			return k;
		if (mapTable.get(j | (k + 1) << 11) != null)
			return k;
		if (mapTable.get(j | (k - 1) << 11) != null)
			return k;
		return 0;
	}

}

虽然所有测试用例都可以在时间限制内运行完毕,但时间复杂度O(n^2)，运行时间351ms，只击败了7.82%的用户……这不能忍。

版本三

深度优先+记忆搜索：
将版本一和二结合，将深度优先搜索的结果及时记录在每块石头的力量表中。

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
public class Solution {
	int[] stones;
	HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	HashMap<Integer, Boolean> mapKey = new HashMap<Integer, Boolean>();

	public boolean canCross(int[] stones) {

		int len = stones.length;
		this.stones = stones;

		for (int i = 0; i < len; i++)
			map.put(stones[i], i);

		mapKey.put(0, true);

		return solve(1, stones[len - 1], 1);
	}

	private boolean solve(int pos, int endPos, int k) {

		if (k == 0)
			return false;

		int keyChar = pos << 11 | k ;

		if (pos == endPos)
			return true;

		if (mapKey.get(keyChar) != null)
			return false;

		if ((pos > endPos) || (map.get(pos) == null)) {
			mapKey.put(keyChar, false);
			return false;
		}

		if (solve(pos + k - 1, endPos, k - 1))
			return true;
		if (solve(pos + k, endPos, k))
			return true;
		if (solve(pos + k + 1, endPos, k + 1))
			return true;

		mapKey.put(keyChar, false);
		return false;

	}

}

时间复杂度小于O(n^2)，运行时间50ms左右。

番外篇

上述版本二与版本三中，都有类似代码：

1
int keyChar = pos << 11 | k ;

这行代码的作用是，将当前石头位置(pos)和当前跳跃力量(k)写进同一个int值，这个int将在后面作为哈希表的键值，建立以二维数组为键值的哈希表。这受启发于博客：安定区：动态规划 DP leetcode403 青蛙过河问题。

为什么是左移11位？

这取决于最远那一颗石头的距离，也就是数组最后一个数字可能的最大值。原题目中说道：

Note:
The number of stones is ≥ 2 and is < 1,100.
Each stone’s position will be a non-negative integer < 2^31.
The first stone’s position is always 0.

石头总数小于1100，根据每次跳跃最多只能比上一次多跳1，可以得知最远的跳跃方案：

0,1,3,6,10,15,…

通项公式为：

f(n)=n*(n+1)/2

最后一块石头最远为1099*1100/2=604450，可以用20位二进制数表示—2^20=1048576。

而石头总数1100可以用11位二进制数表示—-2^11=2,048。

20+11=31位，刚好可以由一个int（32位）容纳。所以，左移11位，将后11位存储力量信息，将前21位存储位置信息。
这样的键值可以无损地模拟数组，并建立哈希表。相比于直接用数组作为键值的哈希表，读写速度得到提升，空间复杂度更小。这都依赖于石头总数小于1100，与其说是巧合，不如说是出题人给出的提示:)