Leetcode weekly buckle race 296

Weekly portal

ranking 20, Big points ！

Minimax game

Ideas ： simulation , Modify in place

Time complexity ：$O(n\ast \lg n)$

Spatial complexity ：$O(n)$

Only half of the elements are reserved for each round of operation , And each operation only depends on two adjacent elements , Independent of previous elements . Therefore, you can simulate the operation process on the original array . See code Notes for details .

class Solution {
    
public:
    int minMaxGame(vector<int>& nums) {
    
        while (nums.size() > 1) {
    
            //  Enumerate the subscripts of the new array  i, from  0  To  n/2
            for (int i = 0; i*2 < nums.size(); i++) {
    
                if (i&1) {
    
                    //  The subscript of the new array is odd , Take the larger of the two 
                    nums[i] = max(nums[i*2], nums[i*2+1]);
                } else {
    
                    //  The subscript of the new array is odd , Take the smaller of the two 
                    nums[i] = min(nums[i*2], nums[i*2+1]);
                }
            }
            //  here  nums  It is already a new array , Only the first half of the elements are meaningful , Reset size .
            nums.resize(nums.size()/2);
        }
        return nums[0];
    }
};

Divide the array so that the maximum difference is K

Ideas ： Sort , greedy , Double pointer

Time complexity ：$O(n\lg n)$

Spatial complexity ：$O(n)$

Let the smallest element in the whole array be $x$, Then place the value at $[x,x+k]$ It is obviously optimal for the elements in the same sequence . For the remaining elements , The partitioning strategy still applies .

On the implementation , But first of all, I will nums Sort , Make the elements in the subsequence in nums Are all adjacent . Then use the double pointer to $O(n)$ The time complexity to get the answer .

class Solution {
    
public:
    int partitionArray(vector<int>& nums, int k) {
    
        //  Sort in ascending order first , Make the elements of the subsequence in  nums  It's all adjacent .
        sort(nums.begin(), nums.end());
        
        //  use  anw  Record answer . At the beginning of the , It has not been divided, so there is only one   Sequence .
        int anw = 1;
        
        // pre  Is the smallest element of the current subsequence  nums  Subscript in 
        //  from  pre  To  n  enumeration  i, Find the maximum value that can be put into the current sequence .
        for (int pre = 0, i = 0; i < nums.size(); i++) {
    
            if (nums[i] - nums[pre] > k) {
    
                //  Out of range , It shows that a new subsequence needs to be divided .
                pre = i;
                anw++;
            }
        }
        return anw;
    }
};

Replace elements in an array

Ideas ： Hashtable

Time complexity ：$O(n+m)$

Spatial complexity ：$O(n)$

Because in the whole process , There are no duplicate elements in the array , So available unordered_map Save the mapping relationship between the element and its position during the modification process .

In every operation , The logic for updating the position of new and old elements is also clear ：

• The new element is in the same position as the old element .
• Old element from unordered_map Delete from .

After modification , You can use unordered_map restructure nums.

class Solution {
    
public:
    vector<int> arrayChange(vector<int>& nums, vector<vector<int>>& operations) {
    
        unordered_map<int, int> pos;
        //  Initialize the mapping relationship between elements and positions 
        for (int i = 0; i < nums.size(); i++) {
    
            pos[nums[i]] = i;
        }
        for (const auto &op : operations) {
    
            //  The new element is in the same position as the old element 
            pos[op[1]] = pos[op[0]];
            //  Delete old element 
            pos.erase(op[0]);
        }
        
        //  Refactoring arrays 
        for (auto p : pos) {
    
            nums[p.second] = p.first;
        }
        
        return nums;
    }
};

Design a text editor

Ideas ： simulation

Time complexity ：

• addText：$O(|text|)$
• deleteText：$O(k)$
• cursorLeft：$O(k)$
• cursorRight：$O(k)$

Spatial complexity ：$O(n)$,$n$ During operation , The longest length a text can reach .

Use two strings prefix and suffix Store the data before and after the cursor respectively , The part after the cursor is stored in reverse order suffix.

such as ,leet|code Such a text ,prefix and suffix The data are as follows ：

• prefix = "leet"
• suffix = "edoc"

On the basis of the above storage methods , The four operations can be implemented as follows ：

• addText： Add to prefix The tail .
• deleteText： Delete prefix At the end of the $k$ Characters .
• cursorLeft： take prefix At the end of the $k$ Characters are moved to suffix The tail .
• cursorRight： take suffix At the end of the $k$ Characters are moved to prefix The tail .

The complete code is as follows ：

class TextEditor {
    
    string prefix;
    string suffix;
public:
    TextEditor() {
    
    }
    
    void addText(string text) {
    
        prefix.append(text.c_str(), text.size());
    }
    
    int deleteText(int k) {
    
        if (k > prefix.size()) {
    
            k = prefix.size();
        }
        prefix.resize(prefix.size()-k);
        return k;
    }
    
    string cursorLeft(int k) {
    
        while (k && prefix.size()) {
    
            k--;
            suffix.append(1, *prefix.rbegin());
            prefix.resize(prefix.size()-1);
        }
        if (prefix.size() <= 10) {
    
            return prefix;
        }
        return prefix.substr(prefix.size()-10);
    }
    
    string cursorRight(int k) {
    
        while (k && suffix.size()) {
    
            k--;
            prefix.append(1, *suffix.rbegin());
            suffix.resize(suffix.size()-1);
        }
        if (prefix.size() <= 10) {
    
            return prefix;
        }
        return prefix.substr(prefix.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); */