# LeetCode Wiggle Subsequence

LeetCode Wiggle Subsequence
A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.
For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.
Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.
Examples:

Input: [1,7,4,9,2,5]
Output: 6
The entire sequence is a wiggle sequence.
Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].
Input: [1,2,3,4,5,6,7,8,9]
Output: 2


Can you do it in O(n) time?

class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
int ans = 1, i = 0, j = 1;
bool up = false;
while (j < n && nums[j] == nums[i])++j;
if (nums[j] > nums[i])up = true;
else up = false;
while (j < n) {
if (nums[j] > nums[i] && up) {
++ans;
up = false;
while (j + 1 < n&&nums[j + 1] >= nums[j])++j;
}
else if (nums[j] < nums[i] && !up) {
++ans;
up = true;
while (j + 1 < n&&nums[j + 1] <= nums[j])++j;
}
i = j++;
}
return ans;
}
};


class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
vector<int> up(n, 0), down(n, 0);
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (nums[i] > nums[j])up[i] = max(up[i], down[j] + 1);
else if (nums[i] < nums[j])down[i] = max(down[i], up[j] + 1);
}
}
return 1 + max(up[n - 1], down[n - 1]);
}
};


class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
vector<int> up(n, 0), down(n, 0);
up[0] = down[0] = 1;
for (int i = 1; i < n; ++i) {
if (nums[i] > nums[i - 1]) {
up[i] = down[i - 1] + 1;
down[i] = down[i - 1];
}
else if (nums[i] < nums[i - 1]) {
down[i] = up[i - 1] + 1;
up[i] = up[i - 1];
}
else {
up[i] = up[i - 1];
down[i] = down[i - 1];
}
}
return max(up[n - 1], down[n - 1]);
}
};


class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n = nums.size();
if (n < 2)return n;
int up = 1, down = 1;
for (int i = 1; i < n; ++i) {
if (nums[i] > nums[i - 1]) {
up = down + 1;
}
else if (nums[i] < nums[i - 1]) {
down = up + 1;
}
}
return max(up, down);
}
};


# LeetCode Non-overlapping Intervals

LeetCode Non-overlapping Intervals
Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
Note:

1. You may assume the interval's end point is always bigger than its start point.
2. Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.

Example 1:

Input: [ [1,2], [2,3], [3,4], [1,3] ]
Output: 1
Explanation: [1,3] can be removed and the rest of intervals are non-overlapping.


Example 2:

Input: [ [1,2], [1,2], [1,2] ]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of intervals non-overlapping.


Example 3:

Input: [ [1,2], [2,3] ]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

bool comp(const Interval &i1, const Interval &i2){
return i1.start < i2.start || (i1.start == i2.start && i1.end < i2.end);
}
class Solution {
public:
int eraseOverlapIntervals(vector<Interval>& intervals) {
if(intervals.empty()) return 0;
sort(intervals.begin(), intervals.end(), comp);
int ans = 1, n = intervals.size(), last_end = intervals[0].end;
for(int i = 1; i < n; ++i){
if(intervals[i].start >= last_end){
++ans;
last_end = intervals[i].end;
} else {
last_end = min(last_end, intervals[i].end);
}
}
return n - ans;
}
};


# LeetCode Is Subsequence

LeetCode Is Subsequence
Given a string s and a string t, check if s is subsequence of t.
You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).
Example 1:
s = "abc", t = "ahbgdc"
Return true.
Example 2:
s = "axc", t = "ahbgdc"
Return false.
If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

class Solution {
public:
bool isSubsequence(string s, string t) {
int m = s.size(), n = t.size();
if (m > n)return false;
int i = 0, j = 0;
while (i < m&&j < n) {
while (j < n&&s[i] != t[j])++j;
if (j >= n)return false;
++i;
++j;
}
return i == m;
}
};


# LeetCode Jump Game II

LeetCode Jump Game II
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
Note:
You can assume that you can always reach the last index.

class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
if (n <= 1)return 0;
int maxJump = n - 1;
vector<int> dp(n, 0);
for (int i = n - 2; i >= 0; --i) {
int curMinJump = maxJump;
for (int j = i + 1; j <= nums[i] + i&&j < n; ++j) {
curMinJump = min(curMinJump, dp[j] + 1);
}
dp[i] = curMinJump;
}
return dp[0];
}
};


class Solution {
public:
int jump(vector<int>& nums) {
int n = nums.size();
if (n <= 1)return 0;
int maxJump = n - 1;
vector<int> dp(n, 0), pre(n, 0);
for (int i = n - 2; i >= 0; --i) {
int curMinJump = maxJump, k = 0;
for (int j = i + 1; j <= nums[i] + i&&j < n; ++j) {
if (dp[j] + 1 < curMinJump) {
curMinJump = dp[j] + 1;
k = j;
}
}
dp[i] = curMinJump;
pre[k] = i; // 从i跳到k能获得最小跳数
}
return dp[0];
}
};


class Solution {
public:
int jump(vector<int>& nums) {
int jumps = 0, curEnd = 0, curFarthest = 0;
for (int i = 0; i < nums.size() - 1; ++i) {
curFarthest = max(curFarthest, i + nums[i]);
if (i == curEnd) {
curEnd = curFarthest;
++jumps;
if (curEnd >= nums.size() - 1)break;
}
}
return jumps;
}
};


# LeetCode Jump Game

LeetCode Jump Game
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.

class Solution {
public:
bool canJump(vector<int>& nums) {
int maxpos = 0;
for (int i = 0; i < nums.size(); ++i) {
if (i > maxpos)break;
maxpos = max(maxpos, i + nums[i]);
}
return maxpos >= nums.size() - 1;
}
};


# LeetCode Best Time to Buy and Sell Stock II

LeetCode Best Time to Buy and Sell Stock II
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

class Solution {
public:
int maxProfit(vector<int>& prices) {
int ans = 0;
for (int i = 1; i < prices.size(); ++i) {
if (prices[i] > prices[i - 1])ans += (prices[i] - prices[i - 1]);
}
return ans;
}
};


# LeetCode Minimum Number of Arrows to Burst Balloons

LeetCode Minimum Number of Arrows to Burst Balloons
There are a number of spherical balloons spread in two-dimensional space. For each balloon, provided input is the start and end coordinates of the horizontal diameter. Since it's horizontal, y-coordinates don't matter and hence the x-coordinates of start and end of the diameter suffice. Start is always smaller than end. There will be at most 104 balloons.
An arrow can be shot up exactly vertically from different points along the x-axis. A balloon with xstart and xend bursts by an arrow shot at x if xstart ≤ x ≤ xend. There is no limit to the number of arrows that can be shot. An arrow once shot keeps travelling up infinitely. The problem is to find the minimum number of arrows that must be shot to burst all balloons.
Example:

Input:
[[10,16], [2,8], [1,6], [7,12]]
Output:
2
Explanation:
One way is to shoot one arrow for example at x = 6 (bursting the balloons [2,8] and [1,6]) and another arrow at x = 11 (bursting the other two balloons).

class Solution {
public:
int findMinArrowShots(vector<pair<int, int>>& points) {
if (points.size() == 0)return 0;
sort(points.begin(), points.end());
int i = 0, j = 1, end, ans = 0;
while (i < points.size()) {
end = points[i].second;
while (j < points.size() && points[j].first <= end) {
end = min(end, points[j].second);
++j;
}
++ans;
i = j++;
}
return ans;
}
};


Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.
Note:
You may assume the greed factor is always positive.
You cannot assign more than one cookie to one child.
Example 1:

Input: [1,2,3], [1,1]
Output: 1
Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.


Example 2:

Input: [1,2], [1,2,3]
Output: 2
Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.

class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int i = g.size() - 1, j = s.size() - 1, ans = 0;
while (i >= 0) {
if (j >= 0 && s[j] >= g[i]) {
++ans;
--j;
}
--i;
}
return ans;
}
};


class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int i = 0, j = 0, ans = 0;
while (i < g.size()) {
while (j < s.size() && g[i] > s[j]) {
++j;
}
if (j >= s.size())break;
++ans;
++i;
++j;
}
return ans;
}
};


AC了，但是还是很慢，449MS。。。

# LeetCode Container With Most Water

LeetCode Container With Most Water
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.

class Solution {
public:
int maxArea(vector<int>& height) {
int mA = 0, i = 0, j = height.size() - 1;
while (i != j)
{
int cur = min(height[i], height[j])*(j - i);
if (cur > mA)
mA = cur;
if (height[i] < height[j])
i++;
else
j--;
}
return mA;
}
};


# hihoCoder 1051-补提交卡

hihoCoder 1051-补提交卡
#1051 : 补提交卡

3
5 1
34 77 82 83 84
5 2
10 30 55 56 90
5 10
10 30 55 56 90

76
59
100

#include<iostream>
#include<vector>
using namespace std;
int main()
{
int t;
cin>>t;
int n,m;
while(t--)
{
cin>>n>>m;
vector<int> a(n+1);
for(int i=0;i<n;i++)
cin>>a[i];
a[n]=101;//哨兵
if(m>=n)
cout<<100<<endl;
else
{
int max_days=0;//最长连续提交天数
int case_num=n-m+1;//总的枚举情况数
for(int i=0;i<case_num;i++)
{
int last_index=m+i-1;//该方案下最后一个下标
if(i==0)
{
if(a[last_index+1]-1>max_days)
max_days=a[last_index+1]-1;
}
else
{
if(a[last_index+1]-a[i-1]-1>max_days)
max_days=a[last_index+1]-a[i-1]-1;
}
}
cout<<max_days<<endl;
}
}
return 0;
}