贪心算法day03

给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A[i] 替换为 -A[i]，然后总共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）

以这种方式修改数组后，返回数组可能的最大和。

看到题目的第一想法

观察，排序，将所有的负数都转成正的

若K还有遗留，则将最小的值，反复取负

看到代码随想录之后的想法

     代码随想录：按照绝对值排序

用stream来排序的代码

nums = IntStream.of(nums)
             .boxed()
             .sorted((o1, o2) -> Math.abs(o2) – Math.abs(o1))
             .mapToInt(Integer::intValue).toArray();

计算数组的总和

Arrays.stream(nums).sum();

自己实现过程中遇到的困难

       我的实现比较繁琐用了两次排序，需要记住这种转成负数的办法

class Solution {
    /*public int largestSumAfterKNegations(int[] nums, int k) {
            //用贪心  局部和整体
            //K次，先把所有的负数转为正数
            //返回的是值可以排序
            Arrays.sort(nums);
            //把所有的负数转为正数
            int sum=0;
            for(int i=0;i<nums.length;i++){
                if(nums[i]<0&&k>0){
                    nums[i] = -nums[i];
                    k--;
                 }
                 sum+=nums[i];
                
            }
            
            if(k==0){
                return sum;
            }
            //都为正数了且K>0
            if(k%2==0){
                return sum;
            }
                Arrays.sort(nums);
                return sum-(nums[0]*2);
            

    }*/
    public int largestSumAfterKNegations(int[] nums, int K) {
            //代码随想录中按照绝对值的大小排序，不需要做额外的判断
            // 将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
	nums = IntStream.of(nums)
		     .boxed()
		     .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))
		     .mapToInt(Integer::intValue).toArray();
	int len = nums.length;	    
	for (int i = 0; i < len; i++) {
	    //从前向后遍历，遇到负数将其变为正数，同时K--
	    if (nums[i] < 0 && K > 0) {
	    	nums[i] = -nums[i];
	    	K--;
	    }
	}
	// 如果K还大于0，那么反复转变数值最小的元素，将K用完

	if (K % 2 == 1) nums[len - 1] = -nums[len - 1];
	return Arrays.stream(nums).sum();
    }
}

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1

看到题目的第一想法

使用暴力算法，gast和cost同时遍历，获得gast[i]-cost[i]的值，若为负数 则break

看到代码随想录之后的想法

暴力算法：为负数不用break，可以在最后进行判断，while(sum>=0&&j%5!=i) while加上个sum>=0的条件

看最后是否满足while跳出条件，也就是 sum>=0&j%5==i，如果满足即可，能把while 走完

贪心的做法：三个参数 start curNum totalNum

若局部的curNum为负数了，则令curNum=0，start为下一个下标重新开始记录

使用一个curNum 和一个totalNum ，totalNum记录每一次gast[i]-cost[i]的和加起来

而curNum记录当前gast[i]-cost[i]的和加起来

若totalNum<0 则不存在 返回-1

若totalNum>=0 则存在该节点，返回curNum计数的起始位置，前面为负的起始位置都给排除了

自己实现过程中遇到的困难

       //暴力算法中for循环里面加while的操作可以再熟悉一下

        能把终止的点加在while的条件中，而不用在while中break；其余的判断在while之后即可

      1 记录每一个差值，如果总和差值为负数，则不存在
      2 局部最优，若当前的差值和为负，那么就从差值和的下一个来判断是否可行
      3 全局最优，如果当前差值和一直到最后都不为负数，而总差值和>=0 则一定存在对应下标，在非负的差值和的第一个下标开始

class Solution {
/*    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;
        for(int i=0;i<gas.length;i++){
            int sum = 0;
            //从i开始 到i这个位置该怎么算呢？
            sum = gas[i]-cost[i];
            int j = (i+1)%len;
            while(j%len!=i){
                if(sum+gas[j]-cost[j]>=0){
                    sum+=gas[j]-cost[j];
                }else{
                    break;
                }
                j=((j+1))%len;
                if(j%len==i){
                    return j;
                }
            }
        }
        return -1;
    }*/
    //暴力解法，数组中每个元素都进行循环，判断是否满足一次
    //需要注意这种最后一次return的方法，我的return太复杂，其实只要在最后看是否满足while条件就行了
    /*  public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;
        for(int i=0;i<gas.length;i++){
            int j = (i+1)%len;
            int sum = gas[i]-cost[i];
            //从i开始 到i这个位置该怎么算呢？
            while(sum>0&&j%len!=i){
                    sum+=gas[j]-cost[j];
                    j=(j+1)%len;
            }
            //这样处理是可以的
            if(sum>=0&&j%len==i){
                return j;
            }
        }
        return -1;
    }*/
    //代码随想录贪心的逻辑:需要观察出，总差值和若为负数则不存在这种回路
    //1 记录每一个差值，如果总和差值为负数，则不存在
    //2 局部最优，若当前的差值和为负，那么就从差值和的下一个来判断是否可行
    //3 全局最优，如果当前差值和一直到最后都不为负数，而总差值和>=0 则一定存在对应下标，在非负的差值和的第一个下标开始
    public int canCompleteCircuit(int[] gas, int[] cost) {
        //差值和
        int curSum = 0;
        //总的差值和
        int totalSum = 0;
        //起始下标
        int start = 0;
        for(int i=0;i<gas.length;i++){
            curSum += gas[i]-cost[i];
            totalSum += gas[i] - cost[i];
            if(curSum<0){
                start=i+1;
                curSum = 0;
            }
        }
        //若总差值和<0 则不存在
        if(totalSum<0) return -1;
        return start;
    }
}

看到题目的第一想法

想着和之前求摆动序列的思路，用一个pre和cur，其实完全不一样

没有思路

看到代码随想录之后的想法

两次贪心，先处理从左到右的结果

再处理从右到左的结果

要看相邻孩子

用一个数组存放每次贪心的结果

先处理左边<右边:从第二个开始若左边<右边则记录在新数组中为

                             右边的元素值=左边的元素值+1

再处理右边<左边 从倒数第二个元素开始，若右边<左边，则

                              左边的元素=Max(右边的元素值+1,数组中原有的元素值)

自己实现过程中遇到的困难

        从左到右赋值问题 与前一个比较，填充在当前位置

        为什么第二次要从右到左，需要的是右边的结果，i依赖于i+1 的内容，所有要从i+1 往前遍历

• • 题目的要求是 相邻的孩子中，评分高的孩子必须获得更多的糖果；所以第一次是保证了 只要右边评分比左边大，右边的孩子就多一个糖果 ，所以第二次应该是从后往前遍历，保证 只要左边评分比右边大，左边的孩子就多一个糖果
  • 如果从前向后遍历，每次只会更新i，这个结果是依据i+1的，但是下次i+1也会更新 ，这个操作就会使得答案有问题
  • 然而如果是从后向前，那么左边比右边大则左边糖果为右边+1，这时候的右边就是第一次从前往后遍历后保证的结果

具体看注释

class Solution {
    public int candy(int[] ratings) {
        //我没找到思路
        //先找到最小的糖果，来左右判断，有点混乱
        //if(ratings[i-1]){
        //}

        //卡哥思路
        //两次贪心，先把左边<右边的处理好，再把右边<左边的处理好
        //存储好局部的值
        //先处理从左往右进行判断的最小糖果数量 统计下来 右边小于左边
        //再处理从右往左进行判断的糖果数量，左边小于右边，与之前统计下来的结果做一个比较，两者中取比较大的那个
        //有个疑惑：第二次统计会破坏第一次的结果吗？
        //不会破坏，因为第二次统计后，只会取两者中更大的那个
        //将两者中统计下来的值的总和加起来返回
        int candy[] = new int[ratings.length];
        for(int i=0;i<candy.length;i++){
            candy[i]=1;
        }
        //看右>左
        //注意赋值的是前一个元素的值+1
        for(int i=1;i<ratings.length;i++){
            if(ratings[i]>ratings[i-1]){
                candy[i] = candy[i-1]+1;
            }
        }
        //看左>右
        //注意赋值的是前一个元素的值+1
        //同时是两者中的最大值，两者中取最大的，代表只会去到比之前的大或者相等的，满足糖果最大数量
        for(int i=ratings.length-2;i>=0;i--){
            if(ratings[i]>ratings[i+1]){
                candy[i] = Math.max(candy[i],candy[i+1]+1);
            }
        }
        int result = 0;
        for(int i:candy){
            result+=i;
        }
        return result;
    }
}
返

代码007普通

打赏 收藏 海报 链接