算法学习day10(贪心算法)

时间:2024-07-13 07:14:44

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

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

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

一、摆动序列(理解难)

连续数字之间的差有正负的交替,则序列称为摆动序列。返回的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的值(为什么?);

代码:

class Solution {
    public int wiggleMaxLength(int[] nums) {
        // 根据nums的长度剪枝
        if (nums.length <= 1)return nums.length;
        // 定义preDiff 和 curDiff 根据循环加result
        int preDiff = 0;
        int curDiff = 0;
        int result = 1;// 把最后的元素看成一个峰值 直接+1
        for (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)

贪心法:

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

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

代码:

    public int maxSubArray(int[] nums) {
        int result=Integer.MIN_VALUE;
        int count=0;
        for(int i=0;i<nums.length;i++){
            count+=nums[i];
            if(count>result)result=count;
            if(count<0)count=0;
        }
        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 sumProfit=0;
        for(int i=1;i<prices.length;i++){
            if(prices[i]-prices[i-1]>0){
                sumProfit+=prices[i]-prices[i-1];
            }
        }
        return sumProfit;
    }
}

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

回溯法:

宽度为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

代码:

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;// 之前已经来过这个下标位置 已经试过这种情况了 就直接返回false

        for (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的范围。coverRange=Math.max(coverRange,i+nums[i]);

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

代码:


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

六、跳跃游戏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++然后跳

代码:

class Solution {
    public int jump(int[] nums) {
        if(nums.length<=1)return 0;
        // 定义变量 cur next result
        int cur = 0, next = 0, result = 0;
        for (int i = 0; i < nums.length; i++) {
            // 每次都更新一个范围里下次能跳到的最远距离
            next = Math.max(i + nums[i], next);

            if(next>=nums.length-1){
                result++;
                break;
            }   
            if(i==cur){
                result++;
                cur=next;
            }
        }
        return result;
    }
}

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

贪心策略的选择:

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

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

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

代码:

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);//先对nums进行排序
        int startK=k;
        for(int i=0;i<nums.length;i++){
            if(nums[i]<0&&k>0){
                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 sum=0;
        for(int i:nums){
            sum+=i;
        }
        return sum;
    }
}

八、加油站(贪心)

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

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

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

代码:

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int gasSum=0;
        int totalSum=0;
        int index=0;
        for(int i=0;i<gas.length;i++){
            gasSum+=gas[i]-cost[i];//当前的累积量 如果<0 说明以i为起点的 无法循环
            totalSum+=gas[i]-cost[i];//总的累积量 如果<0 绝对找不到一个起点
            if(gasSum<0){
                index=(i+1)%gas.length;
                gasSum=0;
            }
        }
        if(totalSum<0)return -1;
        return index;
    }
}

九、分发糖果(贪心法)

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

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

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

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

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

代码:

class Solution {
    public int candy(int[] ratings) {
        int[] candies=new int[ratings.length];
        //首先我们从左往右遍历
        candies[0]=1;
        for(int i=1;i<ratings.length;i++){
            if(ratings[i]>ratings[i-1])
            candies[i]=candies[i-1]+1;
            else candies[i]=1;
        }

        //我们从右往左遍历
        for(int i=ratings.length-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]){
                candies[i]=Math.max(candies[i],candies[i+1]+1);
            }
        }
        return sumOfArr(candies);
        
    }
    public int sumOfArr(int[] candies){
        int sum=0;
        for(int i:candies){
            sum+=i;
        }
        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集合存钱
        Map<Integer, 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)>0&&map.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(){
            @Override
            public void method() { //重写父类method方法
                super.method();
                
            }
        };
     fu.method();   //调用method方法
    }

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

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

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

        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public 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-b
            return b[0]-a[0];//降序排 是b-a
        });

        LinkedList<int[]> queue=new LinkedList<>();
        for(int[] peo:people){
            queue.add(peo[1],peo);
        }
        return queue.toArray(new int[people.length][]);
    }