bool checkZeroOnes(string s) {
int yi = 0, ling = 0;
for (int i = 0, x = 0, y = 0; i < s.size(); i++)
{
if (s[i] == '1'){
y ++;
x = 0;
}
if (s[i] == '0'){
x ++;
y = 0;
}
yi = max(yi, y);
ling = max(ling , x);
}
return yi > ling;
}
2
二分,上取整
double get(vector<int>& dist, int mid)
{
double res = 0; //shijian
for (int i = 0; i + 1<dist.size(); i++)
res += (dist[i] + mid - 1) / mid; //除了最后一段,上取整[a/b]=下取整[a + b -1/b]
return res + (double)dist.back() / mid;
}
int minSpeedOnTime(vector<int>& dist, double hour) {
int l = 1, r = 2e7;
while (l < r) //
{
int mid = l + r >> 1;
if (get(dist, mid) <= hour) r = mid;
else l = mid + 1;
}
if (r == 2e7) return -1;
return r;
}
3
前缀和
bool canReach(string S, int a, int b) {
int n = S.size();
vector<int> f(n + 1), s(n + 1);
f[1] = 1, s[1] = 1;
//DP方案,前缀和
for (int i = 2; i <= n; i ++ ) {
if (S[i - 1] != '0' || i <= a) {
s[i] = s[i - 1];
} else {
// 左端点,右端点
int l = max(1, i - b), r = max(1, i - a);
if (s[r] > s[l - 1]) f[i] = 1; //至少存在一种方案
s[i] = s[i - 1] + f[i];
}
}
return f[n];
}
4
博弈论
int stoneGameVIII(vector<int>& w) {
reverse(w.begin(), w.end());
int n = w.size();
vector<int> s(n + 1), f(n + 1);
for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + w[i - 1];
int v = s[n] - s[0] + f[1];
for (int i = 2; i <= n; i ++ ) {
f[i] = v;
v = max(v, s[n] - s[i - 1] - f[i]);
}
return f[n];
}