理想状态和实际总有距离
这个题和basic calculator差不多，栈来记录状态。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| class Solution {
public:
bool parseBoolExpr(string expression) {
stack<char>s;
for(int i=0;i<expression.size();i++) {
char ch = expression[i];
if(ch==')') {
bool hasT = false;
bool hasF = false;
while(s.top()=='t' || s.top()=='f') {
hasT |= (s.top()=='t');
hasF |= (s.top()=='f');
s.pop();
}
char op = s.top();
s.pop();
if(op == '!') {
if(hasT) {
s.push('f');
}else {
s.push('t');
}
} else if(op=='&') {
if(hasF) {
s.push('f');
} else {
s.push('t');
}
} else if(op=='|'){
if(hasT) {
s.push('t');
} else {
s.push('f');
}
}
} else {
if(ch != ',' && ch!='(') {
s.push(ch);
}
}
}
return s.top()=='t';
}
};
|
这个题和我之前在51nod上讨论过的，求区间大于等于0的最长区间很类似。
那道题需要对前缀和进行排序，解法也非常巧妙。
这个题因为值本身很特殊，都是1或者-1，所以前缀和一定是相差1，解法上有一点类似于之前经历的汽车加油的那道题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public:
int val[10005];
int longestWPI(vector<int>& hours) {
int maxx = 0;
int minn = 0;
map<int,int>hax;
int ans = 0;
for(int i=0;i<hours.size();i++) {
if(hours[i] > 8) {
val[i+1] = 1;
ans = 1;
} else {
val[i+1] = -1;
}
val[i+1] += val[i];
if(i==0) {
maxx = minn = val[i+1];
} else {
maxx = max(maxx ,val[i+1]);
minn = min(minn, val[i+1]);
}
if(hax.count(val[i+1]))continue;
hax[val[i+1]] = i+1;
}
for(int i=minn+1;i<=maxx; i++) {
hax[i] = min(hax[i], hax[i-1]);
}
for(int i=1;i<=hours.size();i++) {
if(val[i]>0) ans = max(ans, i);
if(hax[val[i]-1])
ans = max(ans, i-hax[val[i]-1]);
}
return ans;
}
};
|
本质还是背包
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| class Solution {
public:
vector<int> smallestSufficientTeam(vector<string>& req_skills, vector< vector<string> >& people) {
map<string, int>hax;
for(int i=0;i<req_skills.size();i++) {
hax[req_skills[i]] = i;
}
unordered_map<int,vector<int> >res;
res[0] = {};
vector<int>have;
have.push_back(0);
for(int i=0;i<people.size();i++) {
int bitmask = 0;
for(int j=0;j<people[i].size();j++) {
bitmask = bitmask | (1<<hax[people[i][j]]);
}
set<int>nxt(have.begin(),have.end());
for(int j=have.size()-1;j>=0;j--) {
int val = have[j];
int k = have[j] | bitmask;
if(!res.count(k) || res[k].size() > res[val].size() + 1) {
res[k] = res[val];
res[k].push_back(i);
nxt.insert(k);
}
}
have.clear();
for(auto i:nxt) {
have.push_back(i);
}
sort(have.begin(),have.end());
}
return res[(1<<req_skills.size())-1];
}
};
|
要记怎么来的，不能只记结果，这个踩过很多坑了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| class Solution {
public:
vector<int> shortestAlternatingPaths(int n, vector<vector<int> >& red_edges, vector<vector<int> >& blue_edges) {
queue< pair<int,int> >que;
que.push(make_pair(0,-1));
map<int,int>hax[2];
hax[0][0] = 0;
hax[1][0] = 0;
while(!que.empty()) {
pair<int,int> now = que.front();
que.pop();
if(now.second == -1 || now.second == 1) {
int t = now.second;
now.second = 1;
rep(i,0,red_edges.size()) {
if(red_edges[i][0]==now.first) {
int len = hax[now.second][now.first] + 1;
if(!hax[1 - now.second].count(red_edges[i][1]) || hax[1 - now.second][red_edges[i][1]] > len) {
hax[1-now.second][red_edges[i][1]] = len;
que.push(make_pair(red_edges[i][1], 1-now.second));
}
}
}
now.second=t;
}
if(now.second == -1 || now.second == 0) {
now.second=0;
rep(i,0,blue_edges.size()) {
if(blue_edges[i][0]==now.first) {
int len = hax[now.second][now.first] + 1;
if(!hax[1 - now.second].count(blue_edges[i][1]) || hax[1 - now.second][blue_edges[i][1]] > len) {
hax[1-now.second][blue_edges[i][1]] = len;
que.push(make_pair(blue_edges[i][1], 1-now.second));
}
}
}
}
}
vector<int>ans;
rep(i,0,n) {
int res = 1e9;
if(hax[0].count(i)) {
res = min(res,hax[0][i]);
}
if(hax[1].count(i)) {
res = min(res,hax[1][i]);
}
if(res==1e9) {
res = -1;
}
ans.push_back(res);
}
return ans;
}
};
|
带绝对值这种题，无论多麻烦，都要先脱掉它
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class Solution {
public:
int sum[2][40005];
int diff[2][40005];
int cal(int g[],int n) {
int maxx = g[0];
int minn = g[0];
rep(i,0,n) {
maxx = max(maxx,g[i]);
minn = min(minn,g[i]);
}
return maxx - minn;
}
int maxAbsValExpr(vector<int>& arr1, vector<int>& arr2) {
int n = arr1.size();
rep(i,0,arr1.size()) {
sum[0][i] = arr1[i] + arr2[i] + i;
sum[1][i] = arr1[i] + arr2[i] - i;
diff[0][i] = arr1[i] - arr2[i] + i;
diff[1][i] = arr1[i] - arr2[i] - i;
}
return max(max(cal(sum[0],n),cal(sum[1],n)),max(cal(diff[0],n),cal(diff[1],n)));
}
};
|
题意是找到最长的LCS的值。
如果输出具体的字符串怎么做。记录每个点的pre，判断相等就说明这个字符在最终的结果里。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
int dp[1005][1005];
int longestCommonSubsequence(string text1, string text2) {
memset(dp,0,sizeof(dp));
for(int i=0;i<text1.size();i++) {
for(int j=0;j<text2.size();j++) {
dp[i+1][j+1] = dp[i][j];
if(text1[i] == text2[j]) {
dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j]+1);
}
dp[i+1][j+1] = max(dp[i+1][j+1],dp[i+1][j]);
dp[i+1][j+1] = max(dp[i+1][j+1],dp[i][j+1]);
}
}
return dp[text1.size()][text2.size()];
}
};
|