leetcode 第 296 场算法比赛 排名142/5721

零、背景

这次比赛题目超级简单，最后一题犹豫维护一个双向链表还是双向分块时，浪费了不少时间。

一、极大极小游戏

题意：给一个数组，从前到后两两一组，第一组去最小值，第二组取最大值。
这样，得到的最值可以形成一个新的数组，数组大小与原数组相比减半了。
问不断这样操作，最后得到的长度为 1 的数组的值是多少。

思路：按照题意模拟，直接在原数组上保存值即可。

复杂度：O(n log(n))

二、划分数组使最大差为 K

题意：给一个数组，将数组划分为若干个子序列。
问至少划分多少个子序列，才能使得每个子序列中的最大值与最小值差值不超过 K。

思路：贪心题。
先对数组排序，然后从前到后，不断的寻找满足题意的最长的子数组。
最终子数组的个数就是答案。

三、替换数组中的元素

题意：给一个值互不相同的数组，然后给若干值 a 替换为值 b 的操作。
输出替换若干次后的数组。

思路： map 储存每个值的下标索引，这样替换的时候就可以找到对应的数组下标了。
然后更新 索引和值即可。

四、设计一个文本编辑器

题意：交互题，初始字符串为空，有四个操作。

插入操作：在游标后面插入一个字符串。
删除操作：删除游标左边 k 个字符。
左移操作：游标左移 k 次，并返回移动后，游标前面的字符串（最长为10）。
右移操作：游标右移 k 次，并返回移动后，游标前面的字符串（最长为10）。

思路：模拟题。

最简单的方式是维护一个双向链表，每个节点储存一个字符。

但是我想到一个更方便的操作：双向分块链表。
这样，每个节点储存一个字符串的切片（go 语言中的概念），cpp 就是两个指针。

struct Node{
    Node* pre;
    Node * next;
    const char* start;
    int len;
};

考虑到对一个分块插入或删除时，就对分块进行拆分。
那还不如直接使用普通的链表操作更简单。

所以，最后我实现了一个普通的双向链表过了这道题。

五、最后

这次比赛没啥难度，最后一题建议大家使用双向分块链表做做试试，很有意思的算法。

加油，算法人。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code