算法学习day10（贪心算法）

07-14 1082阅读

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

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

将问题分解为若干个子问题
找出适合的贪心策略
求解每一个子问题的最优解

将局部最优解堆叠成全局最优解

一、摆动序列（理解难）

连续数字之间的差有正负的交替，则序列称为摆动序列。返回的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&&curDiffresult)result=count; if(count 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;i0){
                sumProfit+=prices[i]-prices[i-1];
            }
        }
        return sumProfit;
    }
}

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

回溯法：

宽度为nums[i]的大小，表示可以最大跳多远。for(int i=1;i的话就跳超了，直接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.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=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=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 {
            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 queue=new LinkedList();
        for(int[] peo:people){
            queue.add(peo[1],peo);
        }
        return queue.toArray(new int[people.length][]);
    }