55 这题感觉自己犯蠢了 看了下评论恍然大悟、、
public boolean canJump(int[] nums) { int len = nums.length; if (len <= 1) return true; int maxDis = nums[0]; for (int i = 1; i < len - 1; i++) { if (i <= maxDis) { maxDis = Math.max(maxDis, nums[i]+i); } } return maxDis >= len - 1; }
134 用堆从最大差开始遍历，性能比较差
public static int canCompleteCircuit(int[] gas, int[] cost) { PriorityQueue<Integer> pq = new PriorityQueue<>((k1,k2)->(gas[k2]-cost[k2])-(gas[k1]-cost[k1])); for (int i = 0; i < gas.length; i++) { pq.add(i); } int len = gas.length; A:while (!pq.isEmpty()){ Integer current = pq.poll(); int k = 0; int total = 0; for (int i = current; i < len && k < len; i++) { total+=gas[i]; total-=cost[i]; if (total < 0){ continue A; } if (i == len -1){ i = -1; } k++; } return current; } return -1; }
376 最长摇摆子序列
这个题的动态规划的解看的不是太懂，不过另一种解答方式更容易理解，既然是求出摇摆子序列，我们就根据这个上升和下降 列出对应的点
以上图为例，将上升的列在上面，下降的列在下面，其实不难看出，我们只要从每个段里面选一个数字，就能组成最长的摇摆子序列，保险起见例如选择每个段的最后一个数组 ，例如选择 1,17,5,15(10,13,15任选15) ,5(10和5选择5)，16,8，这样就能得出对应值
public static int wiggleMaxLength(int[] nums) { if (nums.length < 2) return nums.length; int begin = nums[1] == nums[0]?1:2; Boolean top = nums[1] == nums[0] ? null : nums[1]>nums[0]; for (int i = 2; i < nums.length; i++) { if ( ((top == null || top) && nums[i] < nums[i-1] ) || ((top == null || !top) && nums[i] > nums[i-1] ) ){ begin++; top = nums[i] > nums[i-1]; } } return begin; }
406 根据身高重建队列
这个题感觉找规律很重要，最终的规律就是 hi从高到底 ki从低到高 然后根据ki一直往链表i的位置插数据即可
public static int[][] reconstructQueue(int[][] people) { List<int[]> list = new ArrayList<>(); for (int i = 0; i < people.length; i++) { list.add(people[i]); } list.sort((k1,k2)->(k1[0] == k2[0]? k1[1]-k2[1]:k2[0] - k1[0] )); LinkedList<int[]> result = new LinkedList<>(); for (int[] ints : list) { result.add(ints[1],ints); } int[][] arr = new int[result.size()][2]; for (int i = 0; i < result.size(); i++) { arr[i] = result.get(i); } return arr; }
435 无重叠区间 和上题有些类似的地方
根据起点排序，如果后一个数组的起点大于前一个数组的终点 那就要删除一个，具体删除谁就看后一个区间是否被包含在前一个区间中
public static int eraseOverlapIntervals(int[][] people) { List<int[]> list = new ArrayList<>(); for (int[] person : people) { list.add(person); } list.sort((k1,k2)->k2[0]== k1[0] ?k1[1]-k2[1]:k1[0]-k2[0] ); int max = 0; int count = 0; for (int i = 0; i < list.size(); i++) { int[] ints = list.get(i); if (i == 0){ max = ints[1]; }else { if (ints[0] < max){ count++; if (ints[1] < max){ max = ints[1]; } } else { max = ints[1]; } } } return count; }
452 射气球
就是个求区间的问题
public static int findMinArrowShots(int[][] points) { if (points.length == 0){ return 0; } Arrays.sort(points,(k1,k2)->k2[0]== k1[0] ?k1[1]-k2[1]:k1[0]-k2[0] ); int count = 1; int min = points[0][0],max = points[0][1]; for (int i = 1; i < points.length; i++) { int[] shot = points[i]; min = Math.max(shot[0],min); max = Math.min(shot[1],max); if (min > max){ count++; min = shot[0]; max = shot[1]; }else { } } return count; }
621 任务调度器
利用堆来做的
class Solution { public int leastInterval(char[] tasks, int n) { if (n == 0){ return tasks.length; } Map<Character,Integer> map = new HashMap<>(); for (Character character : tasks) { map.put(character,map.getOrDefault(character,0)+1); } PriorityQueue<Character> pq = new PriorityQueue<>((k1,k2)->map.get(k2)-map.get(k1)); pq.addAll(map.keySet()); int k = 0; while (!pq.isEmpty()){ List<Character> list = new ArrayList<>(); int i = 0; for (; i < n+1 &&!pq.isEmpty(); i++) { Character poll = pq.poll(); Integer count = map.get(poll); k++; if (count > 1){ map.put(poll,count-1); list.add(poll); } } if (!list.isEmpty()){ pq.addAll(list); }else { if (pq.isEmpty()){ break; } } if (n+1 >i){ k+=n+1-i; } } return k; } }
leetcode 55,134,376,406,435,452,621
原文：https://www.cnblogs.com/hetutu-5238/p/14368392.html