- 455. 分发饼干
- 376. 摆动序列
- 53. 最大子数组和
- 122. 买卖股票的最佳时机 II
- 55. 跳跃游戏
- 45. 跳跃游戏 II
- 1005. K 次取反后最大化的数组和
- 134. 加油站
- 135. 分发糖果
- 860. 柠檬水找零
- 总结
1 分发饼干
- 题目链接：455. 分发饼干 “455. 分发饼干”)
1.1 题目描述
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
示例1:
输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
示例2:
输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
1.2 思路
对两个数组先进行排序，然后优先满足胃口小的孩子(即两个数组均从头开始遍历，s[i] >= g[j]时则++i),或者优先满足胃口大的孩子(即两个数组从最后一位开始遍历，s[i] >= g[j]时则--i)。
完整代码如下：
Cpp实现
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(),s.end());
int i = s.size()-1, cnt = 0;
for(int j = g.size()-1; j >= 0 && i >= 0; --j){
if(s[i] >= g[j]){
--i;
++cnt;
}
}
return cnt;
}
};C实现
int compare(const void *a, const void *b){
return (*(int *)a - *(int *)b);
}
int findContentChildren(int* g, int gSize, int* s, int sSize){
qsort(g, gSize, sizeof(int), compare);
qsort(s, sSize, sizeof(int), compare);
int index = 0;
for(int i = 0; i < sSize; i++){
if(s[i] >= g[index]){
index++;
if(index == gSize) break;
}
}
return index;
} 2 摆动序列
- 题目链接：376. 摆动序列
2.1 题目描述
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。
例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。
给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。
示例1:
输入: nums = [1,7,4,9,2,5]
输出: 6
解释: 整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。
示例2:
输入: nums = [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。
示例3:
输入: nums = [1,2,3,4,5,6,7,8,9]
输出: 2
解释:
2.2 思路
局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列
完整代码如下：
Cpp实现
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int pre = 0, cur = 0;
int ans = 1;
for(int i = 1; i < nums.size(); ++i){
cur = nums[i] - nums[i-1];
if(cur > 0 && pre <= 0|| cur < 0 && pre >= 0){
pre = cur;
ans++;
}
}
return ans;
}
};C实现
int wiggleMaxLength(int* nums, int numsSize){
if (numsSize <= 1) return numsSize;
int curDiff = 0; // 当前一对差值
int preDiff = 0; // 前一对差值
int result = 1; // 记录峰值个数，序列默认序列最右边有一个峰值
for (int i = 1; i < numsSize; i++) {
curDiff = nums[i] - nums[i-1];
// 出现峰值
if ((curDiff > 0 && preDiff <= 0) || (preDiff >= 0 && curDiff < 0)) {
result++;
preDiff = curDiff;
}
}
return result;
} 3 最大子数组和
- 题目链接：53. 最大子数组和
3.1 题目描述
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例2:
输入: nums = [1]
输出: 1
示例3:
输入: nums = [5,4,-1,7,8]
输出: 23
3.2 思路
遍历整个数组，用sum变量来存储序列的加和，当sum < 0时说明从下一位再开始取比在原有已取的序列基础上继续取所能获得的序列和更大，因而将sum置为0，即以当前位为序列起始重新取连续子序列求和。
完整代码如下：
Cpp实现
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum = 0, ans = INT_MIN;
for(int n: nums){
sum += n;
ans = max(ans, sum);
if(sum <= 0){
sum = 0;
}
}
return ans;
}
};C实现
int maxSubArray(int* nums, int numsSize){
if(numsSize==1) return nums[0];
int ans = INT_MIN,tmp = 0;
for(int i=0;i<numsSize;i++){
if(tmp<0){
tmp = 0;
}
tmp += nums[i];
ans = fmax(ans,tmp);
}
return ans;
} 4 买卖股票的最佳时机 II
- 题目链接：122. 买卖股票的最佳时机 II
4.1 题目描述
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例1:
输入: prices = [7,1,5,3,6,4]
输出: 7
示例2:
输入: prices = [1,2,3,4,5]
输出: 4
示例3:
输入: prices = [7,6,4,3,1]
输出: 0
4.2 思路
遍历整个数组，当当前的价格比前一个价格大时说明前一天买入然后今天卖出是有利润的，如果连续几天都满足这个条件时，可以视为连续几天前一天买入后一天卖出，最终取得的利润和即为所求的答案。
完整代码如下：
Cpp实现
class Solution {
public:
int maxProfit(vector<int>& prices) {
int profit = 0;
int i = 1, n = prices.size();
for(; i < n; ++i){
if(prices[i] - prices[i-1] > 0){
profit += prices[i] - prices[i-1];
}
}
return profit;
}
};C实现
int maxProfit(int* prices, int pricesSize){
int ans=0;
for(int i=0;i<pricesSize-1;i++){
int tmp =0;
tmp = prices[i+1]-prices[i];
if(tmp>0){
ans = ans+tmp;
}
}
return ans;
} 5 跳跃游戏
- 题目链接：55. 跳跃游戏
5.1 题目描述
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例1:
输入: nums = [2,3,1,1,4]
输出: true
示例2:
输入: nums = [3,2,1,0,4]
输出: false
5.2 思路
创建一个变量right表示当前最远可以到达的位置，初始化为0，即初始状态下最远可以到达下标为0的位置。然后遍历数组，同时对right进行更新，更新规则为：上一个位置的最远距离和这个位置的最远距离中的最大值，前者为right，后者为i + nums[i]. 当最远距离大于等于最后一个位置的下标时说明可以到达，返回true，否则继续遍历直至遍历到最远到达的地方，如果此时还没到终点，而最远距离已经走完，说明无法到达终点，返回false.
完整代码如下：
Cpp实现
class Solution {
public:
bool canJump(vector<int>& nums) {
int right = 0, end = nums.size()-1;
for(int i = 0; i <= right; ++i){
right = max(right, i + nums[i]);
if(right >= end){
return true;
}
}
return false;
}
};C实现
bool canJump(int* nums, int numsSize){
if(numsSize <= 1) return true;
int ans = nums[0];
for(int i = 1; i <= ans; i++){
ans = fmax(ans, i + nums[i]);
if(ans >= numsSize - 1) return true;
}
return false;
} 6 跳跃游戏 II
- 题目链接：45. 跳跃游戏 II
6.1 题目描述
给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
示例1:
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
示例2:
输入: nums = [2,3,0,1,4]
输出: 2
6.2 思路
用一个变量来存储当前步可以走的最远距离right， 用另一个变量来存储下一步可以走的最远距离next_right，当走到right包括了终点时直接返回结果，否则判断是否到达当前步最远距离，若是则步数加1并将下一步的最远距离赋给当前步最远距离并进行遍历。
完整代码如下：
Cpp实现
class Solution {
public:
int jump(vector<int>& nums) {
int right = 0, next_right = 0, cnt = 0;
for(int i = 0; i <= right; ++i){
next_right = max(i + nums[i], next_right);
if(right >= nums.size() - 1){
break;
}
if(i == right){
++cnt;
right = next_right;
}
}
return cnt;
}
};C实现
int jump(int* nums, int numsSize){
int curCover = 0, nextCover = 0; //当前步的最远距离/下一步最远距离
int cnt = 0;
for(int i = 0; i<numsSize; i++){
nextCover = fmax(nextCover, nums[i]+i); //更新下一步最远距离
if(i == curCover){ //等于时说明已经走到当前步的最远处
if(curCover == numsSize - 1){ //如果最远处为终点，则return
break;
}else{ //否则说明还没到终点，继续跳
cnt++; //由于当前步已经走完，所以步数加1
curCover = nextCover; //更新当前步的最远距离
}
}
}
return cnt;
} 7 K 次取反后最大化的数组和
- 题目链接：1005. K 次取反后最大化的数组和
7.1 题目描述
给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
选择某个下标 i 并将 nums[i] 替换为 -nums[i] 。
重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
以这种方式修改数组后，返回数组 可能的最大和 。
示例1:
输入: nums = [4,2,3], k = 1
输出: 5
解释: 选择下标 1 ，nums 变为 [4,-2,3] 。
示例2:
输入: nums = [3,-1,0,2], k = 3
输出: 6
解释: 选择下标 (1, 2, 2) ，nums 变为 [3,1,0,2] 。
示例3:
输入: nums = [2,-3,-1,5,-4], k = 2
输出: 13
解释: 选择下标 (1, 4) ，nums 变为 [2,3,-1,5,4] 。
7.2 思路
先排序，然后遍历数组，当数组为负数时进行翻转并将k减去1，当k == 0结束遍历，或完成遍历后k仍大于零。然后再对翻转过后的数组进行排序，如果k大于零，注意，此时的数组中的数字均为非负数，那么我们将剩余翻转次数全用在排序后的数组的第一个数，即nums[0]，如果k为奇数则翻转nums[0]，为偶数则不变，然后算数组加和; 当k为零则不用管，直接求数组加和即可。
这里需要进行两次排序，可以进行优化处理来避免第二次排序。在翻转过程中用一个变量来存储当前遍历过的数(包括翻转过后的数)中最小数对应的索引，然后翻转后如果k为奇数则将最小值索引对应的值翻转然后再进行求和即可。但很奇怪，这样优化后内存反而用得多。
完整代码如下：
Cpp实现
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int size = nums.size();
for(int i = 0; k > 0 && i < size; ++i){
if(nums[i] < 0){
nums[i] = -nums[i];
--k;
}
}
sort(nums.begin(), nums.end());
if(k % 2) nums[0] = -nums[0];
int ans = 0;
for(int i = 0; i < size; ++i){
ans += nums[i];
}
return ans;
}
};C实现
int compare(const void *a, const void *b){
return (*(int *)a - *(int *)b);
}
int largestSumAfterKNegations(int* nums, int numsSize, int k){
if(numsSize == 1){
if(k%2 == 0) return nums[0];
else return -nums[0];
}
qsort(nums, numsSize, sizeof(int), compare);
for(int i = 0; i<numsSize && k > 0; i++){
if(nums[i] < 0){
nums[i] = -nums[i];
k--;
}
}
qsort(nums, numsSize, sizeof(int), compare);
if(k % 2){
nums[0] = -nums[0];
}
int ans = 0;
for(int i = 0; i<numsSize; i++){
ans += nums[i];
}
return ans;
} 8 加油站
- 题目链接：134. 加油站
8.1 题目描述
在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。
示例1:
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
示例2:
输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。
8.2 思路
用一个变量sum记录起始点到当前遍历到的位置的剩余油量，当sum < 0时说明从当前起始点无法到达当前位置，且此时当前位置必不能作为起点(此时gas和cost的差为负),因而起始点更新为当前位置的下个位置；同时用一个变量total_rest来记录全程的油量剩余，如果最后total_rest < 0则说明比不可能走完一圈，因而返回-1；否则返回当前起始点。
完整代码如下：
Cpp实现
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int index = 0, sum = 0, total_rest = 0;
for(int i = 0; i < gas.size(); ++i){
int rest = gas[i] - cost[i];
total_rest += rest;
sum += rest;
if(sum < 0){
sum = 0;
index = i + 1;
}
}
if(total_rest < 0) return -1;
return index >= gas.size() ? -1 : index;
}
};C实现
int canCompleteCircuit(int* gas, int gasSize, int* cost, int costSize){
int tmp[gasSize], last = 0, minVal = INT_MAX;
for(int i = 0; i < gasSize; i++){
tmp[i] = gas[i] - cost[i];
last += tmp[i];
minVal = fmin(minVal, last);
}
if(minVal >= 0) return 0;
for(int i = gasSize-1; i>=0; i--){
minVal += tmp[i];
if(minVal >= 0) return i;
}
return -1;
} 9 分发糖果
- 题目链接：135. 分发糖果
9.1 题目描述
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
示例1:
输入: ratings = [1,0,2]
输出: 5
解释: 你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。
示例2:输入: ratings = [1,2,2]
输出: 4
解释: 你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。
9.2 思路
贪心，遇到单调上升序列就逐位加1颗糖果，遇到相等的，把该位的糖果置为1;同样的，遇到单调下降序列就逐位加1颗(实际上是反过来的),当当前的单调下降序列的长度大于前一个单调上升序列时，要额外加1颗糖果，因为单调下降序列前一个(记为last同学)必定要比单调下降序列的起始位置大1，当当前的单调下降序列的长度大于前一个单调上升序列时说明原来分配给last同学的糖果少了。
用一个变量inc来记录当前的上升序列长度，用des来记录下降序列长度，当上升序列结束后需要将inc的值记录下来，这里用last_inc来保存，然后在下降序列中检测des >= last_inc是否满足，如果是则要给last同学多加1颗，体现在代码中就是直接让答案自加1. 注意相邻两个同学评分相等的情况，两个相等，不论前一个给了多少，下一个只给1颗，并且更新inc和des以及last_inc.
完整代码如下：
Cpp实现
class Solution {
public:
int candy(vector<int>& ratings) {
int des = 0, inc = 1, res = 1, last_inc = 1;
for(int i = 1; i < ratings.size(); ++i){
if(ratings[i] > ratings[i-1]){
++inc;
res += inc;
des = 0;
last_inc = inc;
}else if(ratings[i] == ratings[i-1]){
inc = 1;
des = 0;
last_inc = inc;
res++;
}else{
++des;
if(des >= last_inc) ++res;
res += des;
inc = 1;
}
}
return res;
}
};C实现
/*int candy(int* ratings, int ratingsSize){
int candy[ratingsSize];
candy[0] = 1;
for(int i = 1; i < ratingsSize; i++){ //从前向后遍历，当后一个比前一个评分高则后一个比前一个多一个
if(ratings[i] > ratings[i-1]){
candy[i] = candy[i-1]+1;
}else{
candy[i] = 1; //否则只给最少的数量，即1颗
}
}
int ans = candy[ratingsSize-1]; //从后向前遍历，如果前一个比后一个评分高，则前一个给比后一个多一个
for(int i = ratingsSize-1; i>= 1; i--){ //，但是要取原来的值与后一个+1中的最大，即fmax(candy[i], candy[i+1]+1)
if(ratings[i-1] > ratings[i]){
candy[i-1] = fmax(candy[i-1], candy[i] + 1);
}
ans += candy[i-1];
}
return ans;
}*/
int candy(int* ratings, int ratingsSize){
int ans = 1, pre = 1, dec = 0, inc = 1;
for(int i = 1; i<ratingsSize; i++){
if(ratings[i] >= ratings[i-1]){
dec = 0;
pre = ratings[i]==ratings[i-1] ? 1 : pre + 1;
inc = pre;
ans += pre;
}else{
pre = 1;
dec++;
if(dec == inc) dec += 1;
ans += dec;
}
}
return ans;
} 10 柠檬水找零
- 题目链接：860. 柠檬水找零
10.1 题目描述
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
示例1:
输入: bills = [5,5,5,10,20]
输出: true
解释:
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。
示例2:
输入: bills = [5,5,10,10,20]
输出: false
解释:
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。
10.2 思路
创建两个变量，一个记录剩余的5的个数fives，另一个记录10的个数tens。遍历数组，遇到5则fives加1，遇到10则fives减1且tens加1；遇到20时，优先把10找出去，这也就是这一题的贪心点所在，此时先判断，如果fives已经用光了，那么就没法找零直接返回false，然后判断tens的个数，如果有tens，则tens和fives均减1，否则fives减3(注意这里需要先判断fives大于3).
完整代码如下：
Cpp实现
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int fives = 0, tens = 0;
for(int i: bills){
if(i == 5){
++fives;
}else if(i == 10){
--fives;
++tens;
}else{
if(!fives){
return false;
}else if(tens){
--tens;
--fives;
}else if(fives < 3){
return false;
}else{
fives -= 3;
}
}
}
return true;
}
};C实现
bool lemonadeChange(int* bills, int billsSize){
int cash[2];
memset(cash, 0, sizeof(cash));
for(int i = 0; i < billsSize; i++){
if(bills[i] == 5){
cash[0]++;
}else if(bills[i] == 10){
if(cash[0] == 0){
return false;
}
cash[0]--;
cash[1]++;
}else{
if(cash[0] >= 1 && cash[1] >= 1){
cash[0] -= 1;
cash[1] -= 1;
}else if(cash[0] >= 3){
cash[0] -= 3;
}else{
return false;
}
}
}
return true;
}
