1005

题目

给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：

  • 选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。

重复这个过程恰好 k 次。可以多次选择同一个下标 i 。

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

示例 1：

1
2
3
输入：nums = [4,2,3], k = 1
输出：5
解释：选择下标 1 ，nums 变为 [4,-2,3] 。

示例 2：

1
2
3
输入：nums = [3,-1,0,2], k = 3
输出：6
解释：选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。

示例 3：

1
2
3
输入：nums = [2,-3,-1,5,-4], k = 2
输出：13
解释：选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。

提示：

  • 1 <= nums.length <= 104
  • -100 <= nums[i] <= 100
  • 1 <= k <= 104

思路

这种类型的题 ，在力扣上都是简单的。 基本上都不需要使用贪心算法的思路。 直接使用简单的思路解就可以了。

  1. 先给所有的内容排序， 然后再遍历，如果nums[i]的值小于0 && 在k的范围内， 直接将其变为 -nums[i]即可。
  2. 如果所有的负数遍历完了， 但是k 依旧不等于0 ， 那么再次将刚才转换过的数组排序。
  3. 因为题中给出可以多次选择同一个下标 i 。 所以我们直接将最小的数转换即可。如果剩余的k%2 ==0，那么就是原数，反之就是相反数

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        int count = k;
        for(int i= 0 ; i < k && i<nums.length ; i++ ){
            if(nums[i] <= 0){
                nums[i] = -nums[i];
                count--;
            }
        }
        // 判断是否k == 0 ? 如果不等于还需要将最小的数继续转换为
        if(count > 0 ){
            Arrays.sort(nums);
            if( count % 2 != 0 ){
                nums[0] = -nums[0];
            }else{
                nums[0] = nums[0];
            }
        }
        
        int res =0 ;
        for(int j= 0 ; j < nums.length;j++){
            res += nums[j];
        }
        return res;
    }
}

134

题目

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

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

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

示例 1:

1
2
3
4
5
6
7
8
9
10
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

示例 2:

1
2
3
4
5
6
7
8
9
输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

提示:

  • gas.length == n
  • cost.length == n
  • 1 <= n <= 105
  • 0 <= gas[i], cost[i] <= 104

思路

按照贪心算法的思路：这道题分为三种情况讨论

  1. 剩余的汽油量的总和 > 0.并且累加的过程中没有出现负数，说明油没有断过，那么就是从0 开始的
  2. 剩余的汽油量总和 < 0 那么就是无法完成一周的任务
  3. 剩余的汽油量 > 0 . 但是累加过程中的curGas的最小值为 负数。那么从后往前，看哪个节点能将负数填平， 那么这个数所在的位置就是出发的位置

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        //这道题分为三种情况讨论 
        //1. 剩余的汽油量的总和 > 0.并且累加的过程中没有出现负数，说明油没有断过，那么就是从0 开始的
        //2. 剩余的汽油量总和 < 0 那么就是无法完成一周的任务
        //3. 剩余的汽油量 > 0 . 但是累加过程中的curGas的最小值为 负数。那么从后往前，看哪个节点能将负数填平， 那么这个数所在的位置就是出发的位置
        int curGas  = 0;
        int min = Integer.MAX_VALUE;
        for(int i =0 ;i< gas.length;i++){
            int tmepGas = gas[i] - cost[i];
            curGas += tmepGas;
            //在叠加剩余汽油量的时候，看是否出现最小剩余量为负数的，如果有， 那么就说明
            min = Math.min(min,curGas);
        }
        if(min >= 0 ) return 0;
        if(curGas < 0 ) return -1 ;
        for(int k = gas.length -1 ; k > 0 ; k--){
            int temp = gas[k] - cost[k];
            min += temp;
            if(min >=0 ){
                return k;
            }
        }
        return -1;
    }
}

135

题目

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

你需要按照以下要求，给这些孩子分发糖果：

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

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

示例 1：

1
2
3
输入：ratings = [1,0,2]
输出：5
解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

1
2
3
4
输入：ratings = [1,2,2]
输出：4
解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
     第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

提示：

  • n == ratings.length
  • 1 <= n <= 2 * 104
  • 0 <= ratings[i] <= 2 * 104

思路

本题自己的思路基本是乱的， 按照代码随想录中的思路来实现的，虽然最后理解了。 但是还是没有形成自己的实现思路

按照卡尔的思想

  1. 首先，实现这道题我们需要从两边分别去考虑， 不能只考虑一边，这样实现出来的结果只有一部分。（刚开始我也只考虑了一边）

  2. 先确定前后两个数中右边比左边大的情况。 那么就是从左向右遍历，索引① 和索引② 位置上的评分进行比较。如果索引②的比索引①的评分大 ，那么就将索引②的分到的糖果数量在索引①的基础上加 1。同理 ， 索引②和 索引③的评分比较，以此类推

  3. 通过上述的方式， 可以实现右边比左边大的情况，但是无法实现右边比左边小的情况。如果还是按照从左到右的情况比较， 那么就会下面这样的

image-20230905184135660

从左向右遍历比较 左边比右边评分大的情况。 这样就会出现相邻的小孩 明明评分不一样， 但是分的糖果是一样的，所以这样比较是不对的。

  1. 从右向左遍历 ，比较前后两个数中左边比右边大的情况。 先比较索引为 ratings.length - 2 和 索引为 ratings.length - 1两个的评分。 如果出现 ratings.length - 2的评分 比 ratings.length - 1的评分大， 那么就将索引为 ratings.length - 2分到的糖果在索引为 ratings.length - 1的基础上加一。 注意， 这里可能会出现之前 ratings.length - 2的糖果本来就比 ratings.length - 1的多的情况，要进行比较。 取最大值即可

  2. 最后将两种情况所得到的糖果数量全部加起来就是所有孩子分到的糖果总数。

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int candy(int[] ratings) {
        int[] gets = new int[ratings.length];
        Arrays.fill(gets,1);
        //从左向右比较 比较右边的是否比左边的大， 如果是， 那么右边的gets[i] + 1
        for(int i = 1; i < ratings.length; i++){
            if(ratings[i] > ratings[i-1]){
                gets[i] = gets[i-1] + 1;
            }
        }
        //从右向左比较 比较左边的是否比右边的大， 如果是， 那么左边的gets[i] + 1
        for(int j = ratings.length - 2; j >= 0; j--){
            if(ratings[j] > ratings[j + 1]){
                //还需要将之前的从左向右比较的结果＋进去
                gets[j] = Math.max(gets[j+1] + 1,gets[j]);
            }
        }
        //统计结果
        int res= 0 ;
        for(int i =0 ; i<gets.length;i++){
            res += gets[i];
        }
        return res;
    }
}

​