做网站前怎么建立数据结构,软件开发流程工具,海兴网站建设,网站建设人员性格455. 分发饼干
1. LeetCode链接
455. 分发饼干 - 力扣#xff08;LeetCode#xff09;
2. 题目描述 3. 解法 贪心法#xff0c;首先想到的是#xff0c;局部最优#xff1a;让每个孩子尽可能拿能拿到的最小饼干尺寸。为了方便查找#xff0c;这就要求至少饼干尺寸是从…455. 分发饼干
1. LeetCode链接
455. 分发饼干 - 力扣LeetCode
2. 题目描述 3. 解法 贪心法首先想到的是局部最优让每个孩子尽可能拿能拿到的最小饼干尺寸。为了方便查找这就要求至少饼干尺寸是从小到大排列的。 两个for循环解决。把小孩按照胃口也从小到大排列更快。
class Solution {
public:int findContentChildren(vectorint g, vectorint s) {vectorbool used(s.size(), false);int sum 0;// sort(g.begin(), g.end());sort(s.begin(), s.end());for (int i 0; i g.size(); i) {for (int j 0; j s.size(); j) {if (used[j]) continue;if (s[j] g[i]) {sum;used[j] true;break;}}}return sum;}
};
但是很明显还是太慢了。 假如说小孩的胃口和饼干的尺寸都从小到大排序。可以着么想。加入某个小孩i和某个饼干j匹配成功了后面一个小孩i1就只能去匹配后面的饼干( j)前面的饼干完全不需要考虑。所以只用一个for循环就可以搞定。 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() index g.size(); i) {if (g[index] s[i]) {index;}}return index;}
};
其中for循环时由饼干的数组控制的原因在于如果当前小孩和饼干不匹配的话即当前饼干不是能满足小孩的最小尺寸饼干应该用下一块饼干去匹配当前小孩。
假如用下一个小孩去匹配当前饼干而在当前小孩都不匹配的情况下下一个胃口更大的小孩更不可能匹配这就导致在一个for循环下找不到任何一对匹配的。
376. 摆动序列
1. LeetCode链接
376. 摆动序列 - 力扣LeetCode
2. 题目描述 3. 解法
贪心局部最优每次找最近的一对相邻的数字且两数之差与上一个不一样。
详细来说摆动序列要求序列数组成上坡——下坡交替状。
而一般的数组在一对上下坡之间要不是有一堆单调坡要不是有平路。
摆动序列即找峰值点旁边的上下坡。 代码解读 首先要找到合适的初值主要是防止前n项都为相同的值。int cha的作用是记录第一对相邻但不相等的差值。找到初值后初始化bool turnturn true表示前一个差值是正数否则是负数。 找到初值并初始化turn后接下来就开始找与上一个差值不同的相邻两数改变turn如此往复。
class Solution {
public:int wiggleMaxLength(vectorint nums) {int cha 0;bool turn true;int len 1;for (int i 1; i nums.size(); i) {if (cha 0 nums[i] - nums[i - 1] ! 0) {cha nums[i] - nums[i - 1];turn (cha 0 ? true : false);len;} else {if ((nums[i] - nums[i - 1] 0 turn false) || (nums[i] - nums[i - 1] 0 turn true)) {len;turn (turn true ? false : true);}}}return len;}
};
53. 最大子数组和
1. LeetCode链接
53. 最大子数组和 - 力扣LeetCode
2. 题目描述 3. 解法
1. 我的解法 首先考虑特殊情况即数组中全是非正数这就成了找最大值的题。 需要遍历一遍遍历完就输出最大值遇到第一个正数则停止。 将第一个正数累加到sum上。 从一个正数的下一个开始开始遇到下一个正数结束为一个阶段。有两种情况1. 该阶段中的负数累加到sum上后的值0则刷新累加和sum和局部累加和sumb。此种情况要记录之前最大的sum2. sumb0则sumb加到累加和上sumb刷新。
比较之前记录的历史最大sum和当前的sum输出较大的一个。
class Solution {
public:int maxSubArray(vectorint nums) {int sum INT_MIN;int i 0;for (; i nums.size(); i) {if (nums[i] 0) break;else if (nums[i] sum) sum nums[i];}if (i nums.size()) return sum;sum nums[i];i;int sumb 0;int max INT_MIN;for (; i nums.size(); i) {if (sum sumb 0) {if (sum nums[i] sum max) max sum; sum 0;sumb 0;}sumb nums[i];if (sumb 0) {sum sumb;sumb 0;}}return sum max ? sum : max;}
};
1. 记录所有可能的连续和为正值的和只保留最大值。
2. 改变连续子区间的起点和终点在子区间累加和0后使子区间累加和0相当于重新设置起点重点是使得累加和0的所有都可以成为终点保留最大子区间和。
class Solution {
public:int maxSubArray(vectorint nums) {int result INT32_MIN;int count 0;for (int i 0; i nums.size(); i) {count nums[i];if (count result) { // 取区间累计的最大值相当于不断确定最大子序终止位置result count;}if (count 0) count 0; // 相当于重置最大子序起始位置因为遇到负数一定是拉低总和}return result;}
};
