LeetCode周赛296，难度较低的新手练习场
大家好，日拱一卒，我是梁唐。本文始发于Coder梁
今天是周一，我们照惯例来看看昨天的LeetCode周赛。这次的周赛是上海诺基亚贝尔赞助的，我也不清楚诺基亚贝尔和诺基亚是什么关系……这次的奖励也很有意思，除了前200名有内推机会之外，前50名还能获得校园学创班的机会……
这次的比赛的题目总体感觉比之前的几场要简单一些，考察的算法偏基础，总的说起来还是挺适合新人练手的。如果你对自己的算法能力没有信心的话，不妨尝试着赛后练习一下，说不定这场比赛能够帮你找到信心。
好了， 废话就说到这里，让我们一起来看题吧。
极大极小游戏
给你一个下标从 0 开始的整数数组 nums ，其长度是 2 的幂。
对 nums 执行下述算法：
- 设 n 等于 nums 的长度，如果 n == 1 ，终止 算法过程。否则，创建 一个新的整数数组 newNums ，新数组长度为 n / 2 ，下标从 0 开始。
- 对于满足 0 <= i < n / 2 的每个 偶数 下标 i ，将 newNums[i] 赋值 为 min(nums[2 * i], nums[2 * i + 1]) 。
- 对于满足 0 <= i < n / 2 的每个 奇数 下标 i ，将 newNums[i] 赋值 为 max(nums[2 * i], nums[2 * i + 1]) 。
- 用 newNums 替换 nums 。
- 从步骤 1 开始 重复 整个过程。
执行算法后，返回 nums 中剩下的那个数字。
题解
题目当中给的范围非常小，最多只有1024个数，那么我们随便怎么玩都行。
直接按照题目的意思编写逻辑即可，基本没有难度。
比赛的时候，我脑抽了用的Python，其实C++也一样实现。
```python class Solution: def minMaxGame(self, nums: List[int]) -> int: n = len(nums)
while n > 1:
news = []
for i in range(n // 2):
if i % 2 == 0:
news.append(min(nums[i*2], nums[i*2+1]))
else:
news.append(max(nums[i*2], nums[i*2+1]))
nums = news
n = len(nums)
return nums[0]
```
划分数组使最大差为 K
给你一个整数数组 nums 和一个整数 k 。你可以将 nums 划分成一个或多个 子序列 ，使 nums 中的每个元素都 恰好 出现在一个子序列中。
在满足每个子序列中最大值和最小值之间的差值最多为 k 的前提下，返回需要划分的 最少 子序列数目。
子序列 本质是一个序列，可以通过删除另一个序列中的某些元素（或者不删除）但不改变剩下元素的顺序得到。
题解
这题本身其实难度并不大，但很容易给人误导。比如我比赛的时候一直和子序列较劲，因为子序列要保证当中的元素相对顺序和原来不变。所以当时本能地觉得排序这样会打乱元素顺序的操作铁定不行，接着又要用到的序列尽量少，于是就想要贪心，每次创建一个区间，尽可能多地覆盖剩余的元素。
这样当然是可以的，但极端case会超时。比如k等于0，并且数组当中元素又各不相同的话， 我们需要创建n个区间，每次都要遍历所有元素一次，显然会超时。
就在我思考的时候，这道题已经通过了一千多人。那时候差不多才比赛刚开始15分钟，我当时都要陷入自我怀疑了。后来稍微冷静了一下，觉得一定是有什么我没有发现的trick。只要找到了trick，就看可以解决问题。
那么trick在哪里呢？在于题目的限制条件——子序列。表面上看子序列需要保证元素顺序和原来一样，但实际上在本题当中，子序列当中的相对顺序并不重要，我们不关心子序列当中的元素是如何排列的，我们只关心要用到多少子序列。这个限制条件就是出题人的障眼法，置之不理就可以了。
一旦去掉这个限制，解法就呼之欲出了，我们直接把所有元素排序，然后从小到大遍历一次，计算一下覆盖需要的最少区间即可。
```cpp
class Solution {
public:
int partitionArray(vector
sort(nums.begin(), nums.end());
int last = nums[0];
int ret = 1;
for (int i = 1; i < n; i++) {
if (nums[i] > last + k) {
ret++;
last = nums[i];
}
}
return ret;
}
}; ```
替换数组中的元素
给你一个下标从 0 开始的数组 nums ，它包含 n 个 互不相同 的正整数。请你对这个数组执行 m 个操作，在第 i 个操作中，你需要将数字 operations[i][0] 替换成 operations[i][1] 。
题目保证在第 i 个操作中：
- operations[i][0] 在 nums 中存在。
- operations[i][1] 在 nums 中不存在。
请你返回执行完所有操作后的数组。
题解
看一眼数据范围，元素数量以及操作数量都是1e5这个量级，显然我们直接模拟是一定会超时的。
不难想到，不论如何操作，都不会改变元素的数量。那么，即使我们操作m次，一个数改变了m次，我们也可以等价于看做是只改变了一次。相当于我们把这m次操作进行了合并，合并成了一次操作。我们只需要得到这个合并之后的结果，再对数组当中的元素进行一次操作即可。
所以所有的关键都在于操作的合并上，那么怎么进行合并呢？
不难发现，多次操作之间具有关联关系。比如一次操作是将1变成3，第二次操作是将3变成2，那么等价于将1变成2。那么我们怎么样判断这样的关联关系呢？难道要两两配对进行遍历吗？显然这样也会超时，我们可以使用map来存储变化之间的关系。
对于一次操作，我们假设是从u变成了v。我们使用两个map，一个的key是u，value是v，记录u能变成v，我们把这个map叫做fwd(forward)。另外一个反过来，记录v是由u得到的，这个map叫做bkd(backward)。
当我们遍历得到一个新的操作(u, v)时，我们首先判断bkd[u]是否存在，如果不存在，说明这个操作和之前的操作没有任何关系，我们直接记录：fwd[u]=v; bdk[v] = u。如果存在，那么将fwd[bkd[u]] = v，并且更新bkd：bdk[v] = bkd[u]，最后删除bdk[u]即可。
```cpp
class Solution {
public:
vector
int n = nums.size();
for (int i = 0; i < n; i++) {
int u = nums[i];
if (fwd.count(u)) nums[i] = fwd[u];
}
return nums;
}
}; ```
设计一个文本编辑器
请你设计一个带光标的文本编辑器，它可以实现以下功能：
- 添加：在光标所在处添加文本。
- 删除：在光标所在处删除文本（模拟键盘的删除键）。
- 移动：将光标往左或者往右移动。
当删除文本时，只有光标左边的字符会被删除。光标会留在文本内，也就是说任意时候 0 <= cursor.position <= currentText.length 都成立。
请你实现 TextEditor 类：
- TextEditor() 用空文本初始化对象。
- void addText(string text) 将 text 添加到光标所在位置。添加完后光标在 text 的右边。
- int deleteText(int k) 删除光标左边 k 个字符。返回实际删除的字符数目。
- string cursorLeft(int k) 将光标向左移动 k 次。返回移动后光标左边 min(10, len) 个字符，其中 len 是光标左边的字符数目。
- string cursorRight(int k) 将光标向右移动 k 次。返回移动后光标左边 min(10, len) 个字符，其中 len 是光标左边的字符数目。
题解
这题花里胡哨看起来好像很复杂，但实际上题意非常简单，就是让我们模拟生成一个编辑器。
做算法题有一个小技巧， 题目比较长的问题不一定困难，往往反而比较简单。因为题目越长说明给的信息越多，题目的描述也越清楚。真正的难题反而很短，越短说明信息量越凝练，需要我们做的分析和推理就越多。
回到问题，这题最大的难点在于我们输入文本以及移动光标的时候会导致光标左右两侧内容的变化。如果我们使用字符串来记录光标左右两侧的内容的话，显然这会非常影响性能。光标左侧的字符串还好，我们都是在它的末尾进行插入和删除，我们可以把字符串当做是vector进行push_back和pop_back，这些都是O(1)的操作。
对于光标右侧的内容就比较麻烦了，我们需要在它的头部进行操作。在一个数组头部元素进行增删是最麻烦的，需要移动整个数组或者是拷贝整个数组。
但我们分析一下题目就会发现，其实光标右侧的内容我们只需要记录下来即可，我们需要显示的永远只有光标左侧的结果。所以我们可以将光标右侧的文本进行反向存储，比如LEET|CODE，这里的|表示光标，那么光标右侧实际存储的字符串是EDOC。这样当我们移动光标的时候，就等价于在数组的末尾进行操作了。
其实这题考察的就是对于字符串进行修改的复杂度的理解，只要利用pop_back和push_back都是O(1)的复杂度，就可以很轻易地解出这题。
```cpp class TextEditor { public:
string cl, cr;
int p;
TextEditor() {
p = 0;
}
void addText(string text) {
for (auto c : text) {
cl.push_back(c);
}
}
int deleteText(int k) {
int ret = 0;
// 删除，等价于弹出光标左侧的末尾元素
for (int i = 0; i < k; i++) {
if (cl.empty()) break;
ret++;
cl.pop_back();
}
return ret;
}
string cursorLeft(int k) {
// 向左移动光标，等价于删除光标左侧的内容，插入到右侧
for (int i = 0; i < k; i++) {
if (cl.empty()) break;
char c = cl.back();
cl.pop_back();
cr.push_back(c);
}
string ret = "";
for (int i = max((int) cl.size()-10, 0); i < cl.size(); i++) ret.push_back(cl[i]);
return ret;
}
string cursorRight(int k) {
// 向右移动光标，等价于弹出光标右侧的内容，插入到左侧
for (int i = 0; i < k; i++) {
if (cr.empty()) break;
char c = cr.back();
cr.pop_back();
cl.push_back(c);
}
string ret = "";
for (int i = max((int) cl.size()-10, 0); i < cl.size(); i++) ret.push_back(cl[i]);
return ret;
}
};
/ * Your TextEditor object will be instantiated and called as such: * TextEditor obj = new TextEditor(); * obj->addText(text); * int param_2 = obj->deleteText(k); * string param_3 = obj->cursorLeft(k); * string param_4 = obj->cursorRight(k); / ```
怎么样，这周的题目基本上都没有用到一些比较困难的算法，大多是对一些基础技能和知识的考量。
如果觉得不错，不妨亲自上手练一练吧~
- LeetCode周赛309，米哈游赞助的比赛居然不收简历……
- LeetCode周赛311，中规中矩的裸题大赛……
- 日拱一卒，麻省理工教你信息安全和密码学
- LeetCode周赛301，离大谱，手速场掉分，质量场掉大分……
- 日拱一卒，元编程不是元宇宙，麻省理工教你makefile、依赖管理和CI
- LeetCode周赛300，差点AK，刚拿到的勋章要丢了……
- 日拱一卒，麻省理工教你性能分析，火焰图、系统调用栈，黑科技满满
- 日拱一卒，麻省理工教你Debug，从此debug不再脱发
- 日拱一卒，麻省理工教你学Git，工程师必备技能
- 日拱一卒，配置开发环境不再愁，麻省理工手把手教你
- 日拱一卒，麻省理工CS入门课，命令行这样用也太帅了
- 日拱一卒，麻省理工YYDS，一节课让我学会用vim
- 日拱一卒，麻省理工教你CS基础，那些酷炫无比的命令行工具
- LeetCode周赛297，一小时AK你也可以
- 听说你入行好几年还只会cd和ls，麻省理工开了这门课……
- 日拱一卒，伯克利CS61A完结撒花
- 日拱一卒，伯克利教你用SQL处理数据
- LeetCode周赛296，难度较低的新手练习场
- 日拱一卒，伯克利教你Python核心技术，迭代器和生成器
- 日拱一卒，伯克利CS61A，教你用Python写一个Python解释器