1005.K次取反后最大化的数组和

文章：9. K次取反后最大化的数组和

题目：1005. K 次取反后最大化的数组和

【思路】

局部最优推出全局最优

题目蕴含了两次取反：

1.数组里有正数和负数，我们优先对负数进行取反。优先找绝对值最大的负数进行取反。

2.数组里面都是正数，我们优先对最小的正数进行反复取反。消耗取反次数。

步骤：

1.按数组绝对值的大小进行排序

2.对负数进行取反

以上完成第一次贪心的操作

3.k还没用完，（k是奇数）取最小的-1，（k是偶数）不用修改数组，完成第二次贪心，直接求和返回*

我觉得本题的难度在于怎么让数组按绝对值大小进行排序&&求和返回

  • Java实现

//数组按绝对值从大到小排序
nums = IntStream.of(nums).boxed().sorted((o1,o2) -> Math.abs(o2) - Math.abs(o1)).mapToInt(Integer::intValue).toArray();

  1. IntStream.of(nums) 将整数数组 nums 转换为一个 IntStream 流对象。
  2. .boxed() 将 IntStream 流对象中的元素装箱成 Integer 类型的对象。
  3. .sorted((o1,o2) -> Math.abs(o2) - Math.abs(o1)) 对流中的元素进行排序，排序规则为按照元素的绝对值从大到小排序。其中 (o1, o2) -> Math.abs(o2) - Math.abs(o1) 是一个 lambda 表达式，代表了一个比较器，用于对两个元素进行比较。
  4. .mapToInt(Integer::intValue) 将排序后的结果再次转换为一个 IntStream 流对象。
  5. .toArray() 将 IntStream 流对象中的元素转换为一个整数数组，并将其存储回 nums 数组中。

//数组求和
return Arrays.stream(nums).sum();

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    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++){
            if(nums[i] <0 && k>0){
                k--;
                nums[i] *= -1;
            }
        }
        if(k%2 == 1) nums[len-1] = -nums[len-1];
        //数组求和
        return Arrays.stream(nums).sum();
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func largestSumAfterKNegations(nums []int, k int) int {
    sort.Slice(nums,func(i,j int)bool{
        return math.Abs(float64(nums[i])) > math.Abs(float64(nums[j]))
    })

    for i:=0;i<len(nums);i++{
        if k >0&&nums[i] <0{
            if k > 0 && nums[i] <0{
                nums[i] = -nums[i]
                k--
            }
        }
    }
    if k %2 == 1 {
        nums[len(nums)-1] = - nums[len(nums)-1] 
    }
    res := 0
    for i:=0;i<len(nums);i++{
        res += nums[i]
    }
    return res
}

134.加油站

文章：11. 加油站

题目：134. 加油站

【思路】

直接从全局进行贪心选择：

  • 情况1：如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的。
  • 情况2：rest[i] = gas[i] - cost[i] 为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油没有断过那么0就是起点。
  • 情况3：如果累加的最小值是负数，汽车就要从非0节点出发，从后往前，看哪个节点能把这个负数填平，就把这个填平的节点当作出发节点。

或者我们从局部最优推出全局最优开始看：

局部最优：当前累加rest[i]的和curSum一旦小于0，起始位置至少要是i+1，因为从i之前开始一定不行。

全局最优：找到可以跑一圈的起始位置。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int cursum= 0;
        int total = 0;
        int start = 0;
        for(int i=0;i<gas.length;i++){
            cursum += gas[i] - cost[i];
            total += gas[i]-cost[i];
            if(cursum < 0){
                start = i+1;
                cursum = 0;
            }
        }
        if(total <0)return -1;
        return start;
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func canCompleteCircuit(gas []int, cost []int) int {
    curSum,totalSum,start :=0,0,0
    for i:=0;i<len(gas);i++{
        curSum += gas[i] - cost[i]
        totalSum += gas[i] - cost[i]
        if curSum < 0{
            start = i+1
            curSum =0
        }
    }
    if totalSum < 0{
        return -1
    }
    return start
}

135.分发糖果

文章：12. 分发糖果

题目：135. 分发糖果

【思路】

遇到需要思考两边的情况，我们先确定一边再去确定另一边。

1.只看右边小孩得分比左边小孩得分高的情况。第一个for循环

右小孩的糖果 = 左边小孩的糖果+1

2.左孩子比右孩子得分高。第二个for循环

左边小孩的糖果 = 右小孩的糖果+1

同时取以上两个值的最大值。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int candy(int[] ratings) {
        int res = 0;
        int[] candy = new int[ratings.length];
        //初始化为1 ，每个人都起码有一颗
        candy[0]=1;
        for(int i=1;i<ratings.length;i++){
            candy[i] =( ratings[i] >ratings[i-1])?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+1]+1,candy[i]);
            }
        }
        for(int i = 0 ; i < candy.length;i++){
            res += candy[i];
        }
        return res;
    }
}
  • Go实现
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
func candy(ratings []int) int {
    candy := make([]int,len(ratings))
    for i:=0 ;i <len(candy);i++{
        candy[i]=1
    }
    for i :=1;i<len(ratings);i++{
        if ratings[i] > ratings[i-1]{
            candy[i] = candy[i-1]+1
        }
    }
    for i :=len(ratings)-2;i>=0;i--{
        if ratings[i] > ratings[i+1]{
            candy[i] = max(candy[i+1]+1,candy[i])
        }
    }
    res:=0
    for _,i := range candy{
        res+= i
    }
    return res
}
func max(a,b int)int{
    if a > b{
        return a
    }
    return b
}

【算法总结】

  • K次取反后最大化的数组：使用贪心，将数组进行绝对值从大到小排列，首先对绝对值较大的负数进行取反；如果在数组的负数都被取反完而k还没有消耗完的时候，选择数组里面最小的值进行操作（判断此时的k是奇数还是偶数，奇数的话*-1，偶数不变）。
  • 加油站：使用贪心，局部最优：如果当前累加的rest[i] 为负数，则从i+1开始出发（使用totalSum+=get[i]-cost[i]和curSum+=get[i]-cost[i]和start=i+1）；全局最优：如果totalSum为负数，说明当前没有可以跑完一圈的情况存在，返回-1；否则返回start
  • 分发糖果：使用贪心，遇到这种需要向两边分别对比的情况我们优先确定其中一边的情况。我们首先需要对数组进行初始化（每个人都可以获得一颗糖果），然后开始比较右孩子比左孩子大的情况，如果右孩子比左孩子大的话candy[i] = candy[i-1]+1；然后我们比较左孩子比右孩子大的情况，如果左孩子比右孩子大的话candy[i] = candy[i+1]+1

【语言总结】

  • Java

//数组按绝对值从大到小排序
nums = IntStream.of(nums).boxed().sorted((o1,o2) -> Math.abs(o2) - Math.abs(o1)).mapToInt(Integer::intValue).toArray();

  1. IntStream.of(nums) 将整数数组 nums 转换为一个 IntStream 流对象。
  2. .boxed() 将 IntStream 流对象中的元素装箱成 Integer 类型的对象。
  3. .sorted((o1,o2) -> Math.abs(o2) - Math.abs(o1)) 对流中的元素进行排序，排序规则为按照元素的绝对值从大到小排序。其中 (o1, o2) -> Math.abs(o2) - Math.abs(o1) 是一个 lambda 表达式，代表了一个比较器，用于对两个元素进行比较。
  4. .mapToInt(Integer::intValue) 将排序后的结果再次转换为一个 IntStream 流对象。
  5. .toArray() 将 IntStream 流对象中的元素转换为一个整数数组，并将其存储回 nums 数组中。

//数组求和
return Arrays.stream(nums).sum();

  • Go实现
1
2
3
4
////数组按绝对值从大到小排序
sort.Slice(nums,func(i,j int)bool{
    return math.Abs(float64(nums[i])) > math.Abs(float64(nums[j]))
})

再次感谢卡尔劳斯的知识传递，感谢坚持到现在的自己，虽然已经摸了一天鱼。