彻底翻车了
最后一个都没写出来。。
找个理由强行解释下，可能是没睡好hhh。
简单模拟， 不过我这里写的太麻烦了。
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
| class Solution {
public:
bool checkZeroOnes(string s) {
char p = '2';
int mx1 = 0, mx0 = 0;
int sum1 = 0, sum0 = 0;
for(auto c: s) {
if(c == p){
if(c == '0'){
sum0++;
mx0 = max(mx0, sum0);
} else if(c == '1') {
sum1++;
mx1 = max(mx1, sum1);
}
} else {
if(c == '0'){
mx0 = max(mx0, sum0);
sum0=1;
mx0 = max(mx0, sum0);
} else if(c == '1') {
mx1 = max(mx1, sum1);
sum1=1;
mx1 = max(mx1, sum1);
}
}
p = c;
}
return mx1 > mx0;
}
};
|
二分答案。 注意浮点数二分用次数就好了。
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:
bool check(vector<int>& dist, double hour, double x) {
double time = 0;
for(auto a: dist) {
time = ceil(time);
time += a/x;
}
return time <= hour;
}
int minSpeedOnTime(vector<int>& dist, double hour) {
double l = 0, r = 1e9, mid;
bool flag = false;
for(int i=0;i<100;i++) {
mid = (l+r) / 2.0;
if(check(dist, hour, mid)) r = mid, flag = true;
else l=mid;
}
if(flag) return ceil(r);
else return -1;
}
};
|
这里因为minJump和maxJump的取值范围很有可能使maxJump−minJump∈[0,1e5] , 所以不建议直接bfs。
这里可以参考扫描线维护区间覆盖的方式逐步遍历过去。同时判断每个位置是否被覆盖了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
bool canReach(string s, int minJump, int maxJump) {
int n = s.size();
vector<int> vis(n+1);
bool flag = false;
for(int i=0;i<n;i++) {
if(i) vis[i] += vis[i-1];
if(s[i] == '0' && (vis[i]>0 || i==0)) {
vis[min(n, i+minJump)] ++;
vis[min(n-1,i+maxJump)+1] --;
}
}
return s[n-1] == '0' && vis[n-1]>0;
}
};
|
这里最开始脑抽了，以为可以讨论出来，后面才想起来得DP，（DP水平实在太差了）
这里设dp(i) 表示 第i个位置已经是新的合并后的石子时先手的最大差值。
这里注意下，我一直觉得这里很绕。
当轮到后手时因为他的值在差值里时被减的，后手又想要差值尽可能小。
这个时候如果不考虑之前的状态，那么可以说明这个后手就是现在的先手, 所以后手的选择策略和先手时一样的。
转移方程为：
dp(i)={MAX(−dp(j)+(∑idx=ijstone[idx]+∑idx=0i−1stone[idx]) ),j∈[i+1,n)}
这一手货的的积分减去下一手的最大差值
这里因为题目条件有个这个
- 将一个 新的石子 放在最左边，且新石子的值为被移除石子值之和。
所以第i个位置其实已经是∑idx=0istone[idx] 了。
化简一下转移方程就是：
dp(i)={MAX(−dp(j)+∑idx=0jstone[idx]),j∈[i+1,n)}
连续和维护一个前缀和sum(i)就好了。
最终转移就是
dp(i)=max(−dp(j)+sum[j]),j∈[i+1,n)
最大值可以从后遍历维护，总的复杂度是O(N)的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
int stoneGameVIII(vector<int>& a) {
int n = a.size();
vector<int> sum(n+1);
for(int i=0;i<n;i++) sum[i+1] = sum[i] + a[i];
vector<int> dp(n+1);
dp[n] = 0;
int mx = sum[n];
for(int i=n-1;i>0;i--) {
dp[i] = mx;
mx = max(mx, -dp[i]+sum[i]);
}
return dp[1];
}
};
|
