leetcode刷题Day01
贪心算法：
1.什么是贪心算法？
贪心的本质是选择每一阶段的局部最优解，从而达到全局最优
2.什么样的题目是贪心？
一般是找出局部最优解，并可以推出全局最优解
445.分发饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
示例 1:
1
2
3
4
5
6
| 输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
|
示例 2:
1
2
3
4
5
6
| 输入: g = [1,2], s = [1,2,3]
输出: 2
解释:
你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出2.
|
提示：
1 <= g.length <= 3 * 104
0 <= s.length <= 3 * 104
1 <= g[i], s[j] <= 231 - 1
解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(s.begin(),s.end());
sort(g.begin(),g.end());
int j=0;
int count=0;
for(int i=0;i<g.size();i++)
{
while(j<s.size()&&g[i]>s[j])
{
j++;
}
if(j<s.size())
{
j++;
count++;
}
else
break;
}
return count;
}
};
|
376.摆动序列
如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。少于两个元素的序列也是摆动序列。
例如， [1,7,4,9,2,5] 是一个摆动序列，因为差值 (6,-3,5,-7,3) 是正负交替出现的。相反, [1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。
示例 1:
1
2
3
| 输入: [1,7,4,9,2,5]
输出: 6
解释: 整个序列均为摆动序列。
|
示例 2:
1
2
3
| 输入: [1,17,5,10,13,15,10,5,16,8]
输出: 7
解释: 这个序列包含几个长度为 7 摆动序列，其中一个可为[1,17,10,13,10,16,8]。
|
示例 3:
1
2
| 输入: [1,2,3,4,5,6,7,8,9]
输出: 2
|
进阶:
你能否用 O(n) 时间复杂度完成此题?
解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if(nums.size()<2)
return nums.size();
int result=1;
int cur;
int pre=0;
for(int i=0;i<nums.size()-1;i++)
{
cur=nums[i+1]-nums[i];
if((cur>0&&pre<=0)||(cur<0&&pre>=0))
{
result++;
pre=cur;
}
}
return result;
}
};
|
53.最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
1
2
3
4
5
| 示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
|
1
2
3
4
| 示例 2：
输入：nums = [1]
输出：1
|
1
2
3
4
| 示例 3：
输入：nums = [0]
输出：0
|
1
2
3
4
| 示例 4：
输入：nums = [-1]
输出：-1
|
1
2
3
4
| 示例 5：
输入：nums = [-100000]
输出：-100000
|
提示：
1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
方法一：暴力求解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum=INT32_MIN;
int count;
for(int i=0;i<nums.size();i++)
{
count=0;
for(int j=i;j<nums.size();j++)
{
count+=nums[j];
sum=sum>count?sum:count;
}
}
return sum;
}
};
|
方法二：贪心法
重点！！！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum=INT32_MIN;
int count=0;
for(int i=0;i<nums.size();i++)
{
count+=nums[i];
sum=sum>count?sum:count;
if(count<0)
count=0;
}
return sum;
}
};
|
方法三：动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int maxSubArray(vector<int>&nums) {
if (nums.size() ==0) return0;
vector<int>dp(nums.size(), 0);
dp[0] =nums[0];
int result=dp[0];
for (inti=1; i<nums.size(); i++) {
dp[i] =max(dp[i-1] +nums[i], nums[i]);
if (dp[i] >result) result=dp[i];
}
return result;
}
};
|
