--0--
455. 分发饼干
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
int res=0;
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int p1=0,p2=0;
while(p1<g.size() && p2<s.size()) {
if(s[p2]>=g[p1]) {
res++;
p2++;
p1++;
}
else{
p2++;
}
}
return res;
}
};
--1--
376. 摆动序列
出自评论区这位大佬，真的tql%%%
思路其实和下面方法4的状态自动机差不多，但代码就是简洁很多。
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2) {
return n;
}
int up = 1;
int down = 1;
for (int i = 1; i < n; i++) {
if (nums[i] > nums[i - 1]) {
up = down + 1;
}
if (nums[i] < nums[i - 1]) {
down = up + 1;
}
}
return max(up, down);
}
};
--2--
402. 移掉K位数字
稍微思考一下可以发现，因为位数是相同的，所以需要尽量保持高位的数字小，因此出现当前位比下一位大，就把当前位删掉。
因此使用了一个栈结构，但是是用vector来模拟栈，因为vector可以遍历，最后输出字符串更方便。
还有需要注意的是前导0处理，在下面代码中有注释。
class Solution {
public:
string removeKdigits(string num, int k) {
vector<char> s;
string res="";
for(int i=0;i<num.length();i++){
while(s.size()!=0 && s[s.size()-1]>num[i] && k>0){
s.pop_back();
k--;
}
//处理前导0，只有在数字为0而且栈空的情况下，不会push
if(num[i]!='0' || s.size())
s.push_back(num[i]);
}
while(s.size()&&k){
s.pop_back();
k--;
}
for(int i=0;i<s.size();i++)
res+=s[i];
if(res=="") res="0";
return res;
}
};
--3--
55. 跳跃游戏
class Solution {
public:
bool canJump(vector<int>& nums) {
int maxlen=-1;
for(int i=0; i<nums.size(); i++) {
maxlen= max(nums[i]+i,maxlen);
// 把maxlen<=i后面的&&去掉提交一下就知道为啥要加了。。
if(maxlen<=i && !(i==nums.size()-1 && nums[i]==0))
return false;
}
return true;
}
};
--4--
45. 跳跃游戏 II
class Solution {
public:
int jump(vector<int>& nums) {
if(nums.size()<2) return 0;
int res=1;
int current_max_index=nums[0];
int pre_max_index=nums[0];
for(int i=0;i<nums.size();i++){
if(i>current_max_index){
res++;
current_max_index=pre_max_index;
}
pre_max_index=max(pre_max_index,nums[i]+i);
}
return res;
}
};
--5--
452. 用最少数量的箭引爆气球
1.按气球前端排序（逐渐缩小区间的思想）
虽然过了但是很慢QAQ
class Solution {
public:
int findMinArrowShots(vector<vector<int>> &points) {
if (points.size() == 0)
return 0;
sort(points.begin(), points.end(),
[](vector<int> x, vector<int> y) { return x[0] < y[0]; });
int res = 1;
int begin = points[0][0];
int end = points[0][1];
for (int i = 1; i < points.size(); i++) {
if (end >= points[i][0]) {
begin = points[i][0];
end = min(end, points[i][1]);
} else {
res++;
begin = points[i][0];
end = points[i][1];
}
}
return res;
}
};
2.按气球后端排序（大佬思想）
大佬的代码简洁又快QAQ，前面sync_with_stdio那个是关同步，提高cin速度。具体可以参考 解析static auto x = []() { std::ios::sync_with_stdi..._CSDN博客
大佬的代码
static const auto io_sync_off = []()
{
// turn off sync
std::ios::sync_with_stdio(false);
// untie in/out streams
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
int findMinArrowShots(vector<vector<int>>& points) {
if (points.empty()) return 0;
sort(points.begin(), points.end(), [](const auto& l, const auto& r)
{
return l[1] < r[1];
});
int count = 1;
int tail = points[0][1];
for (int i = 1; i < points.size(); i++)
{
if (points[i][0] <= tail) continue;
count += 1;
tail = points[i][1];
}
return count;
}
};
一开始感觉贪心算简单的了。。现在感觉贪心对脑子要求很高QAQ
PAT 1033 To Fill or Not to Fill (25分)
经典贪心，汽车加油问题
