Solution 1: #Greedy, 先满足胃口小的
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() && s[i] >= g[index]) index++;
}
return index;
}
};Solution 2: #Greedy， 先满足胃口大的
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 && g[i] <= s[index]){
result++;
index--;
}
}
return result;
}
};Solution 1: #Greedy
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if(nums.size() <= 1) return nums.size();
int prediff = 0;
int curdiff = 0;
int count = 1;
for(int i = 0; i < nums.size() - 1; i++){
int curdiff = nums[i + 1] - nums[i];
// 记录坡度改变的情况
if((prediff <= 0 && curdiff > 0) || (prediff >= 0 && curdiff < 0)){
prediff = curdiff;
count++;
}
}
return count;
}
};Solution 2: 📉统计波峰波谷轮番出现的次数
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int peak = 1;
int valley = 1;
for(int i = 1; i < nums.size(); i++){
if(nums[i] > nums[i - 1]) peak = valley + 1;
else if(nums[i] < nums[i - 1]) valley = peak + 1;
}
return max(peak, valley);
}
};Solution 1: #Greedy
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int curSum = 0;
int maxSum = INT_MIN;
for(auto x : nums){
curSum += x;
if(curSum < x) curSum = x;
if(curSum > maxSum) maxSum = curSum;
}
return maxSum;
}
};Solution 2: #Dynamic Programming
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 0); // dp[i]表示从其实位置到当前位置的最大子数组和
dp[0] = nums[0];
int maxSum = dp[0];
for(int i = 1; i < n; i++){
dp[i] = max(dp[i - 1] + nums[i], nums[i]);
maxSum = max(dp[i], maxSum);
}
return maxSum;
}
};122. Best Time to Buy and Sell Stock II
Solution 1: #Greedy, 策略就是收集每天的正差价
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<int> gap;
gap.push_back(0);
int profit = 0;
for(int i = 1; i < prices.size(); i++){
gap.push_back(prices[i] - prices[i - 1]);
}
for(auto x : gap){
profit += ( x > 0 ? x : 0);
}
return profit;
}
};Solution 2: #Dynamic Programming
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(2, 0));
dp[0][0] = -prices[0]; // have the stock on the day 0;
dp[0][1] = 0; // don't have the stock on the day 0;
for(int i = 1; i < prices.size(); i++){
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
}
return dp[n - 1][1]; // don't have the stock on the day n - 1
}
};Solution 1: #Greedy
class Solution {
public:
bool canJump(vector<int>& nums) {
if(nums.size() == 1) return true;
int cover = 0;
for(int i = 0; i <= cover; i++){
cover = max(i + nums[i], cover);
if(cover >= nums.size() - 1) return true;
}
return false;
}
};Solution 2: 不断回退，检查能否到0
class Solution {
public:
bool canJump(vector<int>& nums) {
int targetNumIndex = nums.size() - 1;
for(int i = nums.size() - 2; i >= 0; i--){
if(targetNumIndex <= i + nums[i]){
targetNumIndex = i;
}
}
return targetNumIndex == 0;
}
};Solution 1: #Sliding Window
class Solution {
public:
int jump(vector<int>& nums) {
if(nums.size() == 1) return 0;
int ans = 0;
int curDis = 0;
int nextDis = 0;
for(int i = 0; i < nums.size(); i++){
nextDis = max(i + nums[i], nextDis);
if(i == curDis){ // 走到当前下标覆盖的最大范围的时候
ans++; // 多走1步
curDis = nextDis; // 更新当前下标覆盖的最大范围
if(curDis >= nums.size() - 1) break;
}
}
return ans;
}
};Solution 2: #Greedy
class Solution {
public:
int jump(vector<int>& nums) {
int curDis = 0;
int ans = 0;
int nextDis = 0;
for(int i = 0; i < nums.size() - 1; i++){
nextDis = max(i + nums[i], nextDis); // 下一步可以到达的最大距离
if(i == curDis){ // 已走到当前可以走到的最大距离
ans++; // 跳一步
curDis = nextDis; // 更新覆盖的距离
}
}
return ans;
}
};1005. Maximize Sum Of Array After K Negations
Solution 1: #Greedy
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size() && nums[i] < 0 && k > 0; i++){
nums[i] *= -1;
k--;
}
int minNum = INT_MAX;
int sum = 0;
for(int i = 0; i < nums.size(); i++){
minNum = min(nums[i], minNum);
sum += nums[i];
}
if(k % 2 != 0) sum -= minNum * 2;
return sum;
}
};Solution 1: #Brute Force
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
for(int i = 0; i < gas.size(); i++){ // traverse every station
int rest = gas[i] - cost[i];
int index = (i + 1) % gas.size();
while(rest > 0 && index != i){ // travel around the circuit
rest += gas[index] - cost[index];
index = (index + 1) % gas.size();
}
if(rest >= 0 && index == i) return i;
}
return -1;
}
};Solution 2: #Greedy
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){
start = i + 1;
curSum = 0;
}
}
if(totalSum < 0) return -1;
return start;
}
};Solution 1: #Greedy
class Solution {
public:
int candy(vector<int>& ratings) {
vector<int> vec(ratings.size(), 1); // initialise
for(int i = 1; i < ratings.size(); i++){ // satisfy the left neighbor
if(ratings[i] > ratings[i - 1]) vec[i] = vec[i - 1] + 1;
}
for(int i = ratings.size() - 2; i >= 0; i--){ // satisfy the right neighbor
if(ratings[i] > ratings[i + 1]) vec[i] = max(vec[i], vec[i + 1] + 1);
}
int ans = 0;
for(auto x : vec) ans += x;
return ans;
}
};Solution 1: #Greedy
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
int five = 0, ten = 0, twenty = 0;
for(auto x : bills){
if(x == 5) five++;
if(x == 10){
if(five <= 0) return false;
five--;
ten++;
}
if(x == 20){
if(ten > 0 && five > 0){
ten--;
five--;
}
else if(five >= 3) five -= 3;
else return false;
}
}
return true;
}
};406. Queue Reconstruction by Height
Solution 1: #Greedy
class Solution {
public:
static bool cmp(const vector<int>& a, const vector<int>& b){
if(a[0] == b[0]) return a[1] < b[1];
return a[0] > b[0];
}
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), cmp);
vector<vector<int>> que;
for(int i = 0; i < people.size(); i++){
int position = people[i][1];
que.insert(que.begin() + position, people[i]);
}
return que;
}
};452. Minimum Number of Arrows to Burst Balloons
Solution 1: #Greedy
class Solution {
public:
static bool cmp(vector<int>& a, vector<int>& b){
return a[0] < b[0];
}
int findMinArrowShots(vector<vector<int>>& points) {
if(points.size() == 0) return 0;
sort(points.begin(), points.end(), cmp);
int result = 1;
for(int i = 1; i < points.size(); i++){
if(points[i][0] > points[i - 1][1]) result++;
else{
points[i][1] = min(points[i - 1][1], points[i][1]);
}
}
return result;
}
};435. Non-overlapping Intervals
Solution 1: #Greedy
class Solution {
public:
static bool cmp(vector<int>& a, vector<int>& b){
return a[1] < b[1];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if(intervals.size() == 0) return 0;
sort(intervals.begin(), intervals.end(), cmp);
int count = 1;
int end = intervals[0][1];
for(int i = 1; i < intervals.size(); i++){
if(end <= intervals[i][0]){ // count the num of non-overlapping intervals
end = intervals[i][1];
count++;
}
}
return intervals.size() - count;
}
};Solution 1: #Greedy
class Solution {
public:
vector<int> partitionLabels(string s) {
int hash[27] = {0}; // 统计字符出现的最后位置
for(int i = 0; i < s.size(); i++){
hash[s[i] - 'a'] = i;
}
vector<int> result;
int left = 0;
int right = 0;
for(int i = 0; i < s.size(); i++){
right = max(right, hash[s[i] - 'a']);
if(i == right){
result.push_back(right - left + 1);
left = right + 1;
}
}
return result;
}
};Solution 1: #Greedy
class Solution {
public:
static bool cmp(vector<int>& a, vector<int>& b){
if(a[0] == b[0]) return a[1] < b[1];
return a[0] < b[0];
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end(), cmp);
vector<vector<int>> ans;
ans.push_back(intervals[0]);
for(int i = 1; i < intervals.size(); i++){
if(intervals[i][0] <= ans.back()[1]){
ans.back()[1] = max(intervals[i][1], ans.back()[1]); // 维护最大右边界
}
else ans.push_back(intervals[i]);
}
return ans;
}
};738. Monotone Increasing Digits
Solution 1: #Greedy
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string strNum = to_string(n);
int flag = strNum.size(); // 标记赋值的9从哪里开始
for(int i = strNum.size() - 1; i > 0; i--){
if(strNum[i] < strNum[i - 1]){
flag = i;
strNum[i - 1]--;
}
}
for(int i = flag; i < strNum.size(); i++){
strNum[i] = '9';
}
return stoi(strNum);
}
};Solution 1: #Greedy
class Solution {
public:
int result;
int traversal(TreeNode* cur){
if(cur == NULL) return 2;
int left = traversal(cur->left);
int right = traversal(cur->right);
if(left == 2 && right == 2) return 0;
if(left == 0 || right == 0){
result++;
return 1;
}
if(left == 1 || right == 1) return 2;
return -1;
}
int minCameraCover(TreeNode* root) {
result = 0;
if(traversal(root) == 0) result++;
return result;
}
};
// 我们分别有三个数字来表示：
// 0：该节点无覆盖
// 1：本节点有摄像头
// 2：本节点有覆盖