周赛链接：https://leetcode.cn/contest/weekly-contest-149/
涉及知识点：动态规划、滑动窗口、线段树、布尔投票法
直接根据天数规律计算即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int dayOfYear(string date) {
int year = stoi(date.substr(0, 4));
int month = stoi(date.substr(5, 2));
int day = stoi(date.substr(8, 2));
bool leapYear = (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
int monthDays[] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
if (leapYear) { monthDays[1] = 29; }
int result = 0;
for (int i = 0; i < month - 1; i++) { result += monthDays[i]; }
return result + day;
}
};
|
列出状态转移方程：
$
f(n, j) = {\textstyle \sum_{x=1}^{k}} f(n-1, j-x)
$
然后根据方程列写动态规划即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int numRollsToTarget(int n, int k, int target) {
vector<int> dp(k + 1, 1);
dp[0] = 0;
for (int i = 2; i <= n; i++) {
vector<int> newDp(k * i + 1, 0);
for (int j = k * i; j > 0; j--) {
for (int l = j - k; l <= j - 1; l++) {
if (l >= 1 && l <= dp.size() - 1) {
newDp[j] += dp[l];
newDp[j] %= 1000000007;
}
}
}
dp = newDp;
}
if (target >= n && target <= n * k) { return dp[target] % 1000000007; }
return 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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| class Solution {
public:
int maxRepOpt1(string text) {
unordered_map<char, int> charCnts;
unordered_map<char, bool> isRepeated;
int result = 0;
char curr = text[0];
int currCnt = 1;
for (int i = 1; i < text.size(); i++) {
if (text[i] == curr) {
currCnt++;
}
else {
if (charCnts.find(curr) == charCnts.end()) {
charCnts[curr] = currCnt;
}
else {
isRepeated[curr] = true;
if (currCnt > charCnts[curr]) {
charCnts[curr] = currCnt;
}
}
curr = text[i];
currCnt = 1;
}
}
if (charCnts.find(curr) == charCnts.end()) {
charCnts[curr] = currCnt;
}
else {
isRepeated[curr] = true;
if (currCnt > charCnts[curr]) {
charCnts[curr] = currCnt;
}
}
for (auto& it : charCnts) {
if (isRepeated[it.first]) {
result = max(result, it.second + 1);
}
else {
result = max(result, it.second);
}
}
for (int i = 1; i < text.size() - 1; i++) {
if (text[i - 1] == text[i + 1] && text[i] != text[i - 1]) {
char curr = text[i - 1];
int leftPtr = i - 1; int rightPtr = i + 1; int currCnt = 0;
while (leftPtr >= 0 && text[leftPtr] == curr) { leftPtr--; currCnt++; }
while (rightPtr < text.size() && text[rightPtr] == curr) { rightPtr++; currCnt++; }
for (int j = 0; j < text.size(); j++) {
if (text[j] == curr && (j <= leftPtr || j >= rightPtr)) {
result = max(result, currCnt + 1);
}
}
result = max(result, currCnt);
}
}
return result;
}
};
|
布尔投票法
寻找一个数组中的绝对众数（即出现次数大于等于数组长度的一半的元素）时，同时去除两个互不相同的元素不对结果产生影响，由此可得布尔投票法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int majorityElement(vector<int>& nums) {
int candidate = -1;
int count = 0;
for (int num : nums) {
if (num == candidate)
++count;
else if (--count < 0) {
candidate = num;
count = 1;
}
}
return candidate;
}
};
|
线段树
自底向上维护的，划分一个线段的树状结构。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| void build(int s, int t, int p) {
if (s == t) {
d[p] = a[s];
return;
}
int m = s + ((t - s) >> 1);
build(s, m, p * 2), build(m + 1, t, p * 2 + 1);
d[p] = d[p * 2] + d[(p * 2) + 1];
}
|
由于将区间分为两部分分别得到candidate和count，并再将两个区间的该值进行比较仍然能得出众数结果，所以采取线段树对指定子数组的众数状态进行管理。