这次周赛的题目感觉简单了一点。
成了三题选手了...😂，第四题被卡在第 68 个用例了，可惜了。
6090. Min Max Game
Analysis
直接按照题目来模拟就行。
Code
这是当时提交通过的代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
int minMaxGame(vector<int>& nums) {
int n = nums.size();
if(n == 1) return nums[0];
while(n != 1) {
n = nums.size();
vector<int> tmp;
for(int i = 0; i < n / 2; i++) {
int t;
if(i % 2 == 0) t = min(nums[2 * i], nums[2 * i + 1]);
else t = max(nums[2 * i], nums[2 * i + 1]);
tmp.push_back(t);
}
nums = tmp;
}
return nums[0];
}
};
改直观一点：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
int minMaxGame(vector<int>& nums) {
int n;
while(n != 1) {
n = nums.size();
vector<int> tmp;
for(int i = 0; i < n / 2; i++) {
int t;
if(i % 2 == 0) t = min(nums[2 * i], nums[2 * i + 1]);
else t = max(nums[2 * i], nums[2 * i + 1]);
tmp.push_back(t);
}
nums = tmp;
}
return nums[0];
}
};
6091. Partition Array Such That Maximum Difference Is K
Analysis
思路是排序 + 贪心。
为了使分成的序列尽可能少，需要将差值满足条件的数尽可能多的放在一个序列中。实际上也就是小数与小一点的数放一个序列，大数与大一点的数放在一个序列。
Code
这是当时提交通过的代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
int partitionArray(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int n = nums.size();
int cnt = 0;
int left = 0, right;
while(left < n) {
int right = left;
while(right < n && nums[right] - nums[left] <= k) right++;
cnt++;
left = right;
}
return cnt;
}
};
这样写有点滑动窗口的味道，其实可以改的更简单一点：1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public:
int partitionArray(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
int n = nums.size(), cnt = 0;
for(int i = 0, j = 0; j < n; j++) {
if(nums[j] - nums[i] > k) {
cnt++;
i = j;
}
}
return cnt + 1;
}
};
6092. Replace Elements in an Array
Analysis
思路是哈希 + 模拟。
因为需要将nums中的operation[i][0]替换成operation[i][1]，为了方便查找元素，用哈希表保存一下nums中元素的下标。每次完成替换操作后，哈希表会删除被替换的那个数字的下标（也可以不删除），然后更新新元素的下标。
Code
这是当时提交通过的代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
vector<int> arrayChange(vector<int>& nums, vector<vector<int>>& operations) {
int n = nums.size(), m = operations.size();
unordered_map<int, int> indices;
for(int i = 0; i < n; i++) {
indices[nums[i]] = i;
}
for(int i = 0; i < m; i++) {
int x = operations[i][0], y = operations[i][1];
int index = indices[x];
nums[index] = y;
indices[y] = index;
indices.erase(x);
}
return nums;
}
};
实际上，这个题可以反着思考。比如有 3 次操作，分别是[1, 3]、[2, 1]和[3, 2]，那么可以从后模拟这些操作，最终 mp 中的元素就是：mp[3] = 2, mp[2] = 1, mp[1] = mp[3] = 2。然后再遍历一次 nums 数组，直接修改对应的元素即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public:
vector<int> arrayChange(vector<int>& nums, vector<vector<int>>& operations) {
unordered_map<int, int> mp;
int m = operations.size();
for(int i = m - 1; i >= 0; i--) {
if(!mp.count(operations[i][1])) mp[operations[i][0]] = operations[i][1];
else mp[operations[i][0]] = mp[operations[i][1]];
}
for(int &i: nums) {
if(mp.count(i)) i = mp[i];
}
return nums;
}
};
逆序遍历 operations 数组的好处在于，如果一个数字会被多次修改，那这个数字再逆序遍历的过程中会直接得到它最终被修改的那个数字，这样就避免了很多不需要的修改。
同时需要说明的是，因为题目限定了 nums 中的所有数字互不相同、operations 中的数字也是在 nums 中不存在的，所以可以直接不加区分的正向修改，也就是最上面的做法，但逆向思考的方法也适用有重复数字的出现。
最后一个题，明天在来~
2296. Design a Text Editor
Analysis
题目意思很清晰，当时的思路是纯模拟。
Code
暴力模拟
这是当时提交的代码：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
77class TextEditor {
string te;
int pos;
public:
TextEditor() : pos(-1){
}
void addText(string text) {
if(pos == -1) {
pos = text.length();
for(int i = 0; i < te.size(); i++) {
text.push_back(te[i]);
}
te = text;
} else if(pos == te.length()) {
te += text;
pos = te.length();
} else {
string tmp = "";
for(int i = 0; i < pos; i++) {
tmp.push_back(te[i]);
}
tmp += text;
int t = pos;
pos = tmp.length();
while(t < te.length()) {
tmp.push_back(te[t]);
t++;
}
te = tmp;
}
}
int deleteText(int k) {
int cnt = 0;
for(int i = 0; i < k; i++) {
if(pos > 0) {
te.erase(te.begin() + pos - 1);
pos--;
cnt++;
} else break;
}
return cnt;
}
string cursorLeft(int k) {
string tmp = "";
pos -= k;
if(pos < 0) {
pos = -1;
return tmp;
}
int tpos = pos - 1, i = 10;
while(tpos >= 0 && i > 0) {
tmp.push_back(te[tpos]);
tpos--;
i--;
}
reverse(tmp.begin(), tmp.end());
return tmp;
}
string cursorRight(int k) {
string tmp = "";
if(pos == -1) pos = k;
else pos += k;
if(pos > te.length()) pos = te.length();
int tpos = pos - 1, i = 10;
while(tpos >= 0 && i > 0) {
tmp.push_back(te[tpos]);
tpos--;
i--;
}
reverse(tmp.begin(), tmp.end());
return tmp;
}
};
纯纯的模拟思路，死在第 68 个用例的原因是写了很多输出语句来调试代码（Leetcode 返回的错误信息是超出输出限制）。删除多余的输出语句后，还是死在了第 72 个用例，原因是超时了，想想写了这么多 reverse，不超时怪了。
这个题用模拟确确实实是可以做出来的，只是我的思路有点问题，参考了别人的暴力解法：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
33class TextEditor {
public:
TextEditor() : curpos(0) {}
void addText(string text) {
te.insert(curpos, text);
curpos += text.length();
}
int deleteText(int k) {
int pos = max(0, curpos - k);
int num = curpos - pos;
text.erase(pos, num);
curpos = pos;
return num;
}
string cursorLeft(int k) {
curpos = max(0, curpos - k);
int num = min(10, curpos);
return te.substr(curpos - num, num);
}
string cursorRight(int k) {
int len = te.length();
curpos = min(len, curpos + k);
int num = min(10, curpos);
return te.substr(curpos - num, num);
}
private:
string te;
int curpos;
};
不得不说，还是自己 API 用的不熟练...
实际上，这个题的正确做法应该是用双向链表或者栈来做。
链表模拟
为什么要使用双向链表？因为需要左移或右移光标，双向链表可以很容易的完成这个操作。
先考虑链表创建的过程中需要的东西。
首先是结点的定义和构造函数：1
2
3
4
5struct Node {
char ch;
Node *pre, *next;
Node(char _ch): ch(_ch), pre(nullptr), next(nullptr){}
};
创建链表肯定要插入结点：1
2
3
4
5
6
7Node* insert(Node* pos, Node* node) {
node->pre = pos;
node->next = pos->next;
node->pre->next = node;
node->next->pre = node;
return node;
}
题目还要求要删除，所以删除结点的操作也需要：1
2
3
4void remove(Node* pos) {
pos->pre->next = pos->next;
pos->next->pre = pos->pre;
}
偷下懒，不做真正的删除，只断链...（实际项目中可别这样干）
接下来要考虑的问题就是 TextEditor 需要什么。首先肯定需要一个光标位置cur，这个指针指向光标位置左边的第一个结点。既然是链表，不妨创建一个头（哑）结点来方便插入。1
2
3
4
5
6
7
8
9
10class TextEditor {
public:
TextEditor() {
head = new Node();
head->pre = head->next = head;
cur = head;
}
private:
Node *cur, *head;
}
之所以把头结点的指向自身，是为了方便后面移动光标的操作，注意整个链表是成环的。
插入与删除文本就很简单了：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16void addText(string text) {
for(char ch: text) {
Node *tmp = new Node(ch);
cur = insert(cur, tmp);
}
}
int deleteText(int k) {
int tmp = k;
while(k && cur != head) {
cur = cur->pre;
remove(cur->next);
k--;
}
return tmp - k;
}
光标左移与右移的操作都需要返回一段文本，不妨把这个功能封装起来，让左移与右移只完成移动的功能。
返回的字符串长度是 10 和光标左边字符数之间的最小值。因为前面让头结点指向了自身，所以可以让头结点作为左边最小字符的边界条件。另外，别忘了要翻转字符串。1
2
3
4
5
6
7
8
9
10
11
12string text() {
Node *p = cur;
string tmp = "";
int k = 10;
while(k && p != head) {
tmp.push_back(p->ch);
k--;
p = p->pre;
}
reverse(tmp.begin(), tmp.end());
return tmp;
}
然后是左移操作，光标最多只能移动到头结点处：1
2
3
4
5
6
7string cursorLeft(int k) {
while(k && cur != head) {
cur = cur->pre;
k--;
}
return text();
}
最后是右移，光标只能移动到最后一个结点处，同样可以用最后一个结点的next是否是头结点来判断是否到了链表末尾：1
2
3
4
5
6
7string cursorRight(int k) {
while(k && cur->next != head) {
cur = cur->next;
k--;
}
return text();
}
合并：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
72class TextEditor {
public:
struct Node {
char ch;
Node *pre, *next;
Node(){}
Node(char _ch): ch(_ch), pre(nullptr), next(nullptr){}
};
Node* insert(Node* pos, Node* node) {
node->pre = pos;
node->next = pos->next;
node->pre->next = node;
node->next->pre = node;
return node;
}
void remove(Node* pos) {
pos->pre->next = pos->next;
pos->next->pre = pos->pre;
}
TextEditor() {
head = new Node();
head->pre = head->next = head;
cur = head;
}
void addText(string text) {
for(char ch: text) {
Node *tmp = new Node(ch);
cur = insert(cur, tmp);
}
}
int deleteText(int k) {
int tmp = k;
while(k && cur != head) {
cur = cur->pre;
remove(cur->next);
k--;
}
return tmp - k;
}
string text() {
Node *p = cur;
string tmp = "";
int k = 10;
while(k && p != head) {
tmp.push_back(p->ch);
k--;
p = p->pre;
}
reverse(tmp.begin(), tmp.end());
return tmp;
}
string cursorLeft(int k) {
while(k && cur != head) {
cur = cur->pre;
k--;
}
return text();
}
string cursorRight(int k) {
while(k && cur->next != head) {
cur = cur->next;
k--;
}
return text();
}
private:
Node *cur, *head;
};
如果是 C++ 的话，可以用 STL 内的 list 来完成，思路是一致的：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
45class TextEditor {
private:
list<char> l;
list<char>::iterator cur = l.begin();
public:
TextEditor() {}
void addText(string text) {
for(char ch: text) {
l.insert(cur, ch);
}
}
int deleteText(int k) {
int k0 = k;
for(; k && cur != l.begin(); k--) {
cur = l.erase(prev(cur));
}
return k0 - k;
}
string text() {
string tmp;
auto it = cur;
for(int k = 10; k && it != l.begin(); k--) {
it = prev(it);
tmp.push_back(*it);
}
reverse(tmp.begin(), tmp.end());
return tmp;
}
string cursorLeft(int k) {
for(; k && cur != l.begin(); k--) {
cur = prev(cur);
}
return text();
}
string cursorRight(int k) {
for(; k && cur != l.end(); k--) {
cur = next(cur);
}
return text();
}
};
栈模拟
准确来说，应该是用双栈来模拟，说的更直观一点就是对顶栈，也就是这两个栈的栈顶是拼在一起的，这样题目要求的光标位置就是这两个栈对顶的位置，而移动光标的操作就是两个栈来回倒的过程了。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
54class TextEditor {
private:
stack<char> left, right;
public:
TextEditor() {}
void addText(string text) {
for(char ch: text) {
left.push(ch);
}
}
int deleteText(int k) {
int k0 = k;
while(k && !left.empty()) {
left.pop();
k--;
}
return k0 - k;
}
string text() {
int k = 10;
string tmp;
while(k && !left.empty()) {
tmp.push_back(left.top());
k--;
left.pop();
}
reverse(tmp.begin(), tmp.end());
for(char &ch: tmp) {
left.push(ch);
}
return tmp;
}
string cursorLeft(int k) {
while(k && !left.empty()) {
k--;
right.push(left.top());
left.pop();
}
return text();
}
string cursorRight(int k) {
while(k && !right.empty()) {
k--;
left.push(right.top());
right.pop();
}
return text();
}
};
为了更好的使用 API，其实直接用 string 容器来当作栈更好。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
39class TextEditor {
string left, right;
public:
TextEditor() {
left = right = "";
}
void addText(string text) {
left += text;
}
int deleteText(int k) {
int k0 = k;
for(; k && left.length() > 0; k--) {
left.pop_back();
}
return k0 - k;
}
string cursorLeft(int k) {
if(left.length() < k) k = left.length();
for(int i = 0; i < k; i++) {
right.push_back(left.back());
left.pop_back();
}
string ans(left.end() - min(10, (int)left.length()), left.end());
return ans;
}
string cursorRight(int k) {
if(right.length() < k) k = right.length();
for(int i = 0; i < k; i++) {
left.push_back(right.back());
right.pop_back();
}
string ans(left.end() - min(10, (int)left.length()), left.end());
return ans;
}
};
Summary
这次周赛比较简单，没 AK 说明自己还是太弱了...😂
最后一个题挺不错的，解法挺多的，虽然没有卡掉暴力解法，但是题目倒是很能打开思路，难度算在中等比较好。
第 2、3 题算是中等题中的简单题了...
