# weekly-contest-296

## A

### Statement

Metadata

`nums` 执行下述算法：

1. `n` 等于 `nums` 的长度，如果 `n == 1`终止 算法过程。否则，创建 一个新的整数数组 `newNums` ，新数组长度为 `n / 2` ，下标从 0 开始。
2. 对于满足 `0 <= i < n / 2` 的每个 偶数 下标 `i` ，将 `newNums[i]` 赋值`min(nums[2 * i], nums[2 * i + 1])`
3. 对于满足 `0 <= i < n / 2` 的每个 奇数 下标 `i` ，将 `newNums[i]` 赋值`max(nums[2 * i], nums[2 * i + 1])`
4. `newNums` 替换 `nums`
5. 从步骤 1 开始 重复 整个过程。

``````输入：nums = [1,3,5,2,4,8,2,2]

1 是最后剩下的那个数字，返回 1 。
``````

``````输入：nums = [3]

``````

• `1 <= nums.length <= 1024`
• `1 <= nums[i] <= 109`
• `nums.length``2` 的幂

Metadata

You are given a 0-indexed integer array `nums` whose length is a power of `2`.

Apply the following algorithm on `nums`:

1. Let `n` be the length of `nums`. If `n == 1`, end the process. Otherwise, create a new 0-indexed integer array `newNums` of length `n / 2`.
2. For every even index `i` where `0 <= i < n / 2`, assign the value of `newNums[i]` as `min(nums[2 * i], nums[2 * i + 1])`.
3. For every odd index `i` where `0 <= i < n / 2`, assign the value of `newNums[i]` as `max(nums[2 * i], nums[2 * i + 1])`.
4. Replace the array `nums` with `newNums`.
5. Repeat the entire process starting from step 1.

Return the last number that remains in `nums` after applying the algorithm.

Example 1:

``````Input: nums = [1,3,5,2,4,8,2,2]
Output: 1
Explanation: The following arrays are the results of applying the algorithm repeatedly.
First: nums = [1,5,4,2]
Second: nums = [1,4]
Third: nums = [1]
1 is the last remaining number, so we return 1.
``````

Example 2:

``````Input: nums = [3]
Output: 3
Explanation: 3 is already the last remaining number, so we return 3.
``````

Constraints:

• `1 <= nums.length <= 1024`
• `1 <= nums[i] <= 109`
• `nums.length` is a power of `2`.

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

class Solution {
public:
int minMaxGame(vector<int> &nums) {
int n = nums.size();

while (n > 1) {
vector<int> tmp(n >> 1, 0);

for (int i = 0; i < n / 2; i++) {
if (i % 2 == 0) {
tmp[i] = min(nums[2 * i], nums[2 * i + 1]);
} else {
tmp[i] = max(nums[2 * i], nums[2 * i + 1]);
}
}

nums.swap(tmp);
n >>= 1;
}

return nums[0];
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## B

### Statement

Metadata

``````输入：nums = [3,6,1,2,5], k = 2

``````

``````输入：nums = [1,2,3], k = 1

``````

``````输入：nums = [2,2,4,5], k = 0

``````

• `1 <= nums.length <= 105`
• `0 <= nums[i] <= 105`
• `0 <= k <= 105`

Metadata

You are given an integer array `nums` and an integer `k`. You may partition `nums` into one or more subsequences such that each element in `nums` appears in exactly one of the subsequences.

Return the minimum number of subsequences needed such that the difference between the maximum and minimum values in each subsequence is at most `k`.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Example 1:

``````Input: nums = [3,6,1,2,5], k = 2
Output: 2
Explanation:
We can partition nums into the two subsequences [3,1,2] and [6,5].
The difference between the maximum and minimum value in the first subsequence is 3 - 1 = 2.
The difference between the maximum and minimum value in the second subsequence is 6 - 5 = 1.
Since two subsequences were created, we return 2. It can be shown that 2 is the minimum number of subsequences needed.
``````

Example 2:

``````Input: nums = [1,2,3], k = 1
Output: 2
Explanation:
We can partition nums into the two subsequences [1,2] and [3].
The difference between the maximum and minimum value in the first subsequence is 2 - 1 = 1.
The difference between the maximum and minimum value in the second subsequence is 3 - 3 = 0.
Since two subsequences were created, we return 2. Note that another optimal solution is to partition nums into the two subsequences [1] and [2,3].
``````

Example 3:

``````Input: nums = [2,2,4,5], k = 0
Output: 3
Explanation:
We can partition nums into the three subsequences [2,2], [4], and [5].
The difference between the maximum and minimum value in the first subsequences is 2 - 2 = 0.
The difference between the maximum and minimum value in the second subsequences is 4 - 4 = 0.
The difference between the maximum and minimum value in the third subsequences is 5 - 5 = 0.
Since three subsequences were created, we return 3. It can be shown that 3 is the minimum number of subsequences needed.
``````

Constraints:

• `1 <= nums.length <= 105`
• `0 <= nums[i] <= 105`
• `0 <= k <= 105`

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

class Solution {
public:
int partitionArray(vector<int> &nums, int k) {
sort(nums.begin(), nums.end());
int res = 1;

int l = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] - nums[l] > k) {
l = i;
++res;
}
}

return res;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## C

### Statement

Metadata

• `operations[i][0]` 在 `nums` 中存在。
• `operations[i][1]` 在 `nums` 中不存在。

``````输入：nums = [1,2,4,6], operations = [[1,3],[4,7],[6,1]]

- 将数字 1 替换为 3 。nums 变为 [3,2,4,6] 。
- 将数字 4 替换为 7 。nums 变为 [3,2,7,6] 。
- 将数字 6 替换为 1 。nums 变为 [3,2,7,1] 。

``````

``````输入：nums = [1,2], operations = [[1,3],[2,1],[3,2]]

- 将数字 1 替换为 3 。nums 变为 [3,2] 。
- 将数字 2 替换为 1 。nums 变为 [3,1] 。
- 将数字 3 替换为 2 。nums 变为 [2,1] 。

``````

• `n == nums.length`
• `m == operations.length`
• `1 <= n, m <= 105`
• `nums` 中所有数字 互不相同 。
• `operations[i].length == 2`
• `1 <= nums[i], operations[i][0], operations[i][1] <= 106`
• 在执行第 `i` 个操作时，`operations[i][0]` 在 `nums` 中存在。
• 在执行第 `i` 个操作时，`operations[i][1]` 在 `nums` 中不存在。

Metadata

You are given a 0-indexed array `nums` that consists of `n` distinct positive integers. Apply `m` operations to this array, where in the `ith` operation you replace the number `operations[i][0]` with `operations[i][1]`.

It is guaranteed that in the `ith` operation:

• `operations[i][0]` exists in `nums`.
• `operations[i][1]` does not exist in `nums`.

Return the array obtained after applying all the operations.

Example 1:

``````Input: nums = [1,2,4,6], operations = [[1,3],[4,7],[6,1]]
Output: [3,2,7,1]
Explanation: We perform the following operations on nums:
- Replace the number 1 with 3. nums becomes [3,2,4,6].
- Replace the number 4 with 7. nums becomes [3,2,7,6].
- Replace the number 6 with 1. nums becomes [3,2,7,1].
We return the final array [3,2,7,1].
``````

Example 2:

``````Input: nums = [1,2], operations = [[1,3],[2,1],[3,2]]
Output: [2,1]
Explanation: We perform the following operations to nums:
- Replace the number 1 with 3. nums becomes [3,2].
- Replace the number 2 with 1. nums becomes [3,1].
- Replace the number 3 with 2. nums becomes [2,1].
We return the array [2,1].
``````

Constraints:

• `n == nums.length`
• `m == operations.length`
• `1 <= n, m <= 105`
• All the values of `nums` are distinct.
• `operations[i].length == 2`
• `1 <= nums[i], operations[i][0], operations[i][1] <= 106`
• `operations[i][0]` will exist in `nums` when applying the `ith` operation.
• `operations[i][1]` will not exist in `nums` when applying the `ith` operation.

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <vector>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T& a, const S& b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T& a, const S& b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

const int N = 1e6 + 10;
int f[N];

// 1 2
// 2 3
// 3 1
// 3 2

class Solution {
public:
Solution() {
for (int i = 1; i <= 1e6; i++) {
f[i] = i;
}
}
vector<int> arrayChange(vector<int>& nums, vector<vector<int>>& operations) {
int n = operations.size();

for (int i = n - 1; i >= 0; i--) {
const auto& o = operations[i];
f[o[0]] = f[o[1]];
}

for (auto& a : nums) {
a = f[a];
}

for (const auto& o : operations) {
f[o[0]] = o[0];
}

return nums;
}
};

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````

## D

### Statement

Metadata

• 添加：在光标所在处添加文本。
• 删除：在光标所在处删除文本（模拟键盘的删除键）。
• 移动：将光标往左或者往右移动。

• `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` 是光标左边的字符数目。

``````输入：
["TextEditor", "addText", "deleteText", "addText", "cursorRight", "cursorLeft", "deleteText", "cursorLeft", "cursorRight"]
[[], ["leetcode"], [4], ["practice"], [3], [8], [10], [2], [6]]

[null, null, 4, null, "etpractice", "leet", 4, "", "practi"]

TextEditor textEditor = new TextEditor(); // 当前 text 为 "|" 。（'|' 字符表示光标）
textEditor.addText("leetcode"); // 当前文本为 "leetcode|" 。
textEditor.deleteText(4); // 返回 4
// 当前文本为 "leet|" 。
// 删除了 4 个字符。
textEditor.addText("practice"); // 当前文本为 "leetpractice|" 。
textEditor.cursorRight(3); // 返回 "etpractice"
// 当前文本为 "leetpractice|".
// 光标无法移动到文本以外，所以无法移动。
// "etpractice" 是光标左边的 10 个字符。
textEditor.cursorLeft(8); // 返回 "leet"
// 当前文本为 "leet|practice" 。
// "leet" 是光标左边的 min(10, 4) = 4 个字符。
textEditor.deleteText(10); // 返回 4
// 当前文本为 "|practice" 。
// 只有 4 个字符被删除了。
textEditor.cursorLeft(2); // 返回 ""
// 当前文本为 "|practice" 。
// 光标无法移动到文本以外，所以无法移动。
// "" 是光标左边的 min(10, 0) = 0 个字符。
textEditor.cursorRight(6); // 返回 "practi"
// 当前文本为 "practi|ce" 。
// "practi" 是光标左边的 min(10, 6) = 6 个字符。
``````

• `1 <= text.length, k <= 40`
• `text` 只含有小写英文字母。
• 调用 `addText` ，`deleteText` ，`cursorLeft` 和 `cursorRight` 的 次数不超过 `2 * 104` 次。

Metadata

Design a text editor with a cursor that can do the following:

• Add text to where the cursor is.
• Delete text from where the cursor is (simulating the backspace key).
• Move the cursor either left or right.

When deleting text, only characters to the left of the cursor will be deleted. The cursor will also remain within the actual text and cannot be moved beyond it. More formally, we have that `0 <= cursor.position <= currentText.length` always holds.

Implement the `TextEditor` class:

• `TextEditor()` Initializes the object with empty text.
• `void addText(string text)` Appends `text` to where the cursor is. The cursor ends to the right of `text`.
• `int deleteText(int k)` Deletes `k` characters to the left of the cursor. Returns the number of characters actually deleted.
• `string cursorLeft(int k)` Moves the cursor to the left `k` times. Returns the last `min(10, len)` characters to the left of the cursor, where `len` is the number of characters to the left of the cursor.
• `string cursorRight(int k)` Moves the cursor to the right `k` times. Returns the last `min(10, len)` characters to the left of the cursor, where `len` is the number of characters to the left of the cursor.

Example 1:

``````Input
["TextEditor", "addText", "deleteText", "addText", "cursorRight", "cursorLeft", "deleteText", "cursorLeft", "cursorRight"]
[[], ["leetcode"], [4], ["practice"], [3], [8], [10], [2], [6]]
Output
[null, null, 4, null, "etpractice", "leet", 4, "", "practi"]
Explanation
TextEditor textEditor = new TextEditor(); // The current text is "|". (The '|' character represents the cursor)
textEditor.addText("leetcode"); // The current text is "leetcode|".
textEditor.deleteText(4); // return 4
// The current text is "leet|".
// 4 characters were deleted.
textEditor.addText("practice"); // The current text is "leetpractice|".
textEditor.cursorRight(3); // return "etpractice"
// The current text is "leetpractice|".
// The cursor cannot be moved beyond the actual text and thus did not move.
// "etpractice" is the last 10 characters to the left of the cursor.
textEditor.cursorLeft(8); // return "leet"
// The current text is "leet|practice".
// "leet" is the last min(10, 4) = 4 characters to the left of the cursor.
textEditor.deleteText(10); // return 4
// The current text is "|practice".
// Only 4 characters were deleted.
textEditor.cursorLeft(2); // return ""
// The current text is "|practice".
// The cursor cannot be moved beyond the actual text and thus did not move.
// "" is the last min(10, 0) = 0 characters to the left of the cursor.
textEditor.cursorRight(6); // return "practi"
// The current text is "practi|ce".
// "practi" is the last min(10, 6) = 6 characters to the left of the cursor.
``````

Constraints:

• `1 <= text.length, k <= 40`
• `text` consists of lowercase English letters.
• At most `2 * 104` calls in total will be made to `addText`, `deleteText`, `cursorLeft` and `cursorRight`.

### Solution

``````#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl "\n"
#define fi first
#define se second
#define all(x) begin(x), end(x)
#define rall rbegin(a), rend(a)
#define bitcnt(x) (__builtin_popcountll(x))
#define complete_unique(a) a.erase(unique(begin(a), end(a)), end(a))
#define mst(x, a) memset(x, a, sizeof(x))
#define MP make_pair

using ll = long long;
using ull = unsigned long long;
using db = double;
using ld = long double;
using VLL = std::vector<ll>;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using PLL = std::pair<ll, ll>;

using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template <typename T, typename S>
inline bool chmax(T &a, const S &b) {
return a < b ? a = b, 1 : 0;
}

template <typename T, typename S>
inline bool chmin(T &a, const S &b) {
return a > b ? a = b, 1 : 0;
}

#ifdef LOCAL
#include <debug.hpp>
#else
#define dbg(...)
#endif
// head

struct node {
char c;
node *nx;
node *pre;
node(char c) : c(c), nx(nullptr), pre(nullptr) {}
~node() {}
};

class TextEditor {
public:
node *head, *tail, *cur;
TextEditor() {
head = new node('@');
tail = new node('#');
cur = head;
head->nx = tail;
tail->pre = head;
}

~TextEditor() {
while (head->c != '#') {
auto *tmp = head;
head = head->nx;
delete tmp;
}

if (head) {
delete head;
}
}

void addText(string text) {
for (auto c : text) {
node *n = new node(c);
n->pre = cur;
n->nx = cur->nx;
cur->nx->pre = n;
cur->nx = n;
cur = n;
}
}

int deleteText(int k) {
int res = 0;
auto *nx = cur->nx;
for (int i = 0; i < k && cur->c != '@'; i++) {
++res;
auto *tmp = cur;
cur = cur->pre;
delete tmp;
}

cur->nx = nx;
nx->pre = cur;

return res;
}

string cursorLeft(int k) {
for (int i = 0; i < k && cur->c != '@'; i++) {
cur = cur->pre;
}

return getString();
}

string cursorRight(int k) {
for (int i = 0; i < k && cur->nx->c != '#'; i++) {
cur = cur->nx;
}

return getString();
}

string getString() {
string res = "";
auto *tmp = cur;
for (int i = 0; i < 10 && tmp->c != '@'; i++) {
res += tmp->c;
tmp = tmp->pre;
}

reverse(res.begin(), res.end());
return res;
}
};

/**
* 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);
*/

#ifdef LOCAL

int main() {
return 0;
}

#endif
``````