Word Break
Total Accepted: 18367 Total
Submissions: 88637My Submissions
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s = "leetcode",
dict = ["leet", "code"].
Return true because "leetcode" can
be segmented as "leet code".
递推方程： res[n]=E( res[i]&&word[i+1][n] , || ),
class Solution {
public:
bool wordBreak(string s, unordered_set<string> &dict) {
int n=s.length();
if(n==0) return false;
vector<vector<int> > vs(n,vector<int>());
for(int i=0;i<n;i++){
string t="";
for(int j=i;j<n;j++){
t+=s[j];
if(dict.find(t)!=dict.end()){
//vs[i][j]=true;
vs[j].push_back(i);
}
}
}
vector<bool> w(n,false);
for(int i=0;i<n;i++){
if(!vs[i].empty()){
if(vs[i][0]==0) w[i]=true;//0~i
else {
for(int k=0;k<vs[i].size();k++){
int j=vs[i][k];
if(w[j-1]) {w[i]=true;break;}
}
}
}
}
return w[n-1];
}
};
Best Time to Buy and Sell Stock III
Total Accepted: 12168 Total
Submissions: 54912My Submissions
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 at most two transactions.
Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
递推方程 s[n]=max(0,s[n-1],price[n]-minPrice[0~n] ) t[n]=max(0,t[n+1],maxPrice[n~N]-price[n]) (其中边界t[N]=0)
class Solution {
public:
int maxProfit(vector<int> &prices) {
int N=prices.size();
vector<int> l(N,0),r(N+1,0);
int _min=0x7fffffff,_max=0;
for(int i=0;i<N;i++){
if(_min>prices[i]) _min=prices[i];
l[i]=prices[i]-_min;
if(i>0) l[i]=max(l[i-1],l[i]);
l[i]=max(0,l[i]);
}
r[N]=0;
for(int i=N-1;i>=0;i--){
if(_max<prices[i]) _max=prices[i];///@@@@error:_max>prices...
r[i]=_max-prices[i];
if(i<N-1) r[i]=max(r[i+1],r[i]);
r[i]=max(0,r[i]);
}
int res=0;
for(int i=0;i<N;i++){
res=max(res,l[i]+r[i+1]);
}
return res;
}
};
Maximum Subarray
Total Accepted: 20499 Total
Submissions: 61220My Submissions
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.
注意子串不能为空，可能为负
class Solution {
public:
int maxSubArray(int A[], int n) {
int res=0x80000000;int cnt=0;
for(int i=0;i<n;i++){
cnt+=A[i];
res=max(res,cnt);//@@error:res must update before cnt update, to retain the negative max values
if(cnt<0) cnt=0;
}
return res;
}
};
Jump Game II
Total Accepted: 13388 Total
Submissions: 54971My Submissions
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.)
class Solution {
public:
int jump(int A[], int n) {
#define MAXN 0x7fffffff
vector<int> B(n,0);
if(n==0) return 0;
B[n-1]=0;
for(int i=n-2;i>=0;i--){
B[i]=MAXN;
int j=min(n-1,i+A[i]);
if(j>i&&B[j]<MAXN) /////@@@@error: B[j] can not be MAXN, lose this condition
B[i]=B[j]+1;
j=i;
while(j+1<=n-1&&B[j]<B[j+1]) B[j+1]=B[j],j++;///@error:lose j++ as loop continue statement
}
return B[0];
}
};
Gas Station
Total Accepted: 15990 Total
Submissions: 64278My Submissions
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of
gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
class Solution {
public:
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
int n=gas.size();
int g=0,c=0;
for(int i=0;;i++){
int r=gas[i%n]-cost[i%n];
if(g+r>=0){
g+=r,c++;
if(c==n) return (i+1)%n;//下一站就是起点站，index从0开始算
}
else {
g=0,c=0;
if(i>=n) return -1;
}
}
}
};