代码随想录算法训练营第31+天
今日任务
31+0：part01
● 455.分发饼干 ● 376. 摆动序列 ● 53. 最大子序和
31+1：part02
● 122.买卖股票的最佳时机 II ● 55. 跳跃游戏 ● 45.跳跃游戏 II ● 1005.K次取反后最大化的数组和
31+2：part03
● 134. 加油站 ● 135. 分发糖果 ● 860.柠檬水找零 ● 406.根据身高重建队列
31+3：part04
● 452. 用最少数量的箭引爆气球
455.分发饼干
自己想法
贪心在于：优先喂小胃口（用尽可能小的饼干）
class Solution {
public int findContentChildren(int[] g, int[] s) {
int ans = 0;
Arrays.sort(g);
Arrays.sort(s);
// 优先喂小胃口（用尽可能小的饼干）
for(int i = 0, j = 0; i < g.length && i < s.length; i++) { // 从小到大遍历胃口
while(j < s.length && g[i] > s[j]) j++; // 遍历饼干，找满足的最小饼干
if(j < s.length) {
ans++;
j++;
}
else break;
}
return ans;
}
}376. 摆动序列
自己想法
贪心在于：每找到一个大小变化的点，就加入摆动序列
class Solution {
public int wiggleMaxLength(int[] nums) {
if (nums.length <= 1) return nums.length;
int count = 1;
boolean need_upper = false;
int j = 1;
// 找一对不相等的数作为开始
while(j < nums.length && nums[j] == nums[j - 1]) j++;
if(j < nums.length) {
count = 2;
// 确定初始后下一步要什么样的数（大还是小）
if(nums[j] > nums[j - 1]) need_upper = false;
else need_upper = true;
for(int i = 2; i < nums.length; i++) {
if((nums[i] > nums[i - 1] && need_upper) || (nums[i] < nums[i - 1] && !need_upper)) {
count++;
need_upper = !need_upper;
}
}
}
return count;
}
}53. 最大子序和
自己想法
贪心在于：当前子序列是否还可能为整体做出贡献
class Solution {
public int maxSubArray(int[] nums) {
int i = 0;
int ans = 0;
// 找第一个非负数
while(i < nums.length && nums[i] <= 0) i++;
// 全为负数那就返回最大的负数
if(i >= nums.length) return Arrays.stream(nums).max().getAsInt();
// 有非负数则继续找
else {
// 变量初始化
int max_sum = nums[i]; // 记录当前找到的最大子序列和
int try_sum = 0; // 记录正在尝试的子序列和
ans = Math.max(ans, max_sum); // ans初始化为第一个非负数
i++;
while(i < nums.length) {
try_sum += nums[i]; // 更新尝试的子序列和
if(try_sum >= 0) { // 尝试的子序列可以为整体做出贡献时
max_sum += try_sum;
try_sum = 0;
ans = Math.max(ans, max_sum);
}
else { // 如果暂时还不能做出贡献
if(max_sum + try_sum < 0) { // 如果已经反向贡献已经拉满了，那么当前子序列已经成为累赘，舍弃
max_sum = 0;
try_sum = 0;
}
else {} // 反向贡献还没拉满，可以期待后续表现，什么都不干
}
i++;
}
return ans;
}
}
}题解想法
（思路一样，写法更简单）
局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
全局最优：选取最大“连续和”
局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。
class Solution {
public int maxSubArray(int[] nums) {
int ans = nums[0];
int try_sum = nums[0];
for(int i = 1; i < nums.length; i++) {
if(try_sum < 0) try_sum = 0;
try_sum += nums[i];
ans = Math.max(ans, try_sum);
}
return ans;
}
}122.买卖股票的最佳时机 II
自己想法
贪心在于：在下降点卖出，在上升点买入
class Solution {
public int maxProfit(int[] prices) {
int ans = 0;
if(prices.length <= 0) return ans;
int buy = 0;
boolean handle = false;
int i = 1;
while(i < prices.length) {
// 在下降点卖出
if(prices[i - 1] > prices[i] && handle) {
ans += (prices[i - 1] - buy);
handle = false;
}
// 在上升点买入
else if(prices[i - 1] < prices[i] && !handle) {
buy = prices[i - 1];
handle = true;
}
i++;
}
// 如果最后还持有，说明后面没有下降点了，此时也卖出
if(handle) ans += (prices[prices.length - 1] - buy);
return ans;
}
}题解想法
贪心在于：只收集正利润，最后稳稳的就是最大利润了
class Solution {
public int maxProfit(int[] prices) {
int result = 0;
for (int i = 1; i < prices.length; i++) {
result += Math.max(prices[i] - prices[i - 1], 0);
}
return result;
}
}55. 跳跃游戏
自己想法
贪心在于：遍历每个位置，更新最远能到达的位置（right），如果最远位置大于等于数组长度，说明能到达最后一个位置
class Solution {
public boolean canJump(int[] nums) {
int[] farthest = new int[nums.length];
// 计算每个位置能到达的最远位置
for(int i = 0; i < nums.length; i++) farthest[i] = i + nums[i];
int right = farthest[0];
// 注意判断条件的含义：i < farthest.length - 1 说明无需遍历最后一个位置，因为最后一个位置不需要跳跃
// 注意判断条件的含义：i <= right 说明当前位置能到达的最远位置，如果i > right，说明当前位置已经到不了了
for(int i = 1; i < farthest.length - 1 && i <= right; i++) {
if(right >= nums.length - 1) return true;
right = Math.max(right, farthest[i]);
}
if(right >= nums.length - 1) return true;
else return false;
}
}45.跳跃游戏 II
自己想法
贪心在于：使用step数组，记录到达每个位置所需的最小步数
class Solution {
public int jump(int[] nums) {
if(nums.length <= 1) return 0;
int[] farthest = new int[nums.length];
int[] steps = new int[nums.length]; // steps[i]表示到达i所需最小步数
for(int i = 0; i < nums.length; i++) farthest[i] = i + nums[i];
int right = farthest[0];
int count = 1;
steps[0] = 0;
for(int j = 1; j < steps.length && j <= right; j++) steps[j] = steps[0] + 1;
for(int i = 1; i < farthest.length - 1 && i <= right; i++) {
if(right >= nums.length - 1) return steps[nums.length - 1];
// 更新step数组只在right变大时更新旧right之后的部分，
// 因为更新逻辑是 steps[j] = steps[i] + 1，所以后面的一定大于前面的
int new_right = Math.max(right, farthest[i]);
for(int j = right + 1; j < steps.length && j <= new_right; j++) steps[j] = steps[i] + 1;
right = new_right;
}
return steps[nums.length - 1];
}
}1005.K次取反后最大化的数组和
自己想法
贪心在于：优先反转负数，之后反转0，全正数时反转绝对值最小的数
坑：
-
在 nums[j] < 0 的时候，不能反转完直接j++，因为
-
可能到了正负分界点，需重排序（全非负数）后，重新从第一个开始反转
-
可能 j 越界了（nums里没有非负数），就盯住着最后一个数，因为它的绝对值必然最小
-
-
nums[j] > 0 的时候，需要处理2次，判断到底能不能转回来
-
还至少可以反转2次（包括本次），那就相当于不反转，i多跳1次
-
否则反转，之后就结束for循环了
-
class Solution {
public int largestSumAfterKNegations(int[] nums, int k) {
Arrays.sort(nums);
for(int i = 0, j = 0; i < k; i++) {
if(nums[j] < 0) {
nums[j] = -nums[j];
// 如果到了正负分界点，重排序（全非负数）后，重新从第一个开始反转
if(j + 1 < nums.length && nums[j + 1] >= 0) {
Arrays.sort(nums);
j = 0;
}
// 如果到头了（nums里没有非负数），就盯住着最后一个数，因为它的绝对值必然最小
else if(j + 1 >= nums.length) continue;
else j++;
}
else if(nums[j] == 0) continue;
else {
// 还至少可以反转2次（包括本次），那就相当于不反转，i多跳1次
if(i + 1 < k) i++;
// 否则反转，之后就结束for循环了
else nums[j] = -nums[j];
}
}
return Arrays.stream(nums).sum();
}
}题解想法
贪心的思路，局部最优：让绝对值大的负数变为正数，当前数值达到最大
如果将负数都转变为正数了，K依然大于0，那么又是一个贪心：局部最优：只找数值最小的正整数进行反转
那么本题的解题步骤为：
-
第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
-
第二步：从前向后遍历，遇到负数将其变为正数，同时K--
-
第三步：如果K还大于0，那么反复转变数值最小的元素，将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();
int len = nums.length;
for (int i = 0; i < len; i++) {
//从前向后遍历，遇到负数将其变为正数，同时K--
if (nums[i] < 0 && K > 0) {
nums[i] = -nums[i];
K--;
}
}
// 如果K还大于0，那么反复转变数值最小的元素，将K用完
if (K % 2 == 1) nums[len - 1] = -nums[len - 1];
return Arrays.stream(nums).sum();
}
}134. 加油站
自己想法
感觉没贪，直接找全局最优了
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int least_index = 0;
int least_tank = 0;
int tank = 0;
// 假设邮箱可负，从0开始，遍历每个加油站
for(int i = 0; i < gas.length; i++) {
if(tank < least_tank) {
least_tank = tank;
least_index = i;
}
tank += (gas[i] - cost[i]);
}
// 如果最后的油箱大于等于0，说明可以绕一圈
if(tank >= 0) return least_index;
else return -1;
}
}135. 分发糖果
自己想法
找极值点，极小值点给1，极大值根据相距两个极小值的距离确定。
写起来复杂的一批，摸
题解想法
这在leetcode上是一道困难的题目，其难点就在于贪心的策略，如果在考虑局部的时候想两边兼顾，就会顾此失彼。
那么本题采用了两次贪心的策略：
一次是从左到右遍历，只比较右边孩子评分比左边大的情况。
一次是从右到左遍历，只比较左边孩子评分比右边大的情况。
这样从局部最优推出了全局最优，即：相邻的孩子中，评分高的孩子获得更多的糖果。
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;
}
}860.柠檬水找零
自己想法
贪心在于：优先找零10元，再找零5元
class Solution {
public boolean lemonadeChange(int[] bills) {
int dol_5 = 0;
int dol_10 = 0;
int dol_20 = 0;
for(int i = 0; i < bills.length; i++) {
if(bills[i] == 5) {
dol_5++;
}
else if(bills[i] == 10) {
dol_10++;
if(dol_5 >= 1) dol_5--;
else return false;
}
else {
dol_20++;
if(dol_10 >= 1) {
dol_10--;
if(dol_5 >= 1) dol_5--;
else return false;
}
else if(dol_5 >= 3) {
dol_5 -= 3;
}
else return false;
}
}
return true;
}
}406.根据身高重建队列
题解想法
class Solution {
public int[][] reconstructQueue(int[][] people) {
// 身高从大到小排（身高相同k小的站前面）
Arrays.sort(people, (a, b) -> {
if (a[0] == b[0]) return a[1] - b[1]; // a - b 是升序排列，故在a[0] == b[0]的狀況下，會根據k值升序排列
return b[0] - a[0]; //b - a 是降序排列，在a[0] != b[0]，的狀況會根據h值降序排列
});
LinkedList<int[]> que = new LinkedList<>();
for (int[] p : people) {
que.add(p[1],p); //Linkedlist.add(index, value)，會將value插入到指定index裡。
}
return que.toArray(new int[people.length][]);
}
}452. 用最少数量的箭引爆气球
自己想法
以起点升序排序（相同时按终点升序），遍历每个气球，right记录应该射箭的坐标，
如果当前气球的起点大于right，说明需要一支新的箭；
否则考虑更新right
class Solution {
public int findMinArrowShots(int[][] points) {
Arrays.sort(points, (a, b) -> {
if(a[0] == b[0]) return Integer.compare(a[1], b[1]);
else return Integer.compare(a[0], b[0]);
});
int arrows = 1;
int right = points[0][1];
for(int i = 1; i < points.length; i++) {
if(points[i][0] > right) {
arrows++;
right = points[i][1];
}
else {
right = Math.min(points[i][1], right);
}
}
return arrows;
}
}