刷题记录
- 455. 分发饼干
- *376. 摆动序列
- 53. 最大子数组和
455. 分发饼干
leetcode题目地址
贪心,两个数组排序,从前向后或从后向前均可,二者需保持同序,使用两个指针分别指向两个数组,当胃口满足时两个指针同时后移并计数,若不满足则饼干指针后移寻找合适的饼干。
由于使用了两次快排,所以时间复杂度为O(nlogn)。
时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
空间复杂度: O ( 1 ) O(1) O(1)
// c++
class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(), g.end());sort(s.begin(), s.end());int cnt=0;int i=0, j=0;while(i<g.size() && j<s.size()){if(j<s.size() && s[j]>=g[i]) { // 满足胃口cnt++;i++;}// 不管是否满足胃口 饼干都后移// 1. 满足胃口 当前饼干已使用 所以后移// 2. 不满足胃口 当前饼干小于当前胃口 后移找符合胃口的饼干j++;}return cnt;}
};
*376. 摆动序列
leetcode题目地址
保证前后差值一正一负即可。
有一个问题还没搞清楚,如果使用当前子序列的最后一个元素和当前元素求差(代码中注释掉的写法)则会不通过,这里没有搞清楚是什么原因。。。
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)
// c++
class Solution {
public:int wiggleMaxLength(vector<int>& nums) {bool flag = true;if(nums.size()<2) return nums.size();// int pre = nums[0];int prediff = 0;int curdiff = 0;int cnt = 1;for(int i=1; i<nums.size(); i++){// curdiff = nums[i] - pre;curdiff = nums[i] - nums[i-1];if(curdiff==0) continue;if((prediff>=0&&curdiff<0)||(prediff<=0&&curdiff>0)){cnt++;// pre = nums[i];prediff = curdiff;}}return cnt;}
};
53. 最大子数组和
leetcode题目地址
贪心策略,只要当前和为负就舍弃,因为负数再加后边的数只会让后边的和变小。
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( 1 ) O(1) O(1)
// c++
class Solution {
public:int maxSubArray(vector<int>& nums) {int sum=0;int maxsum=nums[0];for(int i=0; i<nums.size(); i++){sum+=nums[i];if(sum>maxsum) maxsum=sum;if(sum<0) sum=0;}return maxsum;}
};