社团网站建设的功能定位,wordpress dux搜索无法使用,哈市建设网站,湖南土建网贪心算法
当前取最优#xff0c;最终完成全局最优1、买卖股票的最佳时机
#xff08;1#xff09;题目描述以及输入输出
(1)题目描述:
给定一个数组 prices #xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。(2)输入输出描述#xff1a;
输入最终完成全局最优1、买卖股票的最佳时机
1题目描述以及输入输出
(1)题目描述:
给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。(2)输入输出描述
输入[7,1,5,3,6,4]
输出5关键思路
遍历价格
取当前价格和最低价格的最小值
当前价格-最低价格取最大2代码块
class Solution {
public:int maxProfit(vectorint prices) {int cost INT_MAX; // 取当前价格和最低价格的最小值int profit 0; // 当前价格-最低价格取最大for(int price:prices){cost min(cost,price);profit max(profit,price-cost);}return profit;}
};2、跳跃游戏
1题目描述以及输入输出
(1)题目描述:
给你一个非负整数数组 nums 你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标如果可以返回 true 否则返回 false 。(2)输入输出描述
输入nums [2,3,1,1,4]
输出true关键思路
遍历数组
当前距离超过最大可达距离不合理
计算从当前可达的最大距离2代码块
class Solution {
public:bool canJump(vectorint nums) {int max_jump 0;for(int i 0;inums.size();i){if(imax_jump)return false; // 当前距离超过最大可达距离不合理max_jump (max_jump,inums[i]);// 计算从当前可达的最大距离}return true;}
};3、跳跃游戏||
1题目描述以及输入输出
(1)题目描述:
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。(2)输入输出描述
输入: nums [2,3,1,1,4]
输出: 2关键思路
遍历数组
计算从当前可达的最大距离
到达上次最远可达距离时更新接下来的最大可达距离并且更新跳跃步数2代码块
class Solution {
public:int jump(vectorint nums) {int maxpos 0; // 记录当前最远可达位置int end 0; // 记录上次跳跃末端int num 0; // 记录跳跃步数for(int i 0;inums.size()-1;i){maxpos max(maxpos,nums[i]i); // 当前走过的最大可达距离if(i end) // 到达上次跳跃的最远距离需要下次跳跃{end maxpos;num;}}return num;}
};4、划分字母区间
1题目描述以及输入输出
(1)题目描述:
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。
注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。(2)输入输出描述
输入s ababcbacadefegdehijhklij
输出[9,7,8]关键思路
定义哈希数组记录元素最远出现位置
遍历字符在哈希表中查找字符出现的最远位置假如到最远位置2代码块
class Solution {
public:vectorint partitionLabels(string s) {vectorint result;int record[26] {0};for(int i 0;is.size();i){record[s[i]-a] i; // 记录该字母出现的最后位置}int left 0,right 0;for(int i 0;is.size();i){right max(right,record[s[i] - a]); // 更新当前遍历的最远可达距离if(i right) // 到达当前位置的最右边界{result.push_back(right - left 1);left i 1;}}return result;}
};
