淘宝购物返利网站开发,satellite7 wordpress,做网站招聘的职业顾问,微信小程序注册账号目录
一、理论基础
1. 大纲
2. 求解步骤
二、Leetcode 题目
1. 分发饼干
2. 摆动序列
3. 最大子序和
4. 买卖股票的最佳时机 II
5. 跳跃游戏
6. 跳跃游戏 II
7. K 次取反后最大化的数组和
8. 加油站
9. 分发糖果 一、理论基础
1. 大纲 2. 求解步骤
将问题分解为…目录
一、理论基础
1. 大纲
2. 求解步骤
二、Leetcode 题目
1. 分发饼干
2. 摆动序列
3. 最大子序和
4. 买卖股票的最佳时机 II
5. 跳跃游戏
6. 跳跃游戏 II
7. K 次取反后最大化的数组和
8. 加油站
9. 分发糖果 一、理论基础
1. 大纲 2. 求解步骤
将问题分解为若干个子问题。找出适合的贪心策略。求解每一个子问题的最优解。将局部最优解堆叠成全局最优解。 二、Leetcode 题目
1. 分发饼干
https://leetcode.cn/problems/assign-cookies/description/https://leetcode.cn/problems/assign-cookies/description/ 假设你是一位很棒的家长想要给你的孩子们一些小饼干。但是每个孩子最多只能给一块饼干。 对每个孩子 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。
// 方法一大饼干喂饱大胃口
class Solution {
public:int findContentChildren(vectorint g, vectorint s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int result 0;int index s.size() - 1; // 饼干for (int i g.size() - 1; i 0; i--) { // 遍历胃口if (index 0 s[index] g[i]) {result;index--;}}return result;}
};// 方法二小饼干喂饱小胃口
class Solution {
public:int findContentChildren(vectorint g, vectorint s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int index 0;for (int i 0; i s.size(); i) {if (index g.size() s[i] g[index]) {index;}}return index;}
}; 2. 摆动序列
https://leetcode.cn/problems/wiggle-subsequence/description/https://leetcode.cn/problems/wiggle-subsequence/description/ 如果连续数字之间的差严格地在正数和负数之间交替则数字序列称为 摆动序列 。第一个差如果存在的话可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。 例如 [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 思路 本题要考虑三种情况 情况一上下坡中有平坡 情况二数组首尾两端 情况三单调坡度有平坡 class Solution {
public:int wiggleMaxLength(vectorint nums) {int prenum 0;int curnum 0;int result 1;for (int i 1; i nums.size(); i) {curnum nums[i] - nums[i - 1];if ((prenum 0 curnum 0) || (prenum 0 curnum 0)) {result;prenum curnum;}}return result;}
}; 3. 最大子序和
https://leetcode.cn/problems/maximum-subarray/description/https://leetcode.cn/problems/maximum-subarray/description/ 给你一个整数数组 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
// 写法一
class Solution {
public:int maxSubArray(vectorint nums) {if (nums.size() 0) return 0;vectorint dp(nums.size());dp[0] nums[0];int result nums[0];for (int i 1; i nums.size(); i) {// 有两种情况// 第一种延续之前的累加第二种从当前数字进行累加。dp[i] max(dp[i - 1] nums[i], nums[i]);if (dp[i] result) result dp[i];}return result;}
};// 写法二
class Solution {
public:int maxSubArray(vectorint nums) {vectorint dp(nums.size(), INT_MIN);dp[0] nums[0];int result nums[0];for (int i 1; i nums.size(); i) {dp[i] max(nums[i], nums[i] dp[i - 1]);result result dp[i] ? result : dp[i];}return result;}
};
4. 买卖股票的最佳时机 II
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/submissions/570926047/https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/submissions/570926047/ 给你一个整数数组 prices 其中 prices[i] 表示某支股票第 i 天的价格。 在每一天你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买然后在 同一天 出售。 返回 你能获得的 最大 利润 。 示例 1
输入prices [7,1,5,3,6,4]
输出7
解释在第 2 天股票价格 1的时候买入在第 3 天股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4。
随后在第 4 天股票价格 3的时候买入在第 5 天股票价格 6的时候卖出, 这笔交易所能获得利润 6 - 3 3。
最大总利润为 4 3 7 。示例 2
输入prices [1,2,3,4,5]
输出4
解释在第 1 天股票价格 1的时候买入在第 5 天 股票价格 5的时候卖出, 这笔交易所能获得利润 5 - 1 4。
最大总利润为 4 。示例 3
输入prices [7,6,4,3,1]
输出0
解释在这种情况下, 交易无法获得正利润所以不参与交易可以获得最大利润最大利润为 0。
class Solution {
public:int maxProfit(vectorint prices) {int result 0;for (int i 1; i prices.size(); i) {result max(prices[i] - prices[i - 1], 0);}return result;}
}; 5. 跳跃游戏
https://leetcode.cn/problems/jump-game/description/https://leetcode.cn/problems/jump-game/description/ 给你一个非负整数数组 nums 你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标如果可以返回 true 否则返回 false 。 示例 1
输入nums [2,3,1,1,4]
输出true
解释可以先跳 1 步从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。示例 2
输入nums [3,2,1,0,4]
输出false
解释无论怎样总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 所以永远不可能到达最后一个下标。
class Solution {
public:bool canJump(vectorint nums) {if (nums.size() 1) return true;int cover 0;for (int i 0; i cover; i) {cover max(cover, i nums[i]);if (cover nums.size() - 1) return true;}return false;}
}; 6. 跳跃游戏 II
https://leetcode.cn/problems/jump-game-ii/description/https://leetcode.cn/problems/jump-game-ii/description/ 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说如果你在 nums[i] 处你可以跳转到任意 nums[i j] 处: 0 j nums[i] i j n 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。 示例 1:
输入: nums [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置跳 1 步然后跳 3 步到达数组的最后一个位置。示例 2:
输入: nums [2,3,0,1,4]
输出: 2
class Solution {
public:int jump(vectorint nums) {int curDistance 0; // 当前覆盖的最远距离下标int result 0; // 记录走的最大步数int nextDistance 0; // 下一步覆盖的最远距离下标for (int i 0; i nums.size() - 1; i) {nextDistance max(nums[i] i, nextDistance);if (i curDistance) { // 可以到达当前覆盖最远距离则表示可以到达最后一位curDistance nextDistance;result;}}return result;}
}; 7. K 次取反后最大化的数组和
https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/ 给你一个整数数组 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] 。 思路 解题步骤为 第一步将数组按照绝对值大小从大到小排序注意要按照绝对值的大小。第二步从前向后遍历遇到负数将其变为正数同时K--。第三步如果K还大于0那么反复转变数值最小的元素将K用完。第四步求和。 class Solution {
public:static bool cmp(int a, int b) {return abs(a) abs(b);}int largestSumAfterKNegations(vectorint nums, int k) {sort(nums.begin(), nums.end(), cmp);int result 0;for (int i 0; i nums.size() k; i) {if (nums[i] 0) {nums[i] * -1;k--;}}if (k % 2 1) { // 只运行一遍就可以nums[nums.size() - 1] * -1;}for (int a : nums) result a;return result;}
};
8. 加油站
https://leetcode.cn/problems/gas-station/description/https://leetcode.cn/problems/gas-station/description/ 在一条环路上有 n 个加油站其中第 i 个加油站有汽油 gas[i] 升。 你有一辆油箱容量无限的的汽车从第 i 个加油站开往第 i1 个加油站需要消耗汽油 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 升汽油。
因此无论怎样你都不可能绕环路行驶一周。
class Solution {
public:int canCompleteCircuit(vectorint gas, vectorint cost) {int curSum 0;int totalSum 0;int start 0;for (int i 0; i gas.size(); i) {curSum gas[i] - cost[i];totalSum gas[i] - cost[i];if (curSum 0) { // 当前累加rest[i]和 curSum一旦小于 0start i 1; // 起始位置更新为i1curSum 0; // curSum从0开始}}if (totalSum 0) return -1; // 说明怎么走都不可能跑一圈了return start;}
}; 9. 分发糖果
https://leetcode.cn/problems/candy/description/https://leetcode.cn/problems/candy/description/ n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。 你需要按照以下要求给这些孩子分发糖果 每个孩子至少分配到 1 个糖果。相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子分发糖果计算并返回需要准备的 最少糖果数目 。 示例 1
输入ratings [1,0,2]
输出5
解释你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。示例 2
输入ratings [1,2,2]
输出4
解释你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果这满足题面中的两个条件。
class Solution {
public:int candy(vectorint ratings) {// 先从左向右判断再从右向左判断vectorint candyVec(ratings.size(), 1);for (int i 1; i ratings.size(); i) {if (ratings[i] ratings[i - 1]) {candyVec[i] candyVec[i - 1] 1;}}for (int i ratings.size() - 2; i 0; i--) {if (ratings[i] ratings[i 1]) {candyVec[i] max(candyVec[i], candyVec[i 1] 1);}}int result 0;for (int sum : candyVec) result sum;return result;}
};
