1005.K次取反后最大化的数组和
思路:要按照绝对值大小进行排序,负数转换后还不到k个选择最小值不断反转
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();
for (int i = 0; i < nums.length; i++) {
if (nums[i] < 0 && k > 0) {
nums[i] = -nums[i];
k--;
}
}
if (k % 2 == 1)
nums[nums.length - 1] = -nums[nums.length - 1];
return Arrays.stream(nums).sum();
}
}
134. 加油站
思路:计算每个对应加油站位置的差值,计算当前总和,小于0则从i+1重新开始。总的差值若小于0,则无法环路一周
class Solution {
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;
}
}
if (totalSum < 0)
return -1;
return start;
}
}
135. 分发糖果
思路:先从前向后遍历,如果右边>左边,当前值为左边值+1,小于左边就设置为1;从后向前遍历,如果左边大于右边,当前值为右边+1,最后选定的值为两次遍历中最大的
class Solution {
public int candy(int[] ratings) {
int len = ratings.length;
int[] candyVec = new int[len];
candyVec[0] = 1;
for (int i = 1; i < len; i++) {
candyVec[i] = (ratings[i] > ratings[i - 1] ? candyVec[i - 1] + 1 : 1);
}
for (int i = len - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
}
}
int ans = 0;
for (int num : candyVec) {
ans += num;
}
return ans;
}
}