贪心算法
贪心的本质是选择每一阶段的局部最优，从而达到全局最优
455. 分发饼干
题目难度： 简单 用时： 5 分钟 标记： 完成
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
int child = 0,chose = 0;
std::sort(g.begin(), g.end());
std::sort(s.begin(), s.end());
while (chose < s.size() && child < g.size())
{
if (s[chose]>=g[child])child++;
chose++;
}
return child;
}
};
376. 摆动序列
题目难度： 中等 用时： 15 分钟 标记： 未完成
此题可当作搜索题，满足条件+1即可，不要想复杂了
//376. 摆动序列
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if (nums.size()<2) return nums.size();
int max_count = 1; //记录最大值
int cur =0;
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) //如果左升右降或者做左降右升则为满足，注意等号
{
max_count++;
pre = cur; //写到里面，表示贪心，
}
}
return max_count;
}
};
53. 最大子数组和
题目难度： 中等 用时： 17 分钟 标记： 未完成
//如果sum < 0了说明该给sum赋值了0
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxsum = INT32_MIN;
int sum = 0;
for (int i = 0; i < nums.size(); ++i) {
sum+=nums[i];
if (sum > maxsum) maxsum=sum;
if(sum<=0) sum=0; //sum
}
return maxsum;
}
};
122. 买卖股票的最佳时机 II
题目难度： 中等 用时： 2 分钟 标记： 完成
//solution2 -- 只收集上升的一段
class Solution {
public:
int maxProfit(vector<int>& prices) {
int res = 0;
for (int i = 1; i < prices.size(); ++i) {
res+= max(prices[i]-prices[i-1],0);
}
return res;
}
};
55. 跳跃游戏
题目难度： 中等 用时： 22 分钟 标记： 完成
class Solution {
public:
bool canJump(vector<int>& nums) {
int cover = 0; //定义覆盖范围
if (nums.size() == 1)return true;
for (int i = 0; i <= cover; ++i) {
cover = max(cover,i + nums[i]);//更新覆盖范围
if (cover >= nums.size() -1) return true;//达到覆盖范围则return
}
return false;
}
};
45. 跳跃游戏 II
题目难度： 中等 用时： 8 分钟 标记： 完成
class Solution {
public:
int jump(vector<int>& nums) {
if (nums.size() < 2 ) return 0;
int count = 0,index = 0;
while (index + nums[index] < nums.size() -1 && nums[index]!= 0) //判断循环退出条件，到达最后一个或者跳到0时候退出
{
int max_index = 1,maxc = nums[index];
for (int i = 1; i <= nums[index]; ++i) {
if (maxc <= nums[index+i] + i)
{
maxc = nums[index+i] + i;
max_index = i;
}
}
index+=max_index;
count++;
//cout << nums[index] <<endl;
}
if (index == nums.size() -1) return count;
count++;
return count;
}
};
1005. K 次取反后最大化的数组和
题目难度： 简单 用时： 8 分钟 标记： 完成
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
std::sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() && k && nums[i] < 0; ++i,k--) {
if (nums[i] < 0)nums[i] = -nums[i];
}
//找到最小值与和
int mins = nums[0];
int sum = 0;
for (int i = 0; i < nums.size(); ++i) {
sum+=nums[i];
mins = min(mins,nums[i]);
}
if (k % 2 == 0) return sum;
else return sum - 2 * mins;
}
};
134. 加油站
题目难度： 中等 用时： 30 分钟 标记： 未完成
可以换一个思路，首先如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
每个加油站的剩余量rest[i]为gas[i] - cost[i]。
i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，因为这个区间选择任何一个位置作为起点，到i这里都会断油，那么起始位置从i+1算起，再从0计算curSum。
//134. 加油站
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int curSum = 0;
int totalSum = 0;
int start = 0;
for (int i = 0; i < gas.size(); i++) {
curSum += gas[i] - cost[i];
totalSum += gas[i] - cost[i];
if (curSum < 0) { // 当前累加rest[i]和 curSum一旦小于0
start = i + 1; // 起始位置更新为i+1
curSum = 0; // curSum从0开始
}
}
if (totalSum < 0) return -1; // 说明怎么走都不可能跑一圈了
return start;
}
};
135. 分发糖果
题目难度： 困难 用时： 30 分钟 标记： 未完成
//135. 分发糖果
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> candyVec(ratings.size(), 1);
// 从前向后->需要累加
for (int i = 1; i < ratings.size(); ++i) {
if (ratings[i-1] < ratings[i])candyVec[i] = candyVec[i-1]+1;
}
// 从后向前->倒数第二个开始，比价自己和右边的值
for (int i = ratings.size()-2; i >=0; --i) {
if (ratings[i+1] < ratings[i]) candyVec[i] = max(candyVec[i+1]+1,candyVec[i]);
}
return accumulate(candyVec.begin(),candyVec.end(),0);
}
};
860. 柠檬水找零
题目难度： 简单 用时： 8 分钟 标记： 完成
class Solution {
int pays[2] = {0,0};
public:
bool lemonadeChange(vector<int>& bills) {
for (int i = 0; i < bills.size(); ++i) {
if (bills[i] == 5)pays[0]++; //5块
else if (bills[i] == 10)//十块
{
pays[0]--;
pays[1]++;
} else if (bills[i] == 20)//二十块
{
//有10快的先拿10块
if (pays[1] && pays[0])
{
pays[1]--;
pays[0]--;
} else pays[0] = pays[0] - 3;
}
if (pays[0]< 0 ) return false;
}
return true;
}
};
406. 根据身高重建队列
题目难度： 中等 用时： 30 分钟 标记： 未完成
本题有两个维度，h和k，看到这种题目一定要想如何确定一个维度，然后再按照另一个维度重新排列。
那么按照身高h来排序呢，身高一定是从大到小排（身高相同的话则k小的站前面），让高个子在前面。
此时我们可以确定一个维度了，就是身高，前面的节点一定都比本节点高！
那么只需要按照k为下标重新插入队列就可以了
class Solution {
static bool cmp(vector<int>&a,vector<int>&b)
{
if (a[0] == b[0]) return a[1] < b[1];//身高相同 次数从小到大
return a[0] > b[0]; //按照身高从大到小排序
}
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
std::sort(people.begin(), people.end(), cmp);
vector<vector<int>> que;
for (int i = 0; i < people.size(); ++i) {
que.insert(que.begin()+people[i][1],people[i]);
}
return que;
}
};
646. 最长数对链
class Solution {
static bool cmp(const vector<int> &a ,const vector<int> &b )
{
if (a[1] == b[1]) return a[0] < b[0];
return a[1] < b[1];
}
public:
int findLongestChain(vector<vector<int>>& pairs) {
if (pairs.size() < 2) return pairs.size();
std::sort(pairs.begin(), pairs.end(),cmp);
int sum = 1;
for (int i = 1; i < pairs.size(); ++i) {
if (pairs[i-1][1] < pairs[i][0]) sum++;
else pairs[i][1] = pairs[i-1][1];
}
return sum;
}
};
452. 用最少数量的箭引爆气球
题目难度： 中等 用时： 18 分钟 标记： 完成
//452. 用最少数量的箭引爆气球
//注意用static bool cmp速度比 class 快很多
class Solution {
static bool cmp(const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
}
public:
int findMinArrowShots(vector<vector<int>>& points) {
if (points.size() < 2) return points.size();
std::sort(points.begin(), points.end(),cmp);
int count = 1;
int left =points[0][0] ,right=points[0][1];
for (int i = 1; i < points.size(); ++i) {
if (right < points[i][0])
{
count++;
right=points[i][1];
} else right= min(points[i][1],right);
}
return count;
}
};
//二
class Solution {
private:
static bool cmp(const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
}
public:
int findMinArrowShots(vector<vector<int>>& points) {
if (points.size() == 0) return 0;
sort(points.begin(), points.end(), cmp);
int result = 1; // points 不为空至少需要一支箭
for (int i = 1; i < points.size(); i++) {
if (points[i][0] > points[i - 1][1]) { // 气球i和气球i-1不挨着，注意这里不是>=
result++; // 需要一支箭
}
else { // 气球i和气球i-1挨着
points[i][1] = min(points[i - 1][1], points[i][1]); // 更新重叠气球最小右边界
}
}
return result;
}
};
435. 无重叠区间
题目难度： 中等 用时： 8 分钟 标记： 完成
//435. 无重叠区间
class Solution {
static bool cmp(const vector<int>& a, const vector<int>& b) {
if (a[1] == b[1]) return a[0]<b[0];
return a[1] < b[1];
}
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if(intervals.size() < 2) return 0;
std::sort(intervals.begin(), intervals.end(), cmp);
int count = 0;
for (int i = 1; i < intervals.size(); ++i) {
if (intervals[i][0] < intervals[i - 1][1])
{
count++;
intervals[i][1] = intervals[i - 1][1];
}
}
return count;
}
};
763. 划分字母区间
题目难度： 中等 用时： 8 分钟 标记： 完成
这道题关键就是将找到各个字母最后出现的位置，判断当前max是不是在最后出现的位置内
class Solution {
public:
vector<int> partitionLabels(string s) {
unordered_map<char,int> umap;
//找到元素最后出现的位置
for (int i = 0; i < s.size(); ++i) {
if (umap.find(s[i])==umap.end())
{
umap[s[i]] = s.rfind(s[i]);
}
}
int maxpo = 0;
int pre = -1; //起始元素
vector<int> res;
for (int i = 0; i < s.size(); ++i) {
maxpo = max(umap[s[i]],maxpo);
if (i == maxpo)
{
res.push_back(i - pre);
pre = i;
}
}
return res;
}
};
56. 合并区间
题目难度： 中等 用时： 9 分钟 标记： 完成
class Solution {
static bool cmp(const vector<int>& a, const vector<int>& b) {
return a[0] < b[0];
}
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.size() < 2) return intervals;
intervals.push_back({INT_MAX,INT_MAX});
std::sort(intervals.begin(), intervals.end(), cmp);
vector<vector<int>> res;
int left = intervals[0][0],right = intervals[0][1];
for (int i = 1; i < intervals.size(); ++i) {
if (right < intervals[i][0])
{
res.push_back({left,right});
left = intervals[i][0];
right = intervals[i][1];
} else
{
left = min(intervals[i][0],left);
right = max(intervals[i][1],right);
}
}
return res;
}
};
738. 单调递增的数字
题目难度： 中等 用时： 15 分钟 标记： 完成
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string s = to_string(n);
//左到右
for (int i = s.size() - 1; i > 0; --i) {
if (s[i - 1] > s[i])
{
s[i] = '9';
s[i-1]--;
}
}
//右到左
s = to_string(stoi(s));
for (int i = 0; i < s.size() - 1; ++i) {
if (s[i +1] < s[i])
{
s[i+1] = '9';
}
}
return stoi(s);
}
};
968. 监控二叉树
题目难度： 困难 用时： 15 分钟 标记： 未完成
class Solution {
int count = 0;
int fo(TreeNode* root)
{
if (root == NULL) return 2;//空节点为覆盖状态
int r = fo(root->left);
int l = fo(root->right);
if (r == 0 || l == 0)
{
count++;
return 1;
}
if (r == 2 && l == 2) return 0;
return 2;
}
public:
int minCameraCover(TreeNode* root) {
if(fo(root) == 0) count++;
return count;
}
};
1221. 分割平衡字符串
题目难度： 简单 用时： 10分钟 标记： 完成
class Solution {
public:
int balancedStringSplit(string s) {
int R = 0 , L = 0;
int sum = 0;
for (int i = 0; i < s.size(); ++i) {
if (s[i] == 'L') L++;
else R++;
if (R!=0 && R==L )
{
R = 0 , L = 0;
sum++;
}
}
return sum;
}
};
力扣题101
605. 种花问题
题目难度： 简单 用时： 15分钟 标记： 完成
class Solution {
bool manzu(vector<int>& flowerbed,int i)
{
if (flowerbed[i] == 1) return false;
if (flowerbed.size() == 1) return true;
if (i == 0 && flowerbed[i+1] == 1) return false;
if (i == flowerbed.size() - 1 && flowerbed[i-1] == 1) return false;
if (i > 0 && i < flowerbed.size() - 1 && (flowerbed[i-1] == 1 || flowerbed[i+1] == 1)) return false;
return true;
}
public:
bool canPlaceFlowers(vector<int>& flowerbed, int n) {
int count = 0;
for (int i = 0; i < flowerbed.size(); ++i) {
if (manzu(flowerbed,i))
{
flowerbed[i] = 1;
count++;
}
}
return count >= n;
}
};
665. 非递减数列
题目难度： 中等 用时： 15分钟 标记： 完成
class Solution {
public:
bool checkPossibility(vector<int>& nums) {
int count = 0;
for (int i = 1; i < nums.size(); ++i) {
if(nums[i] < nums[i - 1] )
{
count++;
//i 就是要被删除的
if (i > 0 && i < nums.size() - 1 && nums[i - 1] <= nums[i + 1] || i == nums.size() - 1)
{
nums[i] = nums[i - 1];
continue;
}
//i的前一个要被删除
int j = i - 2;
while (j >= 0)
{
if (nums[j] > nums[i]) return false;
j--;
}
}
}
return count <= 1;
}
};
870. 优势洗牌（思路没问题测试不给过）
class Solution {
public:
vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
map<int,int> umap;
for (int i = 0; i < nums1.size(); ++i) umap[nums1[i]]++;
vector<int>res;
for (int i = 0; i < nums2.size(); ++i) {
bool find = false;
int a = -1;
for (auto &x:umap) {
if (x.first > nums2[i] && umap[x.first] > 0)
{
find = true;
res.push_back(x.first);
x.second--;
if(x.second== 0)a = x.first;
break;
}
}
if(a != -1) umap.erase(a);
if (!find)
{
res.push_back(umap.begin()->first);
if(--umap[umap.begin()->first] == 0) umap.erase(umap[umap.begin()->first]);
}
}
return res;
}
};