题意：
给定一个数组，问可以从中选择最多多少个连续的数，使得这些数排序后，相邻两个数的差最多是 1。
数据范围：
1 <= runes.length <= 10^40 <= runes[i] <= 10^4
题解：
值域范围很小，可以直接开一个大小为 10001 的数组，然后统计每个数出现的次数，最后遍历这个数组判断即可。
如果值域范围很大，可以开一个 map 来统计，然后遍历 map 判断即可。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public:
int runeReserve(vector<int>& runes) {
const int MAXN = 10010;
vector<int> cnt(MAXN, 0);
for (auto u: runes) cnt[u] += 1;
int ans = 1;
int res = 0;
for (int i = 0; i < MAXN; ++i) {
if (cnt[i] == 0) {
res = 0;
continue ;
}
res += cnt[i];
ans = max(ans, res);
}
return ans;
}
};
|
题意：
给定一些城墙的区间，按照递增顺序给出，任意两个城墙区间不相交。
现在统一给所有城墙膨胀，每个城墙膨胀数量一样，可以向左向右膨胀，问每个城墙膨胀的最大数量。
数据范围：
3 <= rampart.length <= 10^4rampart[i].length == 20 <= rampart[i][0] < rampart[i][1] <= rampart[i+1][0] <= 10^8
题意：
对于最左和最右边的城墙，其可以无限扩张，所以他们不被考虑在内。
考虑有 3 个城墙，对于 2 号城墙，可以将 1 号 到 2 号和 2 号到 3 号中间这部分城墙全部作为其膨胀得到的城墙。
考虑有 4 个城墙，对于 2 号城墙，可以将 1 号 到 2 号城墙中的部分作为其膨胀的部分，而 2 号和 3号中间这部分，就不好界定了。
考虑二分答案，每个城墙可以膨胀的数量，枚举到第 i 个城墙时，其左边还未被膨胀的部分都可以作为其膨胀的部分，然后再从其右边的部分膨胀其需要的值即可。
代码：
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
|
class Solution {
public:
int rampartDefensiveLine(vector<vector<int>>& vec) {
int l = 0, r = 100000000;
int n = vec.size();
auto check = [&](int mid) {
// 对于每一个，先看其左边可以提供的，左边如果提供足够了，就不考虑右边了，否则看右边提供多少个
int used = 0;
for (int i = 1; i + 1 < n; ++i) {
int left = vec[i][0] - vec[i - 1][1] - used;
if (left < mid) {
int need = mid - left;
if (vec[i + 1][0] - vec[i][1] >= need) used = need;
else return false;
} else {
used = 0;
}
}
return true;
};
while (l < r) {
int mid = l + r + 1 >> 1;
if (check(mid)) l = mid;
else r = mid - 1;
}
return l;
}
};
|
题意：
给定一个长度为 len 的字符串 mantra 和一个 n * m 的矩阵 matrix，
字符串中的字符和矩阵中的元素均为小写字母，初始在 [0, 0] ，按照字符串的顺序依次走到矩阵中的每个位置，问最少需要走多少次可以走完。
数据范围：
0 < matrix.length, matrix[i].length <= 1000 < mantra.length <= 100matrix 和 mantra 仅由小写字母组成
题解：
这题赛时被 dp 卡住了，后面才反应过来是三维 bfs。
每次移动和取数都会增加一次操作，移动会修改 x 或者 y，取数会修改 k。
从 (0, 0, 0) 开始 bfs ，当前位置的字符 matrix[x][y] 和 mantra[k] 相等，则说明可以取数。每次可以向上下左右移动 4 次。
每个(x, y, k) 扩展最多 5 次，时间复杂度是 $O(n\times m\times len)$。
代码：
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
|
const int INF = 0x3f3f3f3f;
int dist[105][105][105];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
class Solution {
public:
int extractMantra(vector<string>& matrix, string mantra) {
int n = matrix.size(), m = matrix[0].size(), len = mantra.size();
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
for (int k = 0; k <= len; ++k)
dist[i][j][k] = INF;
dist[0][0][0] = 0;
queue<tuple<int, int, int>> q;
q.emplace(0, 0, 0);
int ans = INF;
while (!q.empty()) {
auto [x, y, k] = q.front(); q.pop();
if (k == len) {
ans = min(ans, dist[x][y][k]);
continue ;
}
if (matrix[x][y] == mantra[k]) {
if (dist[x][y][k + 1] > dist[x][y][k] + 1) {
dist[x][y][k + 1] = dist[x][y][k] + 1;
q.emplace(x, y, k + 1);
}
}
for (int i = 0; i < 4; ++i) {
int nx = x + dx[i], ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny][k] > dist[x][y][k] + 1) {
dist[nx][ny][k] = dist[x][y][k] + 1;
q.emplace(nx, ny, k);
}
}
}
return ans == INF ? -1 : ans;
}
};
|
题意：
给定一棵树，从根开始，构造这棵树的生成方式，用 0 表示父节点生成一个子节点，用 1 表示从子节点回到父节点，用 0 和 1 表示生成方式，求所有生成方式的最小字典序，注意，生成完树中所有节点后，不用回到根节点。
1 <= parents.length <= 10^4-1 <= parents[i] < i (即父节点编号小于子节点)
题解：
一个直观的生成方式，dfs 得到每棵子树的最小字典序生成方式，然后按照字典序排序输出。复杂度是正确的，但是不会证明。
首先每个子树会被 sort 一次，即除了根外都会 sort 一次，总共 sort 的元素数是 $O(n)$，但是内部的字符串长度是不定的，但是注意，sort 中两个字符串比较取决于较小的长度，即完全 k 叉树的情况会得到最大的 sort 复杂度，如此以完全二叉树为例，$2^{14}=16384$，同时深度最大时，比较最小，最多比较 14 层。故粗略的估计复杂度为 $O(n\log n\times 14)$。
代码：
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
|
class Solution {
public:
string dfs(int u, vector<vector<int>>& g) {
vector<string> vec;
for (int v: g[u]) {
vec.emplace_back(dfs(v, g) + "1");
}
sort(vec.begin(), vec.end());
string res;
for (auto& s: vec) {
res += "0" + s;
}
return res;
}
string evolutionaryRecord(vector<int>& parents) {
if (parents.size() == 1) return "";
int n = parents.size();
vector<vector<int>> g(n);
for (int i = 1; i < n; ++i) {
g[parents[i]].push_back(i);
}
string ans = dfs(0, g);
while (!ans.empty() && ans.back() == '1') ans.pop_back();
return ans;
}
};
|
题意：
给定一个长度为 n 的数组 arr，以及k 个操作，第 i 个操作 operations[i] = [type, x, y]，每个操作有两种类型：
- type = 0，表示修改操作，
arr[x] = y
- type = 1，表示运算操作，将 y 进行
x * n 次与非操作，第 i 次与非运算为：y = y NAND arr[i % n]。
最后将所有运算操作的 y 的异或值返回。
数据范围：
1 <= arr.length, operations.length <= 10^41 <= k <= 300 <= arr[i] <= 2^k- 若
type = 0，0 <= x < arr.length 且 0 <= y < 2^k
- 若
type = 1，1 <= x < 10^9 且 0 <= y < 2^k
- 保证存在
type = 1 的操作
题解：
对于位运算的题，位之间是独立的，考虑拆位，即单独考虑每一位。
对于两个位之间的与非操作，有四种情况：
- !(1 & 1) = 0
- !(1 & 0) = 1
- !(0 & 1) = 1
- !(0 & 0) = 1
可以发现，当任意一个位为 0 ，答案为 1，那么对于查询操作，最后一个 0 操作后，位变成 1，只需要考虑最后一个 0 的位置。
对于连续的 1 ，上述考虑 1 的变换，!(x & 0) => !x，即取反，那么只需要考虑连续 1 的个数为奇数还是偶数即可。
因此，我们的任务转换为了求每一位的最后一个 0 的位置，但是注意，我们还会修改值，因此需要一个快速删除和查询极值的数据结构，线段树或者set都可以。
代码：
set 实现
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
|
// set
class Solution {
public:
int getNandResult(int k, vector<int>& arr, vector<vector<int>>& operations) {
int n = arr.size();
vector<set<int>> vec(k);
for (int i = 0; i < arr.size(); ++i) {
for (int j = 0; j < k; ++j) {
if (arr[i] >> j & 1) continue ;
vec[j].insert(i);
}
}
int ans = 0;
for (auto& op: operations) {
int type = op[0], x = op[1], y = op[2];
if (type == 0) {
for (int j = 0; j < k; ++j) {
if ((arr[x] >> j & 1) == (y >> j & 1)) continue ;
if (!(y >> j & 1)) vec[j].insert(x);
else vec[j].erase(x);
}
arr[x] = y;
} else {
int res = 0;
for (int j = 0; j < k; ++j) {
int start = y >> j & 1;
int odd = 1;
if (vec[j].empty()) {
if (x % 2 == 0 || n % 2 == 0) {
odd = 0;
}
} else {
start = 1;
int last = n - 1 - *(vec[j].rbegin());
if (last % 2 == 0) {
odd = 0;
}
}
if (odd) start ^= 1;
if (start) res |= 1 << j;
}
ans ^= res;
}
}
return ans;
}
};
|
线段树实现：
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
// 线段树
const int N = 10010;
struct Node {
int l, r, p;
}tr[30][N << 2];
vector<int> a;
int n;
void pushup(Node tr[], int u) {
tr[u].p = max(tr[u << 1].p, tr[u << 1 | 1].p);
}
void build(Node tr[], int k, int u, int l, int r) {
tr[u] = {l, r};
if (l == r) {
if (a[l] >> k & 1) tr[u].p = -1;
else tr[u].p = l;
return ;
}
int mid = (l + r) >> 1;
build(tr, k, u << 1, l, mid);
build(tr, k, u << 1 | 1, mid + 1, r);
pushup(tr, u);
}
void modify(Node tr[], int k, int u, int x, int y) {
if (tr[u].l == tr[u].r) {
a[x] = y;
if (a[x] >> k & 1) tr[u].p = -1;
else tr[u].p = x;
return ;
}
int mid = (tr[u].l + tr[u].r) >> 1;
if (x <= mid) modify(tr, k, u << 1, x, y);
else modify(tr, k, u << 1 | 1, x, y);
pushup(tr, u);
}
class Solution {
public:
int getNandResult(int k, vector<int>& arr, vector<vector<int>>& operations) {
a = arr;
n = a.size();
for (int i = 0; i < k; ++i) build(tr[i], i, 1, 0, n - 1);
int ans = 0;
for (auto& u: operations) {
int type = u[0], x = u[1], y = u[2];
if (type == 0) {
for (int i = 0; i < k; ++i) modify(tr[i], i, 1, x, y);
} else {
int res = 0;
for (int i = 0; i < k; ++i) {
int last = tr[i][1].p;
int start = y >> i & 1;
int odd = 1;
if (last == -1) {
if (x % 2 == 0 || n % 2 == 0) {
odd = 0;
}
} else {
start = 1;
if ((n - 1 - last) % 2 == 0) {
odd = 0;
}
}
if (odd) start ^= 1;
if (start) res |= 1 << i;
}
ans ^= res;
}
}
return ans;
}
};
|
F. 万灵之树
鸽了