代码随想录算法训练营第31天 | 455.分发饼干、376. 摆动序列、53. 最大子序和
思路:
- 先将饼干和小朋友的胃口排序,遍历饼干,如果饼干能满足该小朋友的胃口就
++ans
我的AC代码
| |
| class Solution { |
| public: |
| int findContentChildren(vector<int>& g, vector<int>& s) { |
| sort(g.begin(), g.end()); |
| sort(s.begin(), s.end()); |
| int ans = 0; |
| for(int j = 0; ans < g.size() && j < s.size(); ++j) { |
| if(s[j] >= g[ans]) { |
| ++ans; |
| } |
| } |
| return ans; |
| } |
| }; |
标准答案
大饼干喂饱大胃口
| |
| class Solution { |
| public: |
| int findContentChildren(vector<int>& g, vector<int>& s) { |
| sort(g.begin(), g.end()); |
| sort(s.begin(), s.end()); |
| int index = s.size() - 1; |
| int result = 0; |
| 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() && g[index] <= s[i]){ |
| index++; |
| } |
| } |
| return index; |
| } |
| }; |
思路:
- 遍历一次数组,记录本次和上一次的差值,若正负号不相同则
cnt++
,若相同或者这两个数字相同则直接跳过,要注意只有差值正负号不同且两个数不相同的时候才要将flag
赋值给pflag
我的AC代码
贪心
| |
| class Solution { |
| public: |
| int wiggleMaxLength(vector<int>& nums) { |
| int pflag = 0; |
| int flag = 1; |
| int ans = 1; |
| int cnt = 1; |
| for(int i = 1; i < nums.size(); ++i) { |
| if(nums[i] - nums[i - 1] > 0) { |
| flag = 1; |
| } |
| else if(nums[i] - nums[i - 1] < 0) { |
| flag = -1; |
| } |
| else { |
| flag = 0; |
| } |
| if(flag != pflag && flag != 0) { |
| pflag = flag; |
| cnt++; |
| if(cnt > ans) { |
| ans = cnt; |
| } |
| } |
| } |
| return ans; |
| } |
| }; |
标准答案
贪心
| |
| class Solution { |
| public: |
| int wiggleMaxLength(vector<int>& nums) { |
| if (nums.size() <= 1) return nums.size(); |
| int curDiff = 0; |
| int preDiff = 0; |
| int result = 1; |
| for (int i = 0; i < nums.size() - 1; i++) { |
| curDiff = nums[i + 1] - nums[i]; |
| |
| if ((curDiff > 0 && preDiff <= 0) || (preDiff >= 0 && curDiff < 0)) { |
| result++; |
| preDiff = curDiff; |
| } |
| } |
| return result; |
| } |
| }; |
动态规划
| |
| class Solution { |
| public: |
| int dp[1005][2]; |
| int wiggleMaxLength(vector<int>& nums) { |
| memset(dp, 0, sizeof dp); |
| dp[0][0] = dp[0][1] = 1; |
| |
| for (int i = 1; i < nums.size(); ++i) |
| { |
| dp[i][0] = dp[i][1] = 1; |
| |
| for (int j = 0; j < i; ++j) |
| { |
| if (nums[j] > nums[i]) dp[i][1] = max(dp[i][1], dp[j][0] + 1); |
| } |
| |
| for (int j = 0; j < i; ++j) |
| { |
| if (nums[j] < nums[i]) dp[i][0] = max(dp[i][0], dp[j][1] + 1); |
| } |
| } |
| return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]); |
| } |
| }; |
线段树
思路:
- 一直累加数组中每个数的值,当值大于
ans
时更新ans
,当值小于0时直接重置为0(相当于从这个使累加值小于0的值这里跳过,从下一个值开始重新计算子序列和)
我的AC代码
贪心
| |
| class Solution { |
| public: |
| int maxSubArray(vector<int>& nums) { |
| int ans = INT_MIN; |
| int cnt = 0; |
| for(int i = 0; i < nums.size(); ++i) { |
| cnt += nums[i]; |
| if(cnt > ans) { |
| ans = cnt; |
| } |
| if(cnt < 0) { |
| cnt = 0; |
| } |
| } |
| return ans; |
| } |
| }; |
标准答案
贪心
| |
| class Solution { |
| public: |
| int maxSubArray(vector<int>& 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; |
| } |
| }; |
动态规划
| |
| class Solution { |
| public: |
| int maxSubArray(vector<int>& nums) { |
| if (nums.size() == 0) return 0; |
| vector<int> dp(nums.size(), 0); |
| dp[0] = nums[0]; |
| int result = dp[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; |
| } |
| }; |
Comments NOTHING