快手等视频网站做推广,wordpress 文章字体大小,机械推广平台有哪些,凡科互动官网登陆贪心算法#xff1a;由局部最优-全局最优
贪心算法一般分为如下四步#xff1a;
将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解
一、摆动序列#xff08;理解难#xff09;
连续数字之间的差有正负的交替…
贪心算法由局部最优-全局最优
贪心算法一般分为如下四步
将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解
一、摆动序列理解难
连续数字之间的差有正负的交替则序列称为摆动序列。返回的nums值是摆动序列中元素的个数 例如 [1, 7, 4, 9, 2, 5] 是一个 摆动序列 因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。 相反[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列第一个序列是因为它的前两个差值都是正数第二个序列是因为它的最后一个差值为零。
思路将数组想象成一个上上下下的图表定义curDiffnums[i]-nums[i-1]和preDiffnums[i1]-nums[i];
考虑数组两端 : 假设在数组开头元素再添加一个相同的元素(或者初始化preDiff0)这样在遍历第一个元素的时候就不会发生数组越界问题。if(preDiff0curDiff0||preDiff0curDiff0)
前者对应的是先上再下后者对应的是先下可能为平坡再上
考虑到末尾元素直接让result1(默认最右边有一个峰值)
单调坡度有平坡: 不是每一次遍历都要更新preDiff的值而是当遇到峰值前后波动的时候才去更新preDiff的值为什么
代码
class Solution {public int wiggleMaxLength(int[] nums) {// 根据nums的长度剪枝if (nums.length 1)return nums.length;// 定义preDiff 和 curDiff 根据循环加resultint preDiff 0;int curDiff 0;int result 1;// 把最后的元素看成一个峰值 直接1for (int i 0; i nums.length - 1; i) {curDiff nums[i 1] - nums[i];if (preDiff 0 curDiff 0 || preDiff 0 curDiff 0) {result;// 遇到峰值 前后波动preDiff curDiff;}}return result;}
}
二、最大子序和贪心法/dp
贪心法
由局部最优推导出全局最优连续和变为负数下一个元素就不要加连续和。连续和为正数再加。
countnums[i] if(countresult)resultcount; if(count0)count0;
代码 public int maxSubArray(int[] nums) {int resultInteger.MIN_VALUE;int count0;for(int i0;inums.length;i){countnums[i];if(countresult)resultcount;if(count0)count0;}return result;}
Dp动态规划:
dp[i]:表示以从0-i这段集合的最大值。
dp[i]Math.max(dp[i-1]nums[i],nums[i])。eg:以3为下标如果dp[2]为负数那肯定不加加上拖后腿。如果dp[i-1]为正数那肯定加。
代码
class Solution {public int maxSubArray(int[] nums) {int ans Integer.MIN_VALUE;int[] dp new int[nums.length];//dp[0]和nums[0]相等dp[0] nums[0];ans dp[0];for (int i 1; i nums.length; i){dp[i] Math.max(dp[i-1] nums[i], nums[i]);ans Math.max(dp[i], ans);}return ans;}
}
三、买卖股票的最佳时机(一次遍历)
暴力法搜索的话会超时异常
所以使用一次遍历每次遍历到下标为i的元素时就更新minprice。然后计算出在该天卖出可以赚多少钱。
之前的思想是如果在今天买什么时候卖可以赚更多的钱。
现在的思想如果今天卖什么时候买可以赚更多钱。那我们就计算出今天之前的最小值然后在那天买今天卖就可以找出最大利润。
代码
class Solution {public int maxProfit(int[] prices) {int minprice Integer.MAX_VALUE;int maxprofit 0;for (int i 0; i prices.length; i) {if (prices[i] minprice) {minprice prices[i];} else if (prices[i] - minprice maxprofit) {maxprofit prices[i] - minprice;}}return maxprofit;}
}四、买卖股票的最佳时机II
给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。
在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买然后在 同一天 出售。返回 你能获得的 最大 利润。 要求最大利润-就要求从第二天开始每一天的利润。
局部利润最大-全局利润最大
代码
class Solution {public int maxProfit(int[] prices) {int sumProfit0;for(int i1;iprices.length;i){if(prices[i]-prices[i-1]0){sumProfitprices[i]-prices[i-1];}}return sumProfit;}
}
五、跳跃游戏(回溯/贪心)
回溯法
宽度为nums[i]的大小表示可以最大跳多远。for(int i1;inums[i]);i)
深度就是跳到最后一个元素所经历的节点个数。
返回值:boolean参数:int[] nums,int startIndex,boolean[] used
终止条件当startIndexnums.length-1的时候代表已经跳到了最后一个元素。如果的话就跳超了直接return false;
单层递归逻辑
1.首先判断该点是不是遇到过(去重)if(used[startIndex]true)return false;
2.然后使用一个boolean的变量接收下一层遍历的返回值如果下一层返回true那么这一层也返回true。如果下一层返回false,说明下一个不行直接used[istartIndex]true
代码
class Solution {public boolean canJump(int[] nums) {if (nums.length 1)return true;// 只有一个元素的时候boolean[] used new boolean[nums.length];return backTracking(nums, 0, used);}public boolean backTracking(int[] nums, int startIndex, boolean[] used) {if (startIndex nums.length - 1)return true;if (startIndex nums.length - 1)return false;if (used[startIndex])return false;// 之前已经来过这个下标位置 已经试过这种情况了 就直接返回falsefor (int i 1; i nums[startIndex]; i) {boolean flag backTracking(nums, startIndex i, used);if (flag true) {return true;} else {used[startIndex i] true;}}used[startIndex] true;return false;}
}
贪心法
将跳跃问题-范围覆盖问题如果在某点上位置覆盖到nums.length-1那么就说明可以跳到最后一个位置返回true;
在每次coverRange的范围里面去更新coverRange的范围。coverRangeMath.max(coverRange,inums[i]);
if(coverRangenums.length-1)。为什么是而不是。因为如果是的话最后一个节点在我跳跃的范围里面。
代码 class Solution {public boolean canJump(int[] nums) {if(nums.length1)return true;int coverRange0;//覆盖的范围是元素的下标 所以下面的for循环可以使用for(int i0;icoverRange;i){coverRangeMath.max(coverRange,inums[i]);if(coverRangenums.length-1)return true;}return false;}
}
六、跳跃游戏II(贪心)在上一道题的基础上求最小跳跃次数
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
思路整体最优解在一个范围里面,每次都往最远的跳。方式在0-cur这个范围里面找到下一次可以跳跃到的最远距离nextMath.max(next,inums[i]);
如果cur!nums.length-1,说明还没有到达终点,那我们就要curnext改变范围并且result
如果nextnums.lengthresult然后跳
代码
class Solution {public int jump(int[] nums) {if(nums.length1)return 0;// 定义变量 cur next resultint cur 0, next 0, result 0;for (int i 0; i nums.length; i) {// 每次都更新一个范围里下次能跳到的最远距离next Math.max(i nums[i], next);if(nextnums.length-1){result;break;} if(icur){result;curnext;}}return result;}
} 七、K次取反后最大化的数组和
贪心策略的选择
1.如果有负数的话先对绝对值更大的负数进行取反直到k为0
2.如果所有的负数都取反完后k不为0并且为奇数就对最小的非负数进行取反。如果k为偶数不用变。
注意将数组从小到大排序之后负数取反的值可能比之前的正数小所以在取反并且k0后要将数组再次排序。
代码
class Solution {public int largestSumAfterKNegations(int[] nums, int k) {Arrays.sort(nums);//先对nums进行排序int startKk;for(int i0;inums.length;i){if(nums[i]0k0){nums[i]*-1;k--;}}//如果k不为0并且k为一个奇数就选择一个最小的正数去抵消它if(k%2!0){Arrays.sort(nums);nums[0]*-1;}return sumOfArr(nums);}public int sumOfArr(int[] nums){int sum0;for(int i:nums){sumi;}return sum;}
}
八、加油站(贪心)
卡尔哥的思路一个加油站可以a升但是去下一个加油站要消耗b升,一个加油站可以获取/消耗的油为a-b
1.使用变量curSum将它们累加起来如果curSum0就说明汽油不够到达下一个加油站。那么此时将curSum置为零(i也会从下一个开始,
2.再使用一个变量totalSum将所有加油站的盈余都加起来如果0,就说明无论从哪一个起点开始都无法回到起点。
代码
class Solution {public int canCompleteCircuit(int[] gas, int[] cost) {int gasSum0;int totalSum0;int index0;for(int i0;igas.length;i){gasSumgas[i]-cost[i];//当前的累积量 如果0 说明以i为起点的 无法循环totalSumgas[i]-cost[i];//总的累积量 如果0 绝对找不到一个起点if(gasSum0){index(i1)%gas.length;gasSum0;}}if(totalSum0)return -1;return index;}
}
九、分发糖果(贪心法)
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
每个孩子至少分配到 1 个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果计算并返回需要准备的 最少糖果数目 。
问题一个孩子所分发的糖果是由两边人共同影响的。eg:2 5 3 2 。所分的糖果为1,2 但是第三个位置就不知道怎么确定了。
思路先从左边遍历再从右边遍历遍历到相同的位置要取最大值(因为同时要满足两个)
代码
class Solution {public int candy(int[] ratings) {int[] candiesnew int[ratings.length];//首先我们从左往右遍历candies[0]1;for(int i1;iratings.length;i){if(ratings[i]ratings[i-1])candies[i]candies[i-1]1;else candies[i]1;}//我们从右往左遍历for(int iratings.length-2;i0;i--){if(ratings[i]ratings[i1]){candies[i]Math.max(candies[i],candies[i1]1);}}return sumOfArr(candies);}public int sumOfArr(int[] candies){int sum0;for(int i:candies){sumi;}return sum;}
}
十、柠檬水找零(暴力)
暴力法对bills[i]进行分情况判断,5/10/20。使用一个map集合当做钱包
1.等于5的时候直接往map集合中添加
2.等于10的时候先判断5的是否1然后更新一下5和10的数量
3.等于20的时候优先使用5和10的进行支付然后选择三个5的进行支付。(因为5还要去支付10的)
代码
class Solution {public boolean lemonadeChange(int[] bills) {//使用一个map集合存钱MapInteger, Integer map new HashMap();map.put(5,0);map.put(10,0);for (int i 0; i bills.length; i) {if (bills[i] 5) map.put(5, map.get(5) 1);else if (bills[i] 10) {if (map.get(5) 1) {map.put(5, map.get(5) - 1);map.put(10, map.get(10) 1);} else {return false;}} else if (bills[i] 20) {if(map.get(10)0map.get(5)0){map.put(10,map.get(10)-1);map.put(5,map.get(5)-1);}else if(map.get(5)3){map.put(5,map.get(5)-3);}else{return false;}}}return true;}
}
十一、根据身高重建队列贪心
Arrays.sort()函数中可以自定义一个comparator规则一般使用Lambda表达式简化书写(我感觉可读性不高)。
匿名内部类当我们只需要用一次的时候就不需要再创建一个类而是通过匿名内部类来实现
例如
public class Demo {public static void main(String[] args) {//创建匿名内部类直接重写父类的方法省去了创建子类继承创建子类对象的过程Fu fu new Fu(){Overridepublic void method() { //重写父类method方法super.method();}};fu.method(); //调用method方法} 思路将people[][]二维数组通过Arrays.sort()排序。排序规则为:根据身高h排即people[i][0]。
如果身高相等那么根据前面的人people[i][1]来排升序排
第一种是普通的写法/第二种是使用lambda表达式简化开发 Arrays.sort(people, new Comparatorint[]() {Overridepublic int compare(int[] o1, int[] o2) {if(o1[0]o2[0])return o1[1]-o2[1];return o2[0]-o1[0];}}); Arrays.sort(people,((o1, o2) - {if(o1[0]o2[0])return o2[1]-o2[0];return o2[0]-o1[0];//降序排}));
排序好之后根据people[i][k]来进行排序k为多少就插到下标为多少的位置。
java中的集合直接封装好了add(int index,T element)方法
add(peo[1],peo);
代码 public int[][] reconstructQueue(int[][] people) {Arrays.sort(people,(a,b)-{if(a[0]b[0])return a[1]-b[1];//如果身高相同 就比k k越小应该在越前面 所以是a-breturn b[0]-a[0];//降序排 是b-a});LinkedListint[] queuenew LinkedList();for(int[] peo:people){queue.add(peo[1],peo);}return queue.toArray(new int[people.length][]);}
