LeeCode三百题-贪心算法

发表于 2021-04-29 更新于 2026-06-20 分类于 LeeCode三百题

[TOC]

代码工程获取

git clone --depth=1 https://gitee.com/SevDaisy/LeeCode300.git

#55 跳跃游戏

算法思想：贪心/BFS
关键：Integer 可以作为 HashMap 的 Key 么？
- 在工程实践中，不建议这样做
- 但是在刷题的时候，单纯从语法角度上讲，是可以的
查看源码，可以发现
- Integer 作为包装类
  - 内有一个属性是 private final int value
  - Interger所对应的那个int值
- Integer 的 equals 方法，判等的条件是 value == ((Integer)obj).intValue();
- Integer 的 hashCode 方法，是 return value;
所以，Integer 在作为 Key 的时候，是可以满足，该相等相等、该不等不等 的基本要求的。
关键：Set在初次add时会返回true，而在重复add时会返回false
因此，我们直接用visited.add(i)代替
- 先 if-else visited.contains(i) 再 visited.add(i)
关于超时：
一开始，用Stack来决定下一个去哪个位置，但是会超时
后来，优化 Stack 为 优先队列 PriorityQueue
- 每次都贪心地先去索引最大的最远的节点
- 也还是会超出时间限制

仔细想想，我用Stack的时候

本来也就是最后才push最大的节点
和用优先队列效果差不了很多。

/* 用 Stack */
class Solution {

  public boolean canJump(int[] nums) {
    if (nums == null || nums.length < 1) return false;
    int iMax = nums.length;
    int rightMax = 0;
    Stack<Integer> stack = new Stack<Integer>();
    Set<Integer> visited = new HashSet<>(iMax);
    stack.push(0);
    while (!stack.isEmpty()) {
      int cur = stack.pop().intValue();
      int step = nums[cur];
      for (int i = cur - step; i <= cur + step; i++) {
        if (i > 0 && i < iMax && visited.add(i)) {
          stack.push(i);
          rightMax = Math.max(rightMax, i);
        }
      }
    }
    return rightMax + 1 == iMax;
  }
}

/* 用 PriorityQueue */
class Solution {

  public boolean canJump(int[] nums) {
    if (nums == null || nums.length < 1) return false;
    int iMax = nums.length;
    int rightMax = 0;
    Queue<Integer> queue = new PriorityQueue<>(iMax);
    Set<Integer> visited = new HashSet<>(iMax);
    queue.add(0);
    while (!queue.isEmpty()) {
      int cur = queue.poll();
      int step = nums[cur];
      for (int i = cur - step; i <= cur + step; i++) {
        if (i > 0 && i < iMax && visited.add(i)) {
          queue.add(i);
          rightMax = Math.max(rightMax, i);
        }
      }
    }
    return rightMax + 1 == iMax;
  }
}

优化：仔细想想：
- 我们需要做全遍历么？或者说，
- 我们有回头走的必要么？—— 没有
因此，我们不需要 Stack 或者 PriorityQueue，也不需要 visited
我们只需要一直往前走就好了。
记录当前可达的最右索引为rightMax，然后对于 i in [0,iMax) 更新 rightMax
如果 rightMax+1 ≥ iMax，则 return true

否则，return false

for (int i = 0; i < iMax; i++) {
  /* 在能走的范围里 */
  if (i <= rightMax) {
    /* 更新最远可达的位置 */
    rightMax = Math.max(rightMax, i + nums[i]);
    /* 如果最远已经达到或者超过终点了，返回成功 */
    if (rightMax + 1 >= iMax) return true;
  } else {
    /* 否则，失败了就结束吧 */
    break;
  }
}

最终代码 2ms => 83.72%

package Order300;

public class T55_jump_game {

  public static void main(String[] args) {
    System.out.println(new Solution().canJump(new int[] { 2, 3, 1, 1, 4 }));
    System.out.println(new Solution().canJump(new int[] { 3, 2, 1, 0, 4 }));
  }

  static class Solution {

    public boolean canJump(int[] nums) {
      if (nums == null || nums.length < 1) return false;
      int iMax = nums.length;
      int rightMax = 0;

      for (int i = 0; i < iMax && i <= rightMax; i++) {
        /* 更新最远可达的位置 */
        rightMax = Math.max(rightMax, i + nums[i]);
        /* 如果最远已经达到或者超过终点了，返回成功 */
        if (rightMax + 1 >= iMax) return true;
      }

      return false;
    }
  }
}

#45 跳跃游戏 II

在跳跃游戏T55 的基础上，补充计步器即可

// T55 核心代码
int iMax = nums.length;
int rightMax = 0;
for (int i = 0; i < iMax && i <= rightMax; i++) {
  /* 更新最远可达的位置 */
  rightMax = Math.max(rightMax, i + nums[i]);
  /* 如果最远已经达到或者超过终点了，返回成功 */
  if (rightMax + 1 >= iMax) return true;
}

计步器，显然应该从0开始
关键：计步器应该在什么时候++？
- 答：在当前i已经是上一个rightMax的时候
此时，再继续往前走，就意味着使用某个格子来更新了当前正在使用的rightMax
使用了的是哪个格子，并不重要
巧妙的就是，只要我们不得不更新当前正在使用的rightMax，就意味着走出了一步
关键：i 是遍历 [0,iMax-1) 而不是 [0,iMax)
因为，如果在 i == iMax-1 的时候，i 已经在终点了
- 正巧那时，curRightMax 也是 iMax-1，然后就会计步器再++
- 那就走到终点后面去了。那就了多走了一步了。
题目保证了一定会到达终点，所以只要能走到 iMax-2，即 i==iMax-2 时
- 如果正好 curRightMax == iMax-2 那么就 stepCnt++ 下一步就是终点没问题
- 否则 curRightMax > iMax-2，即 curRightMax ≥ iMax-1 所以这一步就足够到达终点

package Order300;

public class T45_jump_game_ii {

  static class Solution {

    public int jump(int[] nums) {
      if (nums == null || nums.length < 1) {
        return 0;
      }
      int iMax = nums.length;
      int rightMax = 0;/* 最远可达的右边 */
      int curRightMax = 0;/* 当前这一步内 最远的可达的右边 */
      int stepCnt = 0;/* 计步器 */

      /**
       * 注意，是遍历 [0,iMax-1) 而不是 [0,iMax)
       * 因为，如果 在 i = iMax-1 的时候，i 已经在终点了
       * 正巧，curRightMax 也是 iMax-1，然后就会 计步器再++
       * 那就走到终点后面去了。那就了多走了一步了。
       * 
       * 题目保证了一定会到达终点，所以只要能走到 iMax-2
       * 如果 正好 curRightMax == iMax-2 那么就 stepCnt++ 下一步就是终点没问题
       * 否则 curRightMax > iMax-2，即 curRightMax ≥ iMax-1 所以这一步就足够到达终点
       */
      for (int i = 0; i < iMax - 1; i++) {
        /* 遍历中，每次都要更新 最远可达的右边 */
        rightMax = Math.max(rightMax, i + nums[i]);
        /* 当 i 已经是 这一步的最远右边 */
        if (i == curRightMax) {
          /* 更新 这一步最远右边 改为 全局的最远可达右边 */
          curRightMax = rightMax;
          /* 说明走了一步，计步器++ */
          stepCnt++;
        }
      }

      return stepCnt;
    }
  }
}

#1306 跳跃游戏 III

优化路径：
递归+HashSet —— 9ms => 31.71%
C++实现 —— 52ms
迭代+HashSet+Stack —— 17ms
迭代+HashSet+LinkedList —— 14~16ms
递归+boolean[] —— 4ms —— 用 boolean[] 代替 HashSet 也勉强算是 状态压缩 了
递归+boolean[]+转移递归出口到递归入口 —— 3ms => 96.72% —— 仅仅减去了一部分叶子节点的剪枝

package Order300;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

public class T1306_jump_game_iii {

  public static void main(String[] args) {
    int[] nums;
    int start;

    nums = new int[] { 4, 2, 3, 0, 3, 1, 2 };
    start = 5;
    System.out.println(new Solution().canReach(nums, start)); // -> true

    nums = new int[] { 4, 2, 3, 0, 3, 1, 2 };
    start = 0;
    System.out.println(new Solution().canReach(nums, start)); // -> true

    nums = new int[] { 3, 0, 2, 1, 2 };
    start = 2;
    System.out.println(new Solution().canReach(nums, start)); // -> false
  }

  /** 递归实现 9ms => 31.71% */
  static class Solution_递归 {

    private boolean step(int[] nums, int cur, Set<Integer> walked) {
      if (cur < 0 || cur >= nums.length) {
        return false;
      }
      if (nums[cur] == 0) {
        return true;
      }
      /* 如果不是第一次加入 walked，则直接退出 */
      if (!walked.add(cur)) {
        return false;
      }
      return (
        step(nums, cur - nums[cur], walked) ||
        step(nums, cur + nums[cur], walked)
      );
    }

    public boolean canReach(int[] arr, int start) {
      if (arr == null || arr.length < 1) {
        return false;
      }
      return step(arr, start, new HashSet<Integer>(arr.length));
    }
  }

  /** 迭代实现 14～16ms */
  static class Solution_迭代 {

    public boolean canReach(int[] arr, int start) {
      if (arr == null || arr.length < 1) {
        return false;
      }
      int iMax = arr.length;
      Set<Integer> visited = new HashSet<Integer>(iMax);
      LinkedList<Integer> stack = new LinkedList<Integer>();
      stack.add(start);
      while (!stack.isEmpty()) {
        int cur = stack.removeLast();
        if (arr[cur] == 0) return true;
        if (visited.add(cur)) {
          if (cur - arr[cur] >= 0) stack.add(cur - arr[cur]);
          if (cur + arr[cur] < iMax) stack.add(cur + arr[cur]);
        }
      }
      return false;
    }
  }

  /* 最终优化版的递归 3ms => 96.72% */
  static class Solution {

    public boolean canReach(int[] arr, int start) {
      boolean[] visited = new boolean[arr.length];
      return step(arr, start, visited);
    }

    private boolean step(int[] arr, int cur, boolean[] visited) {
      if (visited[cur]) return false;
      if (arr[cur] == 0) return true;
      visited[cur] = true;

      return (
        ((cur - arr[cur] >= 0) ? step(arr, cur - arr[cur], visited) : false) ||
        (
          (cur + arr[cur] < arr.length)
            ? step(arr, cur + arr[cur], visited)
            : false
        )
      );
    }
  }
}

#1345 跳跃游戏 IV

point: queue的入队操作，用 offer 感觉更帅 —— 而且真的会少一层函数调用哦

在源码优先队列PriorityQueue：

public boolean add(E e) {
  return offer(e);
}
public boolean offer(E e) {
  if (e == null)
    throw new NullPointerException();
  modCount++;
  int i = size;
  if (i >= queue.length)
    grow(i + 1);
  siftUp(i, e);
  size = i + 1;
  return true;
}

绝妙关键：BFS visited数组元素是boolean 如何维护 stepCnt？
- 使用 levelSize 记录每次的当前这个层次总共有多少节点
- levelSize 用完以后，先维护 stepCnt：stepCnt++
- 再更新：levelSize = queue.size()
int stepCnt = 0;
int levelSize;
queue.add(0);
while (!queue.isEmpty()) {
levelSize = queue.size();
stepCnt++;
while (levelSize-- > 0) {
/* Normally BFS Work Here */
}
}
AStar 搜索不适用于本题
剪枝优化合并连续相同项为两项 48ms => 94.36%
- 因为至少要跳一步，所以是合并为两项而不是一项
写了乱七八糟一堆优化，都没用。就一个剪枝优化有用。感觉浪费了我的6、7个小时。难受啊。

package Order300;

import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class T1345_jump_game_iv {

  public static void main(String[] args) {
    int[] nums;
    nums = new int[] { 100, -23, -23, 404, 100, 23, 23, 23, 3, 404 };
    System.out.println(
      "\nanswer is 3 but " + new Solution().minJumps(nums) + "\n"
    ); // -> 3

    nums = new int[] { 7 };
    System.out.println(
      "\nanswer is 0 but " + new Solution().minJumps(nums) + "\n"
    ); // -> 0

    nums = new int[] { 7, 6, 9, 6, 9, 6, 9, 7 };
    System.out.println(
      "\nanswer is 1 but " + new Solution().minJumps(nums) + "\n"
    ); // -> 1

    nums = new int[] { 6, 1, 9 };
    System.out.println(
      "\nanswer is 2 but " + new Solution().minJumps(nums) + "\n"
    ); // -> 2

    nums = new int[] { 11, 22, 7, 7, 7, 7, 7, 7, 7, 22, 13 };
    System.out.println(
      "\nanswer is 3 but " + new Solution().minJumps(nums) + "\n"
    ); // -> 3

    nums = new int[] { 7, 7, 2, 1, 7, 7, 7, 3, 4, 1 };
    System.out.println(
      "\nanswer is 3 but " + new Solution().minJumps(nums) + "\n"
    ); // -> 3

    nums = BaseNode.BigCaseVal.nums_T1345; // nums_T1345.length = 3549
    System.out.println(
      "\nanswer is 30 but " + new Solution().minJumps(nums) + "\n"
    ); // -> 30
  }

  /** 普通 BFS 85～90ms */
  static class Solution {

    static final Comparator<Integer> descendComparator = new Comparator<Integer>() {
      public int compare(Integer o1, Integer o2) {
        return o2 - o1;
      }
    };

    public int minJumps(int[] arr) {
      if (arr == null || arr.length < 1) {
        return 0;
      }

      int iMax = arr.length;
      /* 剪枝 合并数组中连续的相同项为相同的两项 48ms => 94.36% */
      LinkedList<Integer> list = new LinkedList<>();
      int last = arr[0];
      int count = 0;
      list.add(last);
      for (int x : arr) {
        if (x == last) {
          if (++count == 2) {
            list.add(last);
          }
        } else {
          count = 0;
          last = x;
          list.add(last);
        }
      }
      iMax = list.size();
      arr = new int[iMax];
      int xi = 0;
      for (int x : list) arr[xi++] = x;

      Queue<Integer> queue = new LinkedList<>();
      /* 对 索引 的 访问记录 */
      boolean[] visited = new boolean[iMax];/* boolean 默认初始值为 false */
      /* 对 跳转值 的 访问记录 */
      HashSet<Integer> valSet = new HashSet<>();
      /* 记录可跳转的组 */
      HashMap<Integer, Queue<Integer>> valGroup = new HashMap<Integer, Queue<Integer>>();

      for (int i = 0; i < iMax; i++) {
        int cur = arr[i];
        if (valGroup.containsKey(cur)) {
          /**
           * 其实这个 group 最好是降序排序的
           * // 可能的优化方向: 用 降序 排序的 PriorityQueue 代替 ArrayList
           * 当前 group 已经是 PriorityQueue
           */
          valGroup.get(cur).offer(i);
        } else {
          /**
           * // 实际上，对于每个 group，第一次遇到的索引 i 并不需要保存
           * 上面这个想法是错的。详见 line: [114 ~ 121]
           */
          Queue<Integer> group = new PriorityQueue<Integer>(descendComparator);
          group.offer(i);
          valGroup.put(cur, group);
        }
      }

      int cur, curVal;
      int target = iMax - 1;
      int next;
      int stepCnt = 0;
      int levelSize;
      Queue<Integer> nextJumps;
      queue.offer(0);
      while (!queue.isEmpty()) {
        levelSize = queue.size();
        while (levelSize-- > 0) {
          /* 取 索引 */
          cur = queue.poll().intValue();
          /* 取 索引对应值 */
          curVal = arr[cur];
          /* 判断终点 */
          if (cur == target) {
            return stepCnt;
          }
          /* 索引 标记访问 */
          visited[cur] = true;
          /* 试着跳跃 */
          if (valSet.add(curVal) && valGroup.containsKey(curVal)) {
            nextJumps = valGroup.get(curVal);
            for (int x : nextJumps) {
              /**
               * // 不需要 if (!visited[x]) 因为跳跃肯定是往右跳
               * 上面这个想法是错误的！考虑 A1 ... B1 ... B2 A2
               * 可能会因为 A 就 A1 -> A2
               * 然后 A2 向左走是 B2
               * 结果现在 B2 跳不到 B1 了！—— 因为 group 中只存了 B2
               * 甚至会 B2 跳到 B2 ！—— 因为我这边取消了 if (!visited[x])
               **/
              if (!visited[x]) {
                queue.offer(x);
              }
            }
          }
          /* 试着右走 */
          next = cur + 1;
          if (next < iMax && !visited[next]) {
            queue.offer(next);
          }
          /* 试着左走 */
          next = cur - 1;
          if (next >= 0 && !visited[next]) {
            queue.offer(next);
          }
        }
        stepCnt++;
      }

      return -1;
    }
  }

  /** 退化为 BFS 的 AStar 100ms+ */
  static class Solution_Astar_BFS {

    static class state implements Comparable<state> {

      int index;
      int stepCnt;
      int cost;

      public state(int index, int stepCnt, int target) {
        this.index = index;
        this.stepCnt = stepCnt;
        // this.cost = target - index + stepCnt*1024;
        this.cost = stepCnt;
      }

      public int compareTo(state o) {
        return this.cost - o.cost;
      }
    }

    static final Comparator<Integer> descendComparator = new Comparator<Integer>() {
      public int compare(Integer o1, Integer o2) {
        return o2 - o1;
      }
    };

    public int minJumps(int[] arr) {
      if (arr == null || arr.length < 1) {
        return 0;
      }
      int iMax = arr.length;
      Queue<state> queue = new PriorityQueue<state>();
      boolean[] visited = new boolean[iMax];
      HashSet<Integer> valSet = new HashSet<>(1024);
      HashMap<Integer, Queue<Integer>> valGroup = new HashMap<Integer, Queue<Integer>>(
        1024
      );

      for (int i = 0; i < iMax; i++) {
        int cur = arr[i];
        if (valGroup.containsKey(cur)) {
          valGroup.get(cur).offer(i);
        } else {
          Queue<Integer> group = new PriorityQueue<Integer>(descendComparator);
          group.offer(i);
          valGroup.put(cur, group);
        }
      }
      state cur;
      int target = iMax - 1;
      int next;
      int curStep, curIndex, curVal;
      Queue<Integer> nextJumps;
      queue.offer(new state(0, 0, target));
      visited[0] = true;
      while (!queue.isEmpty()) {
        cur = queue.poll();
        curIndex = cur.index;
        curVal = arr[curIndex];
        curStep = cur.stepCnt;
        if (curIndex == target) {
          return curStep;
        }
        if (valSet.add(curVal) && valGroup.containsKey(curVal)) {
          nextJumps = valGroup.get(curVal);
          for (Integer x : nextJumps) {
            if (!visited[x]) {
              visited[x] = true;
              queue.offer(new state(x, curStep + 1, target));
            }
          }
        }
        next = curIndex + 1;
        if (next < iMax && !visited[next]) {
          visited[curIndex] = true;
          queue.offer(new state(next, curStep + 1, target));
        }
        next = curIndex - 1;
        if (next >= 0 && !visited[next]) {
          visited[curIndex] = true;
          queue.offer(new state(next, curStep + 1, target));
        }
      }
      return -1;
    }
  }
}

LeeCode三百题-贪心算法

#55 跳跃游戏

#45 跳跃游戏 II

#1306 跳跃游戏 III

#1345 跳跃游戏 IV

#1340 跳跃游戏 V

#1696 跳跃游戏 VI