• 算法学习day10（贪心算法）

    贪心算法：由局部最优->全局最优

    贪心算法一般分为如下四步：

    • 将问题分解为若干个子问题
    • 找出适合的贪心策略
    • 求解每一个子问题的最优解
    • 将局部最优解堆叠成全局最优解

    一、摆动序列（理解难）

    连续数字之间的差有正负的交替，则序列称为摆动序列。返回的nums值是摆动序列中元素的个数

    • 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

    • 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

    思路：将数组想象成一个上上下下的图表，定义curDiff=nums[i]-nums[i-1]；和preDiff=nums[i+1]-nums[i];

    考虑数组两端 : 假设在数组开头元素再添加一个相同的元素(或者初始化preDiff==0)，这样在遍历第一个元素的时候，就不会发生数组越界问题。if(preDiff>=0&&curDiff<0||preDiff<=0&&curDiff>0)

    前者对应的是先上再下，后者对应的是先下（可能为平坡）再上

    考虑到末尾元素，直接让result=1(默认最右边有一个峰值)

    单调坡度有平坡: 

    不是每一次遍历都要更新preDiff的值，而是当遇到峰值，前后波动的时候才去更新preDiff的值（为什么？）；

    代码：

    1. class Solution {
    2.     public int wiggleMaxLength(int[] nums) {
    3.         // 根据nums的长度剪枝
    4.         if (nums.length <= 1)return nums.length;
    5.         // 定义preDiff 和 curDiff 根据循环加result
    6.         int preDiff = 0;
    7.         int curDiff = 0;
    8.         int result = 1;// 把最后的元素看成一个峰值 直接+1
    9.         for (int i = 0; i < nums.length - 1; i++) {
    10.             curDiff = nums[i + 1] - nums[i];
    11.             if (preDiff <= 0 && curDiff > 0 || preDiff >= 0 && curDiff < 0) {
    12.                 result++;// 遇到峰值 前后波动
    13.                 preDiff = curDiff;
    14.             }
    15.         }
    16.         return result;
    17.     }
    18. }

    二、最大子序和（贪心法/dp）

    贪心法：

    由局部最优推导出全局最优：连续和变为负数，下一个元素就不要加连续和。连续和为正数再加。

    count+=nums[i] if(count>result)result=count; if(count<0)count=0;

    代码：

    1.     public int maxSubArray(int[] nums) {
    2.         int result=Integer.MIN_VALUE;
    3.         int count=0;
    4.         for(int i=0;i<nums.length;i++){
    5.             count+=nums[i];
    6.             if(count>result)result=count;
    7.             if(count<0)count=0;
    8.         }
    9.         return result;
    10.     }
    Dp（动态规划）:

    dp[i]:表示以从0->i这段集合的最大值。

    dp[i]=Math.max(dp[i-1]+nums[i],nums[i])。eg:以3为下标，如果dp[2]为负数那肯定不加，加上拖后腿。如果dp[i-1]为正数，那肯定加。

    代码：

    1. class Solution {
    2.     public int maxSubArray(int[] nums) {
    3.         int ans = Integer.MIN_VALUE;
    4.         int[] dp = new int[nums.length];
    5.         //dp[0]和nums[0]相等
    6.         dp[0] = nums[0];
    7.         ans = dp[0];
    8.  
    9.         for (int i = 1; i < nums.length; i++){
    10.             dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
    11.             ans = Math.max(dp[i], ans);
    12.         }
    13.  
    14.         return ans;
    15.     }
    16. }

    三、买卖股票的最佳时机(一次遍历)

    暴力法搜索的话会超时异常

    所以使用一次遍历：每次遍历到下标为i的元素时，就更新minprice。然后计算出在该天卖出，可以赚多少钱。

    之前的思想是：如果在今天买，什么时候卖可以赚更多的钱。

    现在的思想：如果今天卖，什么时候买可以赚更多钱。那我们就计算出今天之前的最小值，然后在那天买，今天卖，就可以找出最大利润。

    代码：

    1. class Solution {
    2.     public int maxProfit(int[] prices) {
    3.         int minprice = Integer.MAX_VALUE;
    4.         int maxprofit = 0;
    5.         for (int i = 0; i < prices.length; i++) {
    6.             if (prices[i] < minprice) {
    7.                 minprice = prices[i];
    8.             } else if (prices[i] - minprice > maxprofit) {
    9.                 maxprofit = prices[i] - minprice;
    10.             }
    11.         }
    12.         return maxprofit;
    13.     }
    14. }

    四、买卖股票的最佳时机II

    给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

    在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。返回 你能获得的 最大 利润。

     要求最大利润->就要求从第二天开始每一天的利润。

    局部利润最大->全局利润最大

    代码：

    1. class Solution {
    2.     public int maxProfit(int[] prices) {
    3.         int sumProfit=0;
    4.         for(int i=1;i<prices.length;i++){
    5.             if(prices[i]-prices[i-1]>0){
    6.                 sumProfit+=prices[i]-prices[i-1];
    7.             }
    8.         }
    9.         return sumProfit;
    10.     }
    11. }

    五、跳跃游戏(回溯/贪心)

    回溯法：

    宽度为nums[i]的大小，表示可以最大跳多远。for(int i=1;i<=nums[i]);i++)

    深度就是跳到最后一个元素所经历的节点个数。

    返回值:boolean；参数:int[] nums,int startIndex,boolean[] used

    终止条件：当startIndex==nums.length-1的时候，代表已经跳到了最后一个元素。如果>的话就跳超了，直接return false;

    单层递归逻辑：

    1.首先判断该点是不是遇到过(去重)if(used[startIndex]==true)return false;

    2.然后使用一个boolean的变量接收下一层遍历的返回值，如果下一层返回true，那么这一层也返回true。如果下一层返回false,说明下一个不行，直接used[i+startIndex]=true

    代码：

    1. class Solution {
    2.     public boolean canJump(int[] nums) {
    3.         if (nums.length == 1)
    4.             return true;// 只有一个元素的时候
    5.         boolean[] used = new boolean[nums.length];
    6.         return backTracking(nums, 0, used);
    7.     }
    8.  
    9.     public boolean backTracking(int[] nums, int startIndex, boolean[] used) {
    10.         if (startIndex == nums.length - 1)
    11.             return true;
    12.         if (startIndex > nums.length - 1)
    13.             return false;
    14.         if (used[startIndex])
    15.             return false;// 之前已经来过这个下标位置 已经试过这种情况了 就直接返回false
    16.  
    17.         for (int i = 1; i <= nums[startIndex]; i++) {
    18.             boolean flag = backTracking(nums, startIndex + i, used);
    19.             if (flag == true) {
    20.                 return true;
    21.             } else {
    22.                 used[startIndex + i] = true;
    23.             }
    24.         }
    25.         used[startIndex] = true;
    26.         return false;
    27.     }
    28. }
    贪心法：

    将跳跃问题->范围覆盖问题，如果在某点上，位置覆盖到nums.length-1，那么就说明可以跳到最后一个位置，返回true;

    在每次coverRange的范围里面，去更新coverRange的范围。coverRange=Math.max(coverRange,i+nums[i]);

    if(coverRange>=nums.length-1)。为什么是>=而不是==。因为如果是>=的话，最后一个节点在我跳跃的范围里面。

    代码：

    1.  
    2. class Solution {
    3.     public boolean canJump(int[] nums) {
    4.         if(nums.length==1)return true;
    5.         int coverRange=0;//覆盖的范围是元素的下标 所以下面的for循环可以使用=
    6.         for(int i=0;i<=coverRange;i++){
    7.             coverRange=Math.max(coverRange,i+nums[i]);
    8.             if(coverRange>=nums.length-1)return true;
    9.         }
    10.         return false;
    11.     }
    12. }

    六、跳跃游戏II(贪心)在上一道题的基础上求最小跳跃次数

    给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

    每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。

    返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

    思路：整体最优解：在一个范围里面,每次都往最远的跳。方式：在0->cur这个范围里面，找到下一次可以跳跃到的最远距离，next=Math.max(next,i+nums[i]);

    如果cur!=nums.length-1,说明还没有到达终点,那我们就要cur=next（改变范围），并且result++

    如果next==nums.length，result++然后跳

    代码：

    1. class Solution {
    2.     public int jump(int[] nums) {
    3.         if(nums.length<=1)return 0;
    4.         // 定义变量 cur next result
    5.         int cur = 0, next = 0, result = 0;
    6.         for (int i = 0; i < nums.length; i++) {
    7.             // 每次都更新一个范围里下次能跳到的最远距离
    8.             next = Math.max(i + nums[i], next);
    9.  
    10.             if(next>=nums.length-1){
    11.                 result++;
    12.                 break;
    13.             }   
    14.             if(i==cur){
    15.                 result++;
    16.                 cur=next;
    17.             }
    18.         }
    19.         return result;
    20.     }
    21. }

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

    贪心策略的选择：

    1.如果有负数的话，先对绝对值更大的负数进行取反，直到k为0；

    2.如果所有的负数都取反完后，k不为0并且为奇数，就对最小的非负数进行取反。如果k为偶数，不用变。

    注意：将数组从小到大排序之后，负数取反的值可能比之前的正数小，所以在取反并且k！=0后，要将数组再次排序。

    代码：

    1. class Solution {
    2.     public int largestSumAfterKNegations(int[] nums, int k) {
    3.         Arrays.sort(nums);//先对nums进行排序
    4.         int startK=k;
    5.         for(int i=0;i<nums.length;i++){
    6.             if(nums[i]<0&&k>0){
    7.                 nums[i]*=-1;
    8.                 k--;
    9.             }
    10.         }
    11.         //如果k不为0并且k为一个奇数，就选择一个最小的正数去抵消它
    12.         if(k%2!=0){
    13.             Arrays.sort(nums);
    14.             nums[0]*=-1;
    15.         }
    16.         return sumOfArr(nums);
    17.     }
    18.     public  int sumOfArr(int[] nums){
    19.         int sum=0;
    20.         for(int i:nums){
    21.             sum+=i;
    22.         }
    23.         return sum;
    24.     }
    25. }

    八、加油站(贪心)

    卡尔哥的思路：一个加油站可以a升，但是去下一个加油站要消耗b升,一个加油站可以获取/消耗的油为（a-b），

    1.使用变量curSum将它们累加起来，如果curSum<0，就说明汽油不够到达下一个加油站。那么此时将curSum置为零(i也会从下一个开始）,

    2.再使用一个变量totalSum将所有加油站的盈余都加起来，如果<0,就说明无论从哪一个起点开始都无法回到起点。

    代码：

    1. class Solution {
    2.     public int canCompleteCircuit(int[] gas, int[] cost) {
    3.         int gasSum=0;
    4.         int totalSum=0;
    5.         int index=0;
    6.         for(int i=0;i<gas.length;i++){
    7.             gasSum+=gas[i]-cost[i];//当前的累积量 如果<0 说明以i为起点的 无法循环
    8.             totalSum+=gas[i]-cost[i];//总的累积量 如果<0 绝对找不到一个起点
    9.             if(gasSum<0){
    10.                 index=(i+1)%gas.length;
    11.                 gasSum=0;
    12.             }
    13.         }
    14.         if(totalSum<0)return -1;
    15.         return index;
    16.     }
    17. }

    九、分发糖果(贪心法)

    n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

    • 每个孩子至少分配到 1 个糖果。
    • 相邻两个孩子评分更高的孩子会获得更多的糖果。

    请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。

    问题：一个孩子所分发的糖果是由两边人共同影响的。eg:2 5 3  2 。所分的糖果为1,2 但是第三个位置就不知道怎么确定了。

    思路：先从左边遍历，再从右边遍历，遍历到相同的位置要取最大值(因为同时要满足两个)

    代码：

    1. class Solution {
    2.     public int candy(int[] ratings) {
    3.         int[] candies=new int[ratings.length];
    4.         //首先我们从左往右遍历
    5.         candies[0]=1;
    6.         for(int i=1;i<ratings.length;i++){
    7.             if(ratings[i]>ratings[i-1])
    8.             candies[i]=candies[i-1]+1;
    9.             else candies[i]=1;
    10.         }
    11.  
    12.         //我们从右往左遍历
    13.         for(int i=ratings.length-2;i>=0;i--){
    14.             if(ratings[i]>ratings[i+1]){
    15.                 candies[i]=Math.max(candies[i],candies[i+1]+1);
    16.             }
    17.         }
    18.         return sumOfArr(candies);
    19.         
    20.     }
    21.     public int sumOfArr(int[] candies){
    22.         int sum=0;
    23.         for(int i:candies){
    24.             sum+=i;
    25.         }
    26.         return sum;
    27.     }
    28. }

    十、柠檬水找零(暴力)

    暴力法：对bills[i]进行分情况判断,==5/==10/==20。使用一个map集合当做钱包

    1.等于5的时候，直接往map集合中添加

    2.等于10的时候，先判断5的是否>=1，然后更新一下5和10的数量

    3.等于20的时候，优先使用5和10的进行支付，然后选择三个5的进行支付。(因为5还要去支付10的)

    代码：

    1. class Solution {
    2.     public boolean lemonadeChange(int[] bills) {
    3.         //使用一个map集合存钱
    4.         Map<Integer, Integer> map = new HashMap();
    5.         map.put(5,0);
    6.         map.put(10,0);
    7.         for (int i = 0; i < bills.length; i++) {
    8.             if (bills[i] == 5) map.put(5, map.get(5) + 1);
    9.             else if (bills[i] == 10) {
    10.                 if (map.get(5) >= 1) {
    11.                     map.put(5, map.get(5) - 1);
    12.                     map.put(10, map.get(10) + 1);
    13.                 } else {
    14.                     return false;
    15.                 }
    16.             } else if (bills[i] == 20) {
    17.                 if(map.get(10)>0&&map.get(5)>0){
    18.                     map.put(10,map.get(10)-1);
    19.                     map.put(5,map.get(5)-1);
    20.                 }else if(map.get(5)>=3){
    21.                     map.put(5,map.get(5)-3);
    22.                 }else{
    23.                     return false;
    24.                 }
    25.             }
    26.         }
    27.         return true;
    28.     }
    29. }

    十一、根据身高重建队列（贪心）

    Arrays.sort()函数中可以自定义一个comparator规则，一般使用Lambda表达式简化书写(我感觉可读性不高)。

    匿名内部类：（当我们只需要用一次的时候，就不需要再创建一个类，而是通过匿名内部类来实现）

    例如：

    1. public class Demo {
    2.     public static void main(String[] args) {
    3.         //创建匿名内部类，直接重写父类的方法，省去了创建子类继承，创建子类对象的过程
    4.      Fu fu= new Fu(){
    5.             @Override
    6.             public void method() { //重写父类method方法
    7.                 super.method();
    8.                 
    9.             }
    10.         };
    11.      fu.method();   //调用method方法
    12.     }

    思路：将people[][]二维数组，通过Arrays.sort()排序。排序规则为:根据身高h排，即people[i][0]。

    如果身高相等那么，根据前面的人：people[i][1]来排，升序排

    第一种是普通的写法/第二种是使用lambda表达式简化开发

    1.         Arrays.sort(people, new Comparator<int[]>() {
    2.             @Override
    3.             public int compare(int[] o1, int[] o2) {
    4.                 if(o1[0]==o2[0])return o1[1]-o2[1];
    5.                 return o2[0]-o1[0];
    6.             }
    7.         });
    1.         Arrays.sort(people,((o1, o2) -> {
    2.             if(o1[0]==o2[0])return o2[1]-o2[0];
    3.             return o2[0]-o1[0];//降序排
    4.                 })
    5.         );

    排序好之后，根据people[i][k]来进行排序，k为多少就插到下标为多少的位置。

    java中的集合直接封装好了add(int index,T element)方法；

    add(peo[1],peo);

    代码：

    1.     public int[][] reconstructQueue(int[][] people) {
    2.         Arrays.sort(people,(a,b)->{
    3.             if(a[0]==b[0])return a[1]-b[1];//如果身高相同 就比k k越小应该在越前面 所以是a-b
    4.             return b[0]-a[0];//降序排 是b-a
    5.         });
    6.  
    7.         LinkedList<int[]> queue=new LinkedList<>();
    8.         for(int[] peo:people){
    9.             queue.add(peo[1],peo);
    10.         }
    11.         return queue.toArray(new int[people.length][]);
    12.     }

  • 相关阅读:
    彻底掌握Protobuf编码原理与实战
    nfs共享本机目录遇到错误
    为何越来越多人选择进入软件测试行业？深度剖析软件测试的优势...
    五、伊森商城 前端基础-Vue v-text&v-html&v-bind&v-model p23
    QT信号槽实现原理
    linux查看外网ip的5种方法
    Cocoa-window
    【深入浅出Java并发编程指南】「源码分析篇」透析ThreadLocal线程私有区域的运作机制和源码体系
    穿越火线几次体验良好的游戏优化方案
    正点原子IMX6ULL驱动开发复盘
  • 原文地址：https://blog.csdn.net/2301_78191305/article/details/140305450