当前位置:   article > 正文

【算法刷题day34】Leetcode:1005. K 次取反后最大化的数组和、134. 加油站、135. 分发糖果

【算法刷题day34】Leetcode:1005. K 次取反后最大化的数组和、134. 加油站、135. 分发糖果

草稿图网站
java的Deque

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

题目:1005. K 次取反后最大化的数组和
解析:代码随想录解析

解题思路

使用绝对值大小来排序,可以避免找哪个是最小的不必要的判断

代码

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        // Arrays.sort(nums);
        nums = IntStream.of(nums)//将传入的整型数组 nums 转换为一个原始类型流(IntStream)
                        .boxed()//IntStream 装箱为 Stream<Integer>,以便后续可以使用泛型方法操作流中的元素。
                        .sorted((o1, o2) -> Math.abs(o2) - Math.abs(o1))//传入一个比较器(Comparator)
                        .mapToInt(Integer::intValue).toArray();//将装箱后的流中的元素转换为整型。//返回一个包含流中所有元素的数组。

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0 && k > 0) {
                nums[i] *= -1;
                k--;
            }
        }
        if (k % 2 == 1)
            nums[nums.length-1] *= -1;

        return Arrays.stream(nums).sum();

    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

总结

数组求和方式Arrays.stream(nums).sum();

Leetcode 134. 加油站

题目:134. 加油站
解析:代码随想录解析

解题思路

若当前和<0,总和>=0,则当前和的下一个元素可以成为起点

代码

//暴力,以每个站点为起点走一轮
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        for (int i = 0; i < gas.length; i++) {
            int res = gas[i] - cost[i];
            int index = (i + 1) % gas.length;
            while (res > 0 && index != i) {
                res += gas[index] - cost[index];
                index = (index + 1) % gas.length;
            }
            if (res >= 0 && index == i)
                return i;
        }
        return -1;
    }
}

//贪心
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int curSum = 0;
        int totalSum = 0;
        int start = -1;
        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;
            }
        }
        if (totalSum < 0) return -1;
        return start;
    }
}

  • 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
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36

总结

暂无

Leetcode 135. 分发糖果

题目:135. 分发糖果
解析:代码随想录解析

解题思路

先给每人一颗,然后从左到右加一轮,从右到左加一轮(这一轮加的时候要取原来的糖果数和加的糖果数的最大值)。

代码

class Solution {
    public int candy(int[] ratings) {
        int[] candies = new int[ratings.length];
        Arrays.fill(candies, 1);
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i-1])
                candies[i] = candies[i-1] + 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 Arrays.stream(candies).sum();
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

总结

从右到左的时候,刚开始使用的是candies[i] =candies[i+1] + 1;而不是candies[i] = Math.max(candies[i], candies[i+1] + 1);这导致可能破坏从左到右的规则。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/神奇cpp/article/detail/737169
推荐阅读
相关标签
  

闽ICP备14008679号