# Leetcode 第242场周赛题解

# Problem A - 哪种连续子字符串更长 (opens new window)

# 方法一：暴力

• 时间复杂度$\mathcal{O}(|S|)$
• 空间复杂度$\mathcal{O}(1)$

class Solution {
public:
bool checkZeroOnes(string s) {
int om = 0, zm = 0;
int o = 0, z = 0;
for (char c : s) {
if (c == '0') {
z++;
o = 0;
} else {
o++;
z = 0;
}
om = max(om, o);
zm = max(zm, z);
}
return om > zm;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# Problem B - 准时到达的列车最小时速 (opens new window)

# 方法一：二分

• 时间复杂度$\mathcal{O}(N\log D)$
• 空间复杂度$\mathcal{O}(1)$

using ll = long long;

template<typename ... Args>
std::string string_format( const std::string& format, Args ... args )
{
int size_s = std::snprintf( nullptr, 0, format.c_str(), args ... ) + 1;
if( size_s <= 0 ){ throw std::runtime_error( "Error during formatting." ); }
auto size = static_cast<size_t>( size_s );
auto buf = std::make_unique<char[]>( size );
std::snprintf( buf.get(), size, format.c_str(), args ... );
return std::string( buf.get(), buf.get() + size - 1 );
}

class Solution {
public:
int minSpeedOnTime(vector<int>& dist, double hour) {
int n = dist.size();
int lo = 1, hi = 1e7;
string s = string_format("%.2f", hour);
int m = s.size();
s = s.substr(0, m - 3) + s.substr(m - 2, 2);
ll limit = stoll(s);

while (lo <= hi) {
int mid = (lo + hi) >> 1;
ll tot = 0;
for (int i = 0; i < n - 1; ++i) {
tot += (dist[i] - 1) / mid + 1;
}
tot *= 100;
tot += (dist[n - 1] * 100 - 1) / mid + 1;
if (tot <= limit)
hi = mid - 1;
else
lo = mid + 1;
}
if (lo > 1e7)
return -1;
return lo;
}
};

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

# Problem C - 跳跃游戏 VII (opens new window)

# 方法一：离散化+树状数组+双指针

• 时间复杂度$\mathcal{O}(|S|+M\log M)$，其中$M$为字符串中0的个数。
• 空间复杂度$\mathcal{O}(M)$

inline int lowbit(int x) {
return x & (-x);
}

class Solution {
public:
bool canReach(string s, int minJump, int maxJump) {
int n = s.size();
if (s[n - 1] == '1')
return false;

vector<int> zero;
for (int i = 0; i < n; ++i)
if (s[i] == '0')
zero.emplace_back(i);
int m = zero.size();

vector<int> a(m + 1);
auto query = [&](int pos) {
int ans = 0;
for (; pos; pos -= lowbit(pos))
ans += a[pos];
return ans;
};
auto update = [&](int pos, int val) {
for (; pos <= m; pos += lowbit(pos))
a[pos] += val;
};

update(1, 1);
update(2, -1);
int l = 0, r = 0;
for (int i = 1; i < m; ++i) {
if (query(i) > 0) {
while (l < m && zero[l] < zero[i - 1] + minJump)
l++;
while (r < m && zero[r] <= zero[i - 1] + maxJump)
r++;
update(l + 1, 1), update(r + 1, -1);
}
}

return query(m) > 0;
}
};

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

# 方法二：平衡二叉搜索树

• 时间复杂度$\mathcal{O}(|S|+M\log M)$，其中$M$为字符串中0的个数。
• 空间复杂度$\mathcal{O}(|S|+M)$

class Solution {
public:
bool canReach(string s, int minJump, int maxJump) {
int n = s.size();
if (s[n - 1] == '1')
return false;

vector<int> zero;
for (int i = 0; i < n; ++i)
if (s[i] == '0')
zero.emplace_back(i);
int m = zero.size();
vector<bool> can(n);
can[0] = true;
set<int> st(zero.begin(), zero.end());
for (int i = 0; i + 1 < m; ++i) {
if (can[zero[i]]) {
vector<int> destinations;
for (auto it = st.lower_bound(zero[i] + minJump); it != st.upper_bound(zero[i] + maxJump); ++it) {
destinations.emplace_back(*it);
}
for (int destination : destinations) {
can[destination] = true;
st.erase(destination);
}
}
}

return can[n - 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

# 方法三：双端队列

• 时间复杂度$\mathcal{O}(|S|+M)$，其中$M$为字符串中0的个数。
• 空间复杂度$\mathcal{O}(|S|+M)$

class Solution {
public:
bool canReach(string s, int minJump, int maxJump) {
int n = s.size();
if (s[n - 1] == '1')
return false;

vector<int> zero;
for (int i = 0; i < n; ++i)
if (s[i] == '0')
zero.emplace_back(i);
int m = zero.size();
vector<bool> can(n);
can[0] = true;
deque<int> dq;
int ptr = 0;
for (int i = 1; i < m; ++i) {
while (ptr < i && zero[ptr] + minJump <= zero[i]) {
if (can[zero[ptr]])
dq.emplace_back(zero[ptr]);
ptr++;
}
while (!dq.empty() && dq.front() + maxJump < zero[i])
dq.pop_front();
can[zero[i]] = !dq.empty();
}

return can[n - 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

# Problem D - 石子游戏 VIII (opens new window)

# 方法一：动态规划

$dp[i]=\sum_{j=1}^istones[i]-\max_{j=i+1}^ndp[j]$

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(N)$

using ll = long long;

class Solution {
public:
int stoneGameVIII(vector<int>& stones) {
int n = stones.size();
vector<ll> s(n + 1);
for (int i = 1; i <= n; ++i)
s[i] = s[i - 1] + stones[i - 1];
vector<ll> dp(n + 1);
ll ans = dp[n] = s[n];
for (int i = n - 1; i > 1; --i) {
dp[i] = s[i] - ans;
ans = max(ans, dp[i]);
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18