做网站编辑累不累凡科官方网

当前位置： 首页 > news >正文

做网站编辑累不累,凡科官方网,wordpress主题更换字体教程 | hu,做灯箱到哪个网站找业务目录 理论基础 一、简单贪心 LeetCode455#xff1a;分发饼干 二、中等贪心 2.1 序列问题 LeetCode376#xff1a;摆动序列 2.2 贪心股票问题 LeetCode121#xff1a;买卖股票的最佳时机 LeetCode121#xff1a;买卖股票的最佳时机ii 2.3 两个维度权衡问题 LeetCode135分发饼干 二、中等贪心 2.1 序列问题 LeetCode376摆动序列 2.2 贪心股票问题 LeetCode121买卖股票的最佳时机 LeetCode121买卖股票的最佳时机ii 2.3 两个维度权衡问题 LeetCode135分发糖果 三、较难问题 区间问题  LeetCode55跳跃游戏i LeetCode55跳跃游戏ii LeetCode452用最少数量的箭引爆气球 LeetCode435无重叠区间 LeetCode763划分字母区间 LeetCode56合并区间 其他 LeetCode53最大子序和 贪心算法其实就是没有什么规律可言所以大家了解贪心算法 就了解它没有规律的本质就够了。 不用花心思去研究其规律 没有思路就立刻看题解。基本贪心的题目 有两个极端要不就是特简单要不就是死活想不出来。   学完贪心之后再去看动态规划就会了解贪心和动规的区别。 理论基础 贪心的本质是选择每一阶段的局部最优从而达到全局最优。 举例有一堆钞票你可以拿走十张如果想达到最大的金额你要怎么拿指定每次拿最大的最终结果就是拿走最大数额的钱。 每次拿最大的就是局部最优最后拿走最大数额的钱就是推出全局最优。 再举一个例子如果是 有一堆盒子你有一个背包体积为n如何把背包尽可能装满如果还每次选最大的盒子就不行了。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。 什么时候用贪心呢没有固定的套路。刷题或者面试的时候手动模拟一下感觉可以局部最优推出整体最优而且想不到反例那么就试一试贪心。 贪心算法一般分为如下四步 将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解 一、简单贪心 LeetCode455分发饼干 思路这里的局部最优就是大饼干喂给胃口大的充分利用饼干尺寸喂饱一个 全局最优就是喂饱尽可能多的小孩。 所以可以尝试使用贪心策略先将饼干数组和小孩数组排序。然后从后向前遍历小孩数组用大饼干优先满足胃口大的并统计满足小孩数量。 class Solution {// 思路优先考虑胃口先喂饱大胃口public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int count 0;int start s.length - 1;// 遍历胃口for (int index g.length - 1; index 0; index–) {if(start 0 g[index] s[start]) {start–;count;}}return count;} } 二、中等贪心 2.1 序列问题 LeetCode376摆动序列 思路局部最优是删除连续坡度上的节点保证这个坡度有两个局部峰值 整体最优是整个序列拥有最多的局部峰值 在实际操作上实际连删除都不用做只需添加数组的局部峰值即可 本题的难度在于要考虑多种情况curdiff代表后一个坡度prediff代表前一个坡度 即单调有平坡、上下中间有平坡和只有两个数的情况具体分析见代码随想录 class Solution {public int wiggleMaxLength(int[] nums) {if (nums.length 1) {return nums.length;}//当前差值int curDiff 0;//上一个差值int preDiff 0;int count 1;for (int i 1; i nums.length; i) {//得到当前差值curDiff nums[i] - nums[i - 1];//如果当前差值和上一个差值为一正一负//等于0的情况表示初始时的preDiffif ((curDiff 0 preDiff 0) || (curDiff 0 preDiff 0)) {count;preDiff curDiff;}}return count;} } 这道题还可以用动态规划来做这里就不讲了。之后可以试着做一做。 2.2 贪心股票问题 LeetCode121买卖股票的最佳时机 思路局部最优即左界最小在局部最优的基础上要求的全局最优即右界最大也就是差值最大。 class Solution {public int maxProfit(int[] prices) {int max 0;int low Integer.MAX_VALUE; //保留左侧最小值for (int i 0; i prices.length; i) {low Math.min(low, prices[i]); // 取最左最小价格确定左界max Math.max(max, prices[i] - low); // 寻找右侧最大值}return max;} } LeetCode121买卖股票的最佳时机ii 思路局部最优即在区间中寻找所有的最大递增子区间且子区间之间不能重叠 整体最优取所有最大的递增子区间最后利润和也最大。 由于最后只要求利润该题可以变成只要收集每天的正利润而无需考虑区间的左右界。 // 贪心思路 class Solution {public int maxProfit(int[] prices) {int result 0;for (int i 1; i prices.length; i) {result Math.max(prices[i] - prices[i - 1], 0);}return result;} } 2.3 两个维度权衡问题 LeetCode135分发糖果 思路本题需要先确定一遍后在确定另一边从左到右的局部最优即只要右边评分比左边大右边的孩子就多一个糖果。全局最优评分高的右边孩子比左边孩子糖果更多。 本题需要先从左到右更新再从右到左这样才能满足相邻条件。从右到左局部最优取candyVec[i 1] 1 和 candyVec[i] 最大的糖果数量保证第i个小孩的糖果数量既大于左边的也大于右边的。全局最优相邻的孩子中评分高的孩子获得更多的糖果。 class Solution {/*分两个阶段1、起点下标1 从左往右只要 右边 比 左边 大右边的糖果左边 1不大于就取最小糖果数12、起点下标 ratings.length - 2 从右往左 只要左边 比 右边 大此时 左边的糖果应该 取本身的糖果数符合比它左边大 和 右边糖果数 1 二者的最大值这样才符合 它比它左边的大也比它右边大/public int candy(int[] ratings) {int len ratings.length;int[] candyVec new int[len];candyVec[0] 1;for (int i 1; i len; i) {candyVeci ? candyVec[i - 1] 1 : 1;}for (int i len - 2; i 0; i–) {if (ratings[i] ratings[i 1]) {candyVec[i] Math.max(candyVec[i], candyVec[i 1] 1);}}int ans 0;for (int num : candyVec) {ans num;}return ans;} } 三、较难问题 区间问题  LeetCode55跳跃游戏i 思路总共要跳nums.length-1步才能到达终点局部解即取最大跳跃步数max每次循环以第一轮的max为起点再次计算max的覆盖范围 整体解即所有的最大跳跃步数范围是否能覆盖到终点。 class Solution {public boolean canJump(int[] nums) {int max 0;for(int i0;imax;i){ //这里注意是小于等于maxmax更新等于以新一轮覆盖点为起点再次覆盖max Math.max(inums[i],max);if(maxnums.length-1) return true;}return false;} } LeetCode55跳跃游戏ii 思路局部解即每次的跳转步数尽可能最大这样跳跃次数就最小 整体解即范围覆盖到终点且跳跃次数最小 本题的关键在于什么时候对步数进行1用到两个变量curIndex和preIndex来确定位置 class Solution {public int jump(int[] nums) {int nextIndex 0;int curIndex 0;int count 0;for(int i0; inums.length;i){nextIndex Math.max(nextIndex,inums[i]);if(i curIndex){ //当走到当前的最大覆盖范围时判断是否到终点count; //如果没到就要跳一步curIndex nextIndex; //跳到更新过的下一坐标if(nextIndex nums.length - 1) break; //如果到了则走完了}}return count;} } LeetCode452用最少数量的箭引爆气球 思路写了435这道题就很容易了 class Solution {public int findMinArrowShots(int[][] points) {int count 1;Arrays.sort(points, (x,y)-Integer.compare(x[1],y[1]));int end points[0][1];for(int i1;ipoints.length;i){//只要右界排序记录不重叠的情况就可以了每次不重叠就需要多一支箭if(end points[i][0]){ count;end points[i][1];}}return count;} } LeetCode435无重叠区间 思路重叠区间问题通常有两种思路要么是按左边界排序要么是按右边界

1. 按右边界升序排列从左向右可以记录非重叠区间的个数总数-非重叠个数重叠个数 非重叠只要判断end和上一区间的左区间的关系 class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a,b)- {return Integer.compare(a[1],b[1]);});int count 1; //记录非重叠区间的个数int end intervals[0][1];for(int i 1;i intervals.length;i){if(end intervals[i][0]){ //无重叠区间,count,更新endcount;end intervals[i][1];}}return intervals.length-count;} }
2. 按左边界升序排序向左到右可以记录重叠的区间个数直接得到重叠个数就是移除个数 非重叠和重叠都要更新end之所以count取end和右界的较小值是因为可能会出现3个区间重叠的情况。 class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals, (a,b)- {return Integer.compare(a[0],b[0]);});int count 0; //记录重叠区间的个数int end intervals[0][1];for(int i 1;i intervals.length;i){if(end intervals[i][0]){ //无重叠区间,更新endend intervals[i][1];}else{count;end Math.min(end, intervals[i][1]); //重叠区间的end}}return count;} } LeetCode763划分字母区间 思路首先遍历计算每个字母的最后出现下标然后从头开始遍历并更新最远出现下标当到达最后序号时进行一次分割 class Solution {public ListInteger partitionLabels(String s) {ListInteger list new ArrayList();int[] record new int[26];//首先记录字母最后一次出现的下标for(int i0;is.length();i){record[s.charAt(i)-a] i;}int idx 0;int last -1;//然后当遍历下标等于最后一次的下标时添加字符串长度for(int i0;is.length();i){idx Math.max(idx, record[s.charAt(i)-a]);if(i idx){list.add(idx-last); //先添加结果到list再更新last idx;}}return list;} } LeetCode56合并区间 思路同样首先按照左边界先排序然后判断左边界和最右边界 记得判断到底属于那种情况 class Solution {public int[][] merge(int[][] intervals) {Listint[] res new LinkedList();Arrays.sort(intervals, (x,y)-Integer.compare(x[0],y[0]));int left intervals[0][0];int right intervals[0][1];for(int i 1; iintervals.length; i){if(right intervals[i][0]){ //重叠合并right Math.max(right, intervals[i][1]);}else{ //不重叠添加旧区间更新left、rightres.add(new int[]{left, right});left intervals[i][0];right intervals[i][1];}}res.add(new int[]{left, right});return res.toArray(new int[res.size()][2]);} } 其他 LeetCode53最大子序和 思路连续子数组局部最优即遇到连续和count为负数则立刻放弃当前count置0相当于从当前位置重新开始计算连续子数组和。整体最优即用sum来计算循环中count的最大值。 class Solution {public int maxSubArray(int[] nums) {if (nums.length 1){return nums[0];}int sum Integer.MIN_VALUE;int count 0;for (int i 0; i nums.length; i){count nums[i];sum Math.max(sum, count); // 取区间累计的最大值相当于不断确定最大子序终止位置if (count 0){count 0; // 相当于重置最大子序起始位置因为遇到负数一定是拉低总和}}return sum;} }