# Leetcode-weekly-296周赛

## Min Max Game - LeetCode Contest

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.

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.

class Solution {
public:
int minMaxGame(vector<int>& nums) {
vector<int> m ;
while(nums.size() != 0 ){
m.clear();
for (int i = 0 ;i<nums.size()/2;i++){
if(i%2==0){
m.push_back(min(nums[i*2],nums[i*2+1]));
}else{
m.push_back(max(nums[i*2],nums[i*2+1]));
}
}
nums=m;
}
return nums[0];
}
};

## Partition Array Such That Maximum Difference Is K

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.

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.

class Solution {
public:
int partitionArray(vector<int>& nums, int k) {
sort(nums.begin(),nums.end());
int ans=0;
int i =0;
int mi=nums[0],ma=nums[0];
for(;i<nums.size();i++){
mi=min(mi,nums[i]);
ma=max(ma,nums[i]);
if(ma-mi>k){
ans++;
mi=nums[i];
ma=nums[i];
}
}
ans++;
return ans;
}
};

## Replace Elements in an Array

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.

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].

class Solution {
public:
vector<int> arrayChange(vector<int>& nums, vector<vector<int>>& o) {
map<int,vector<int>> m;
for(int i =0 ; i<nums.size();i++){
m[nums[i]].push_back(i);
}
for(auto & op:o){
m[op[1]].insert(m[op[1]].end(),m[op[0]].begin(),m[op[0]].end());
m[op[0]].clear();
}
for(auto & i : m){
for(auto j : i.second){
nums[j]=i.first;
}
}
return nums;
}
};

### (3) Design a Text Editor - LeetCode Contest]

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.
Input
[[], ["leetcode"], [4], ["practice"], [3], [8], [10], [2], [6]]
Output
[null, null, 4, null, "etpractice", "leet", 4, "", "practi"]

j就是模拟个输入框的io，删除，截取功能吧，可以把光标前后分为两个字符串，前面的串就能直接append了，后面的可以用栈，反向进入出来就模拟了。

class TextEditor {
public:
string q,h;
TextEditor() {

}

q+=text;
}

int deleteText(int k) {
int n = min(k,(int)q.size());
for(int i = 0 ;i<n ;i++){
q.pop_back();
}
return n ;
}

string cursorLeft(int k) {
int n =min(k,(int)q.size());
for(int i = 0;i< n ;i++){
h.push_back(q.back());
q.pop_back();
}
return q.substr(q.size()-min((int)q.size(),10),min((int)q.size(),10));
}

string cursorRight(int k) {
int n =min(k,(int)h.size());
for(int i = 0;i< n ;i++){
q.push_back(h.back());
h.pop_back();
}
return q.substr(q.size()-min((int)q.size(),10),min((int)q.size(),10));
}
};

/**
* Your TextEditor object will be instantiated and called as such:
* TextEditor* obj = new TextEditor();
*/