长春市疫情防控最新政策_摄影作品发布平台_宁波网络推广联系方式_网站建设是干什么的

---

第八章 贪心算法

1 分发饼干

455.分发饼干

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子i，都有一个胃口值g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干j，都有一个尺寸s[j]。如果s[j]>=g[i]，我们可以将这个饼干j分配给孩子i，这个孩子会得到满足。你的目标是满足尽可能多的孩子，并输出这个最大数值。
输入：g = [1,2,3], s = [1,1] 输出：1

思路：

Method1：大贪心

排序后先满足大的再向前遍历，相当于是贪心的先选择最大的。

class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int count=0;int ig=g.length-1,is=s.length-1;while(is>=0&&ig>=0){if(s[is]>=g[ig]){is--;ig--;count++;}else    ig--;}return count;    }
}

Method2：小贪心

class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int count=0;int ig=0,is=0;while(is<s.length&&ig<g.length){if(s[is]>=g[ig]){is++;ig++;count++;}else    is++;}return count;    }
}

---

135.分发糖果

老师想给孩子们分发糖果，有N个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：每个孩子至少分配到1个糖果。相邻的孩子中，评分高的孩子必须获得更多的糖果。那么这样下来，老师至少需要准备多少颗糖果呢？
输入：ratings = [1,0,2] 输出：5

思路：
从左往右遍历一遍，分发一下右边大于左边的孩子，否则就是给一块，然后再从右往左遍历一遍，分发一下左边大于右边的孩子，否则就是给一块。最后去两边遍历的最大值求和即可。

class Solution {public int candy(int[] ratings) {int len=ratings.length;int[] left=new int[len];for(int i=0;i<len;i++){if(i>0&&ratings[i]>ratings[i-1]){left[i]=left[i-1]+1;}else{left[i]=1;}}int[] right=new int[len];for(int i=len-1;i>=0;i--){if(i<len-1&&ratings[i]>ratings[i+1]){right[i]=right[i+1]+1;}else{right[i]=1;}}int sum=0;for(int i=0;i<len;i++){sum+=Math.max(left[i],right[i]);}return sum;}
}

---

406.根据身高重建队列零

假设有打乱顺序的一群人站成一个队列，数组people表示队列中一些人的属性（不一定按顺序）。每个people[i]=[hi,ki]表示第i个人的身高为hi，前面正好有ki个身高大于或等于hi的人。
请你重新构造并返回输入数组people所表示的队列。返回的队列应该格式化为数组queue，其中queue[j]=[hj,kj]是队列中第j个人的属性（queue[0]是排在队列前面的人）。
输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]] 输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

思路：
与135分发糖果类似，也是需要考虑二维的贪心，也是两遍遍历确定，先确定身高，身高从高往低排，这个一定是有序的，再确定位置。

class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people, (a, b) -> ((a[0]==b[0])?Integer.compare(a[1],b[1]):Integer.compare(b[0],a[0])));LinkedList<int[]> que = new LinkedList<>();for (int[] p : people) {que.add(p[1],p);}return que.toArray(new int[people.length][]);}
}

---

2 摆动序列

376.摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
例如，[1,7,4,9,2,5]是一个摆动序列，因为差值(6,-3,5,-7,3)是正负交替出现的。相反,[1,4,7,2,5]和[1,7,4,5,5]不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
给定一个整数序列，返回作为摆动序列的最长子序列的长度。通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
输入：nums = [1,17,5,10,13,15,10,5,16,8] 输出：7
解释：这个序列包含几个长度为 7 摆动序列。其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

思路：
跳过平坡，即遇到相等元素直接跳过，记录上一次是上坡还是下坡。
若上一次是上坡，则只记录下坡，反之则只记录上坡，相当于只记录上坡和下坡数之和。

class Solution {public int wiggleMaxLength(int[] nums) {int sum=1;int flag=0;for(int i=1;i<nums.length;i++){if(nums[i]>nums[i-1]&&(flag==0||flag==-1)){sum++;flag=1;}else if(nums[i]<nums[i-1]&&(flag==0||flag==1)){sum++;flag=-1;}}return sum;}
}

---

3 跳跃游戏

55.跳跃游戏

给你一个非负整数数组nums，你最初位于数组的第一个下标。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标，如果可以，返回true；否则，返回false。
输入：nums = [2,3,1,1,4] 输出：true

思路：
动态规划，如果dp[i-1]<i说明根本到达不了，只需要对比前一个的dp和i+nums[i]即可。

class Solution {public boolean canJump(int[] nums) {int len=nums.length;int[] dp=new int[len+1];dp[0]=nums[0];for(int i=1;i<len;i++){if(dp[i-1]<i){dp[i-1]=0;return false;}dp[i]=Math.max(dp[i-1],i+nums[i]);}return true;}
}

---

45.跳跃游戏II

给定一个长度为n的0索引整数数组nums。初始位置为nums[0]。每个元素nums[i]表示从索引i向后跳转的最大长度。换句话说，如果你在nums[i]处，你可以跳转到任意nums[i+j]处:0<=j<=nums[i];i+j<n。返回到达nums[n-1]的最小跳跃次数。生成的测试用例可以到达nums[n-1]。
输入：nums = [2,3,1,1,4] 输出：2

思路：
动态规划，先将dp初始化为Integer.MAX_VALUE表示不可达，并将起点dp[0]设为0，从每个位置i开始，遍历其跳跃范围[i+1,nums[i]+i]，更新范围内每个位置的最小跳跃次数，从每个位置i开始，遍历其跳跃范围[i+1,nums[i]+i]，更新范围内每个位置的最小跳跃次数，最终，返回到达终点dp[len-1]的最小跳跃次数。

class Solution {public int jump(int[] nums) {int len=nums.length;int[] dp=new int[len+1];Arrays.fill(dp,Integer.MAX_VALUE);dp[0]=0;for(int i=0;i<len;i++){for(int j=i+1;j<Math.min(nums[i]+i+1,len);j++){dp[j]=Math.min(dp[j],dp[i]+1);}}return dp[len-1];}
}

---

4 K次取反后最大化的数组和

1005.K次取反后最大化的数组和

给你一个整数数组nums和一个整数k，按以下方法修改该数组：选择某个下标i并将nums[i]替换为-nums[i]。重复这个过程恰好k次。可以多次选择同一个下标i。以这种方式修改数组后，返回数组可能的最大和。
输入：nums = [4,2,3], k = 1 输出：5

思路：
遍历数组，找出最小的，然后取反，对sum乘两次即可，然后k次翻转即可，。

class Solution {public int largestSumAfterKNegations(int[] nums, int k) {int len = nums.length;	int min = Integer.MAX_VALUE;int min_index=0;	int sum = 0;     for (int j = 0; j < k; j++) {sum=0;for (int i = 0; i < len; i++) {if(nums[i]<min){min=nums[i];min_index=i;}sum += nums[i];}nums[min_index]=-nums[min_index];sum+=2*nums[min_index];min = Integer.MAX_VALUE;}return sum;}
}

---

5 加油站

134.加油站

在一条环路上有n个加油站，其中第i个加油站有汽油gas[i]升。你有一辆油箱容量无限的的汽车，从第i个加油站开往第i+1个加油站需要消耗汽油cost[i]升。你从其中的一个加油站出发，开始时油箱为空。给定两个整数数组gas和cost，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回-1。如果存在解，则保证它是唯一的。
输入：gas = [1,2,3,4,5], cost = [3,4,5,1,2] 输出：3

思路：
因为题目保证如果存在解，解是唯一的，那么如果存在解的情况下，cost的总和一定小于gas的总和，并且如果存在解的情况下，亏汽油最多的地方一定是解的地方。
最亏油的地方（累计油量最低的位置）是可以作为起点的地方。sum[i]=gas[0]-cost[0]+gas[1]-cost[1]+…+gas[i]-cost[i]取得最小值。sum[i]最小，意味着如果从0到i走过来的话，累计油量是最低的。但我们已经知道sum>=0，意味着在i+1之后的油量必须是上升的，否则总和不会非负。由于sum是逐渐上升的，从i+1开始出发，相当于跳过了最“低谷”的地方，让油量处于上升趋势，因此一定可以走完整圈。

class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int sum=0;int min=Integer.MAX_VALUE;int minIndex=-1;for(int i=0;i<gas.length;i++){sum=sum+gas[i]-cost[i];if(sum<min&&sum<0){min=sum;minIndex=i;}}if(sum<0)   return -1;return (minIndex+1)%gas.length;}
}

---

6 柠檬水找零

860.柠檬水找零

在柠檬水摊上，每一杯柠檬水的售价为5美元。顾客排队购买你的产品，（按账单bills支付的顺序）一次购买一杯。每位顾客只买一杯柠檬水，然后向你付5美元、10美元或20美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付5美元。注意，一开始你手头没有任何零钱。给你一个整数数组bills，其中bills[i]是第i位顾客付的账。如果你能给每位顾客正确找零，返回true，否则返回false。
输入：bills = [5,5,5,10,20] 输出：true

思路：
这里贪心的思路是优先花面值大的，再花面值小的。

class Solution {public boolean lemonadeChange(int[] bills) {int five = 0, ten = 0;for (int bill : bills) {if (bill == 5)five++;else if (bill == 10) {five--;ten++;} else if (ten>=1) {five--;ten--;} elsefive -= 3;if (five < 0)return false;}return true;}
}

---

7 合并区间

56.合并区间

以数组intervals表示若干个区间的集合，其中单个区间为intervals[i]=[starti,endi]。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]]

思路：
合并区间，注意自定义排序算法。按照左边界进行排序，左边界取最小，右边界取最大。如果新数组的左边界大于旧数组的右边界，就新开一个区域存数组。

class Solution {public int[][] merge(int[][] intervals) {if (intervals == null || intervals.length == 0) {return new int[0][0]; }Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));int len = intervals.length;int[][] arr = new int[len][2];arr[0] = new int[] { intervals[0][0], intervals[0][1] };int i = 0; for (int j = 1; j < len; j++) {int low = intervals[j][0];int high = intervals[j][1];if (low > arr[i][1]) {i++;	arr[i] = new int[] { low, high };} else {arr[i][1] = Math.max(arr[i][1], high);}}return Arrays.copyOfRange(arr, 0, i + 1);}
}

---

57.插入区间

给你一个无重叠的，按照区间起始端点排序的区间列表intervals，其中intervals[i]=[starti,endi]表示第i个区间的开始和结束，并且intervals按照starti升序排列。同样给定一个区间newInterval=[start,end]表示另一个区间的开始和结束。在intervals中插入区间newInterval，使得intervals依然按照starti升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。返回插入之后的intervals。
输入：intervals = [[1,3],[6,9]], newInterval = [2,5] 输出：[[1,5],[6,9]]

思路：
插入区间相当于合并区间加上一个区间，注意创建一个新的数组，其他与合并区间无异。

---

452.用最少数量的箭引爆气球

有一些球形气球贴在一堵用XY平面表示的墙面上。墙面上的气球记录在整数数组points，其中points[i]=[xstart,xend]表示水平直径在xstart和xend之间的气球。你不知道气球的确切y坐标。一支弓箭可以沿着x轴从不同点完全垂直地射出。在坐标x处射出一支箭，若有一个气球的直径的开始和结束坐标为xstart，xend，且满足xstart≤x≤xend，则该气球会被引爆。可以射出的弓箭的数量没有限制。弓箭一旦被射出之后，可以无限地前进。给你一个数组points，返回引爆所有气球所必须射出的最小弓箭数。
输入：points = [[10,16],[2,8],[1,6],[7,12]] 输出：2

思路：
合并区间，注意自定义排序算法。合并区间是前面取最小，后面取最大。这个是前面取最大，后面取最小。

class Solution {public int findMinArrowShots(int[][] points) {Arrays.sort(points, (a, b) -> (a[0]==b[0])?Integer.compare(a[1],b[1]):Integer.compare(a[0],b[0]));int len = points.length;int[][] arr = new int[len][2];arr[0] = new int[] { points[0][0], points[0][1] };int i = 0;for (int j = 1; j < len; j++) {int low = points[j][0];int high = points[j][1];if (low > arr[i][1]) {i++;    arr[i] = new int[] { low, high };} else {arr[i][0]=  Math.max(arr[i][0],low);arr[i][1] = Math.min(arr[i][1],high);}}return i+1;}
}

---

435.无重叠区间

给定一个区间的集合intervals，其中intervals[i]=[starti,endi]。返回需要移除区间的最小数量，使剩余区间互不重叠。注意只在一点上接触的区间是不重叠的。例如[1,2]和[2,3]是不重叠的。
输入：intervals = [[1,2],[2,3],[3,4],[1,3]] 输出：1

思路：
还是类似于合并区间，但是不同的是，合并区间是一个点重合也要把区间合并了，这个是一个点重合是不合并的，并且我们是要取右区间的最小值。

class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));int i = 0, len = intervals.length;int[][] arr = new int[len][2];arr[0] = new int[] { intervals[0][0], intervals[0][1] };for (int j = 1; j < len; j++) {int low = intervals[j][0];int high = intervals[j][1];if (low >= arr[i][1]) {i++;arr[i] = new int[] { low, high };} else {arr[i][1] = Math.min(arr[i][1], high);}}return len-(i + 1);}
}

---

763.划分字母区间

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
输入：S = “ababcbacadefegdehijhklij” 输出：[9,7,8]
解释： 划分结果为 “ababcbaca”, “defegde”, “hijhklij”。

思路：
还是类似于合并区间，相当于按照字母的相近进行合并区间，这个题的难点是怎么把字母的首次出现和最后出现位置找到，也就是找到区间，运用大量api，需要熟练使用。

class Solution {List<Integer> list = new ArrayList<>();public List<Integer> partitionLabels(String s) {HashMap<Character, int[]> map = new HashMap<>();for (char c : s.toCharArray()) {if (!map.containsKey(c)) {map.put(c, new int[]{s.indexOf(c), s.lastIndexOf(c)});}}List<int[]> collect = new ArrayList<>(map.values());collect.sort((a, b) -> Integer.compare(a[0], b[0]));int[][] arr = collect.toArray(new int[0][0]);int[][] res = new int[arr.length][2];res[0] = new int[]{arr[0][0], arr[0][1]};int index=0;for(int i=1;i<arr.length;i++){int low=arr[i][0];int high=arr[i][1];if(low>res[index][1]) {index++;res[index] = new int[]{low, high};}else{res[index][1]=Math.max(res[index][1],high);}}for(int i=0;i<=index;i++){list.add(res[i][1]-res[i][0]+1);}return list;}
}

---

8 单调递增的数字

738.单调递增的数字

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）
输入：N = 332 输出：299

思路：
从右向左遍历数字，找到第一个违反单调递增的地方，即nums[i]>nums[i+1]。将nums[i]减1，然后把nums[i+1]及其后面的所有数字变成’9’，以保证最终结果尽可能大。继续向左检查，如果nums[i]–后仍然导致nums[i-1]>nums[i]，就继续调整，直到整个数是单调递增的。最终转换回整数，返回结果。

class Solution {public int monotoneIncreasingDigits(int n) {char[] nums = String.valueOf(n).toCharArray();for (int i = nums.length - 2; i >= 0; i--) {if (nums[i] > nums[i + 1]) {nums[i]--;for (int j = i + 1; j < nums.length; ++j) nums[j] = '9';}}return Integer.parseInt(new String(nums));}
}

---

9 监控二叉树

968.监控二叉树

给定一个二叉树，我们在树的节点上安装摄像头。节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。计算监控树的所有节点所需的最小摄像头数量。
输入：[0,0,null,0,0] 输出：1

思路：
定义三种状态：0（无覆盖，需要摄像头）；1（有摄像头）；2（已被覆盖，无需摄像头）。
若子节点0（无覆盖），当前节点必须放置摄像头（返回1，res++）；若子节点1（有摄像头），当前节点被覆盖（返回2）；若子节点2（已覆盖但无摄像头），当前节点无覆盖（返回0）。
使用后序遍历+贪心的思想，后序遍历负责从叶子节点进行处理摄像头的问题，局部最优最终推出全局最优。
如果当前节点为null，为了防止叶子节点防止摄像头，null节点默认被覆盖；如果左右节点都被覆盖了，那么该节点的状态则为未覆盖；如果左右节点有一个是无覆盖的情况，那么应该有一个摄像头放在当前节点；否则该节点应该是覆盖状态。

class Solution {int  res=0;public int minCameraCover(TreeNode root) {if(minCame(root)==0)    res++;return res;}public int minCame(TreeNode root){if(root==null)  return 2;int left=minCame(root.left);int  right=minCame(root.right);// 如果左右节点都覆盖了的话, 那么本节点的状态就应该是无覆盖,没有摄像头(2,2)if(left==2&&right==2)   return 0;else if(left==0||right==0){// 左右节点都是无覆盖状态,那根节点此时应该放一个摄像头// (0,0) (0,1) (0,2) (1,0) (2,0)// 状态值为 1 摄像头数 ++;res++;return 1;}else{// 左右节点的 状态为 (1,1) (1,2) (2,1) 也就是左右节点至少存在 1个摄像头，// 那么本节点就是处于被覆盖状态return 2;}}
}

---