当前位置:  首页>> 技术小册>> 数据结构与算法(中)

难度: hard

内容描述

  1. 一只青蛙正在过河。这条河被分成x个单元,每个单元可能有一块石头,也可能没有。青蛙可以在石头上跳,但不能跳入水中。
  2. 给出一个按升序排列的石头位置列表(单位),确定青蛙是否能够在最后一块石头上着陆过河。最初,青蛙在第一块石头上,并假设第一次跳跃必须是1个单位。
  3. 如果青蛙的最后一次跳跃是k个单位,那么它的下一次跳跃必须是k-1kk+1个单位。注意青蛙只能向前跳。
  4. 注:
  5. 石头的数量是≥ 2且小于1100
  6. 每个石头的位置将是一个小于231的非负整数。
  7. 第一块石头的位置总是0
  8. 1
  9. [0,1,3,5,6,8,12,17]
  10. 一共有8块石头。
  11. 0单元的第一块石头,第1单元的第二块石头,
  12. 第三单元的第三块石头,等等。。。
  13. 17单元的最后一块石头。
  14. 返回true。青蛙可以跳到最后一块石头
  15. 1个单位到第二块石头,然后2个单位到第三块石头,然后
  16. 2个单位到第四块石头,然后3个单位到第六块石头,
  17. 第七石有4个单位,第八石有5个单位。
  18. 2
  19. [0,1,2,3,4,8,9,11]
  20. 返回false。没有办法跳到最后一块石头
  21. 第五石和第六石之间的差距太大。

解题方案

思路 1
**- 时间复杂度: O(N)**- 空间复杂度: O(N)**

  • 关注点放在数据范围。

  • 判断是否能够到达y点(因为问题就是到达最后一个点),需要两个条件:

    • 能够到达x点(x<y)
    • x点能够跳到y点
  • 由于条件2需要前面一个点的跳动情况,所以这个题的子问题是

    flag[x][y]=true表示当青蛙能够跳到x,并且能够跳到y点

  • 状态转移是

    假设flag[x][y]=true,枚举所有的z>y,如果|(z-y) - (y-x)|<=1,那么flag[y][z]=true

  • 这里有个需要注意的优化点,可以固定y,枚举xy,这样对于每个y,只需要扫一遍点数组就可以成功执行转移

  • 复杂度是o(n^2)

代码:

  1. class Solution {
  2. public boolean canCross(int[] stones) {
  3. int n = stones.length;
  4. if (stones[1] != 1) {
  5. return false;
  6. }
  7. boolean[][] flag = new boolean[n][n];
  8. for (int i = 0;i < n;i++) {
  9. for (int j = 0;j < n;j++) {
  10. flag[i][j] = false;
  11. }
  12. }
  13. flag[1][0] = true;
  14. for (int i = 1;i < n;i++) {
  15. int left = i - 1;
  16. int right = i + 1;
  17. while (left >= 0 && right < n) {
  18. while (left >= 0 && !flag[i][left]) left--;
  19. if (left >= 0) {
  20. while (right < n && stones[right] - stones[i] <= stones[i] - stones[left] + 1) {
  21. if (stones[right] - stones[i] == stones[i] - stones[left] - 1
  22. || stones[right] - stones[i] == stones[i] - stones[left]
  23. || stones[right] - stones[i] == stones[i] - stones[left] + 1) {
  24. flag[right][i] = true;
  25. }
  26. right++;
  27. }
  28. left--;
  29. }
  30. }
  31. }
  32. for (int i = 0;i < n;i++) {
  33. if (flag[n - 1][i]) {
  34. return true;
  35. }
  36. }
  37. return false;
  38. }
  39. }

该分类下的相关小册推荐: