因为要准备六级所以最近的题都在外服，lc美服，codeforces来刷。

这样的话，成功的knight了，就九月份之后再见咯！

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.

很简单啊，模拟啊模拟啊模拟哦啊！跟 75双周赛的T2一样

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.

啥意思呢，就是有一个数组，要把它分成最少的子区间，每个子区间要保证他的最大值最小值差小于=k，贪心来一下就好

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

很简单吧，就是可以把所有的同一个值的下表记录起来，然后修改的时候将下标的vector改成另一个新值的后面，并清空。然后模拟哈希表修改nums就行了

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
["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"]

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

坑点：注意一下边界判断把。还有min函数对stl的size（）支持的不太好

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

    }

    void addText(string text) {
        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();
 * obj->addText(text);
 * int param_2 = obj->deleteText(k);
 * string param_3 = obj->cursorLeft(k);
 * string param_4 = obj->cursorRight(k);
 */