当前位置：首页 > news >正文

石家庄网站制作模板北京云网站建设

news 2025/11/7 2:31:01

石家庄网站制作模板,北京云网站建设,南海做网站公司,网站开发案例目录一、理论基础 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(vector<int>& g, vector<int>& 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(vector<int>& g, vector<int>& 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(vector<int>& 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(vector<int>& nums) {if (nums.size() == 0) return 0;vector<int> 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(vector<int>& nums) {vector<int> 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(vector<int>& 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(vector<int>& 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(vector<int>& 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(vector<int>& 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 个加油站开往第 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 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& 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;  // 起始位置更新为i+1curSum = 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(vector<int>& ratings) {// 先从左向右判断，再从右向左判断vector<int> 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;}
};