# # Leetcode 第30场双周赛题解

## # Problem A - 转变日期格式 (opens new window)

class Solution:
def reformatDate(self, date: str) -> str:
a, b, c = date.split(' ')
d = {"Jan": "01", "Feb": "02", "Mar": "03", "Apr": "04", "May": "05", "Jun": "06", "Jul": "07", "Aug": "08", "Sep": "09", "Oct": "10", "Nov": "11", "Dec": "12"}
day = a[:-2]
if len(day) == 1:
day = "0" + day
month = d[b]
year = c
return "{}-{}-{}".format(year, month, day)

1
2
3
4
5
6
7
8
9
10

## # Problem B - 子数组和排序后的区间和 (opens new window)

typedef long long ll;
const ll MOD = 1e9 + 7;

class Solution {
public:
int rangeSum(vector<int>& nums, int n, int left, int right) {
int m = n * (n + 1) / 2;
vector<int> sum(n + 1);
for (int i = 1; i <= n; ++i)
sum[i] = sum[i - 1] + nums[i - 1];
vector<int> v;
v.reserve(m);
for (int i = 1; i <= n; ++i)
for (int j = i; j <= n; ++j)
v.emplace_back(sum[j] - sum[i - 1]);
sort(v.begin(), v.end());
ll ans = 0;
for (int i = left - 1; i < right; ++i)
ans = (ans + v[i]) % MOD;
return ans;
}
};

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

typedef long long ll;
const ll MOD = 1e9 + 7;

class Solution {
int n;
vector<int> pre, prepre;

int search(int k) {
int l = 1, r = pre[n];
while (l <= r) {
int mid = (l + r) >> 1, cnt = 0;
int i = 0, j = 0;
while (i < n) {
while (j < n && pre[j + 1] - pre[i] <= mid)
j++;
cnt += j - i;
i++;
}
if (cnt < k)
l = mid + 1;
else
r = mid - 1;
}
return l;
}

int sum(int k) {
if (k == 0)
return 0;
int target = search(k);
int cnt = 0;
ll ans = 0;
int i = 0, j = 0;
while (i < n) {
while (j < n && pre[j + 1] - pre[i] < target)
j++;
cnt += j - i;
ans += prepre[j] - prepre[i] - (j - i) * pre[i];
i++;
}
ans += (k - cnt) * target;
return ans % MOD;
}
public:
int rangeSum(vector<int>& nums, int n, int left, int right) {
this->n = n;
pre = vector<int>(n + 1);
prepre = vector<int>(n + 1);
for (int i = 1; i <= n; ++i) {
pre[i] = pre[i - 1] + nums[i - 1];
prepre[i] = prepre[i - 1] + pre[i];
}
int r = sum(right);
int l = sum(left - 1);
return (r - l + MOD) % MOD;
}
};

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
57

## # Problem C - 三次操作后最大值与最小值的最小差 (opens new window)

class Solution {
public:
int minDifference(vector<int>& nums) {
int n = nums.size();
if (n <= 4)
return 0;
sort(nums.begin(), nums.end());
int ans = INT_MAX;
for (int i = 0; i <= 3; ++i) {
ans = min(ans, nums[n - 4 + i] - nums[i]);
}
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

class Solution {
public:
bool winnerSquareGame(int n) {
vector<bool> dp(n + 1);
dp[1] = true;
for (int i = 2; i <= n; ++i) {
bool win = false;
for (int k = 1; k * k <= i; ++k)
if (!dp[i - k * k]) {
win = true;
break;
}
dp[i] = win;
}
return dp[n];
}
};

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