1005.K次取反后最大化的数组和
题目链接：力扣
思路
一般能快速想到的就是排序后再进行翻转
1、负数比k多，这种直接翻转就可以
2、负数翻转完了还有k
1、如果剩下的k是偶数，就不用在反转了
2、如果是奇数，那就需要翻转目前数组中最小的数
为了避免这种情况，需要在遍历数组的途中，不断收集翻转之后最小数字
以上这种思路比较难处理的就是负数翻转完之后还有奇数k的情况，这样需要不断更新记录数组中的最小值，所以有更好的排序方法，那就是对数组按照绝对值从大到小的顺序进行排序
1、遍历数组，如果是负数，就进行翻转
2、翻转完负数之后，还有剩余的k
1、如果剩下的k是偶数，就可以直接相加了
2、如果剩下的k是奇数，数组的最后一个数组就是最小的数字，直接翻转就可以
其实这两个方法比较复杂的地方都是，翻转完所有的负数还剩的k为奇数，方法一选择的是在过程中记录这个最小数的下标。方法二是排序的之后就知道最终最小的数字在哪里了
如果使用第一种sort进行排序要记录比较复杂的话那就进行两次排序
K次取反后最大化的数组和
sort()两次排序
第一次排序取反
第二次排序找最小值
class Solution { public int largestSumAfterKNegations(int[] nums, int 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--; } } if (k % 2 == 1) { Arrays.sort(nums); nums[0] = -nums[0]; } for (int num : nums) { sum += num; } return sum; } }
sort()一次排序
取反的同时记录最小值，最终就是原数组的最大的负数的最小的非负数的绝对值在比较
class Solution { public int largestSumAfterKNegations(int[] nums, int k) { // 对数组进行排序 Arrays.sort(nums); int sum = 0; int index = 0; for (int i = 0; i < k; i++) { if (i < nums.length - 1 && nums[i] < 0) { nums[i] = -nums[i]; if (nums[index] >= Math.abs(nums[index + 1])) { index++; } continue; } nums[index] = -nums[index]; } for (int num : nums) { sum += num; } return sum; } }
绝对值排序
就是按照绝对值排序的写法比较复杂，其他就很好理解了
class Solution { public int largestSumAfterKNegations(int[] nums, int k) { int sum = 0; // 将数组按照绝对值从大到小进行排序 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) { nums[i] = -nums[i]; k--; } } System.out.println(k); if (k % 2 == 1) nums[len - 1] = -nums[len - 1]; for (int num : nums) { sum += num; } return sum; } }
134. 加油站
题目链接：力扣
思路
没有状态，后面再仔细分析
加油站
暴力解法
C++的暴力解法可以，java的暴力解法会超出时长
class Solution { public int canCompleteCircuit(int[] gas, int[] cost) { for (int i = 0; i < cost.length; i++) { // 记录剩余的油量 int rest = gas[i] - cost[i]; int index = (i + 1) % cost.length; // 模拟以i为起点行驶一圈 while (rest > 0 && index != i) { rest += gas[index] - cost[index]; index = (index + 1) % cost.length; } if (rest >= 0 && index == i) { return i; } } return -1; } }
贪心算法（一）
没有状态，后面再仔细分析
贪心算法（二）
没有状态，后面再仔细分析
135. 分发糖果
题目链接：力扣
思路
没有状态，后面再仔细分析
分发糖果
class Solution { /** 分两个阶段 1、起点下标1 从左往右，只要 右边 比 左边 大，右边的糖果=左边 + 1 2、起点下标 ratings.length - 2 从右往左， 只要左边 比 右边 大，此时 左边的糖果应该 取本身的糖果数（符合比它左边大） 和 右边糖果数 + 1 二者的最大值，这样才符合 它比它左边的大，也比它右边大 */ 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; } }
