406. 根据身高重建队列

image.png

  1. class Solution {
  2.     //[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]
  3.     //[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]//先按身高从高往低排序，再按第二个元素从第往高排
  4.     //[7,0]
  5.     //[7,0],[7,1]
  6.     //[7,0],[6,1],[7,1]
  7.     //[5,0],[7,0],[6,1],[7,1]
  8.     //[5,0],[5,2],[7,0],[6,1],[7,1]
  9.     //[5,0],[5,2],[7,0],[6,1],[4,4],[7,1]
  10.     public int[][] reconstructQueue(int[][] people) {
  11.         if (people == null || people.length == 0 || people[0].length != 2) return new int[0][0];
  12.         Arrays.sort(people,(p1, p2) -> {
  13.             if (p1[0] != p2[0]) {
  14.                 return p2[0] - p1[0];
  15.             } else {
  16.                 return p1[1] - p2[1];
  17.             }
  18.         });
  19.         List<int[]> res = new ArrayList();
  20.         for (int[] p : people) {
  21.             res.add(p[1], p);
  22.         }
  23.         return res.toArray(new int[res.size()][]);
  24.     }
  25. }

55. 跳跃游戏

image.png

  • 动态规划

    1. class Solution {
    2.   public boolean canJump(int[] nums) {
    3.       if (nums == null || nums.length == 0) return false;
    4.       boolean[] dp = new boolean[nums.length];
    5.       //dp[i]=dp[j]&&nums[j]>=i-j
    6.       dp[0] = true;
    7.       for (int i = 1; i < nums.length; i++) {
    8.           for (int j = i - 1; j >= 0; j--) {
    9.               dp[i] |= dp[j] && nums[j] >= (i - j);
    10.               if (dp[i]) break;
    11.           }
    12.       }
    13.       return dp[nums.length - 1];
    14.   }
    15. }

  • 贪心法

    1. class Solution {
    2.   public boolean canJump(int[] nums) {
    3.       if (nums == null || nums.length < 2) return true;
    4.       int maxRemote = 0;
    5.       for (int i = 0; i < nums.length - 1; i++) {
    6.           if (i <= maxRemote) {
    7.               maxRemote = Math.max(maxRemote, i + nums[i]);
    8.           }
    9.           if (maxRemote >= nums.length - 1) return true;
    10.       }
    11.       return false;
    12.   }
    13. }