leetcode-weekly-contest-296

Problem List

• [1] 极大极小游戏
• [2] 划分数组使最大差为 K
• [3] 替换数组中的元素
• [4] 设计一个文本编辑器

1. 极大极小游戏

1.1 题目描述

给你一个下标从 0 开始的整数数组 nums ，其长度是 2 的幂。

对 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：
输入： nums = [1,3,5,2,4,8,2,2]
输出： 1
解释： 重复执行算法会得到下述数组。
第一轮：nums = [1,5,4,2]
第二轮：nums = [1,4]
第三轮：nums = [1]
1 是最后剩下的那个数字，返回 1 。

示例2：
输入： nums = [3]
输出： 3
解释： 3 就是最后剩下的数字，返回 3 .

1.2 思路

  思路即上述算法过程，第四步的”用 newNums 替换 nums“可以用递归实现，第一步则是在算法开头检测输入数组的元素个数是否为1，若是说明递归完成，返回nums[0]即可。

class Solution {
public:
    int minMaxGame(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return nums[0];      // 第1步
        vector<int> newnums(n/2);
        // 第4步实际上就是第2步和第3步的结合
        for(int i = 0; i < n/2; ++i){
            if(i%2 == 0){               // 第2步
                newnums[i] = min(nums[i*2], nums[i*2+1]);
            }else{                      // 第3步
                newnums[i] = max(nums[i*2], nums[i*2+1]);
            }
        }
        return minMaxGame(newnums);     // 第5步，递归
    }
};

2. 划分数组使最大差为 K

2.1 题目描述

给你一个整数数组 nums 和一个整数 k 。你可以将 nums 划分成一个或多个 子序列 ，使 nums 中的每个元素都 恰好 出现在一个子序列中。

在满足每个子序列中最大值和最小值之间的差值最多为 k 的前提下，返回需要划分的 最少 子序列数目。

子序列 本质是一个序列，可以通过删除另一个序列中的某些元素（或者不删除）但不改变剩下元素的顺序得到。

示例1：

输入： nums = [3,6,1,2,5], k = 2
输出： 2
解释： 可以将 nums 划分为两个子序列 [3,1,2] 和 [6,5] 。
第一个子序列中最大值和最小值的差值是 3 - 1 = 2 。
第二个子序列中最大值和最小值的差值是 6 - 5 = 1 。
由于创建了两个子序列，返回 2 。可以证明需要划分的最少子序列数目就是 2

示例2：

输入： nums = [1,2,3], k = 1
输出： 2
解释：
可以将 nums 划分为两个子序列 [1,2] 和 [3] 。
第一个子序列中最大值和最小值的差值是 2 - 1 = 1 。
第二个子序列中最大值和最小值的差值是 3 - 3 = 0 。
由于创建了两个子序列，返回 2 。注意，另一种最优解法是将 nums 划分成子序列 [1] 和 [2,3] 。

示例3：

输入： nums = [2,2,4,5], k = 0
输出： 3
解释：
可以将 nums 划分为三个子序列 [2,2]、[4] 和 [5] 。
第一个子序列中最大值和最小值的差值是 2 - 2 = 0 。
第二个子序列中最大值和最小值的差值是 4 - 4 = 0 。
第三个子序列中最大值和最小值的差值是 5 - 5 = 0 。
由于创建了三个子序列，返回 3 。可以证明需要划分的最少子序列数目就是 3 。

2.2 思路

  很直接的想法，由于题目只要求子序列中任意元素两两的差值不超过k而不是前一个元素和后一个元素的差值不超过k，前者无序(这里的顺序是指原数组中的顺序)而后者有序。那么可以直接对原数组按升序排序，然后遍历数组，采用 滑动窗口 的思路进行求解即可。

class Solution {
public:
    int partitionArray(vector<int>& nums, int k) {
        int n = nums.size();
        if(n < 2) return n;
        sort(nums.begin(), nums.end());
        // 窗口左端点初始化为第一个元素
        // 窗口截断的条件是当前元素的值大于left+k,即二者差值超过k
        int res = 1, left = nums[0];
        for(int i = 1; i < n; ++i){
            if(nums[i] <= left+k){
                continue;
            }
            left = nums[i];
            res++;
        }
        return res;
    }
};

• 大佬的写法：

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

3. 替换数组中的元素

3.1 题目描述

给你一个下标从 0 开始的数组 nums ，它包含 n 个 互不相同 的正整数。请你对这个数组执行 m 个操作，在第 i 个操作中，你需要将数字 operations[i][0] 替换成 operations[i][1] 。

题目保证在第 i 个操作中：

• operations[i][0] 在 nums 中存在。
• operations[i][1] 在 nums 中不存在。
  请你返回执行完所有操作后的数组。

示例1：

输入： nums = [1,2,4,6], operations = [[1,3],[4,7],[6,1]]
输出： [3,2,7,1]
解释： 我们对 nums 执行以下操作：

• 将数字 1 替换为 3 。nums 变为 [3,2,4,6] 。
• 将数字 4 替换为 7 。nums 变为 [3,2,7,6] 。
• 将数字 6 替换为 1 。nums 变为 [3,2,7,1] 。
  返回最终数组 [3,2,7,1] 。

示例2：

输入： nums = [1,2], operations = [[1,3],[2,1],[3,2]]
输出： [2,1]
解释： 我们对 nums 执行以下操作：

• 将数字 1 替换为 3 。nums 变为 [3,2] 。
• 将数字 2 替换为 1 。nums 变为 [3,1] 。
• 将数字 3 替换为 2 。nums 变为 [2,1] 。
  返回最终数组 [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 中不存在。

3.2 思路

  题目中指出了nums中的数字各不相同，并且在进行操作时，操作后的数在数组中也是不存在的，即操作前后均不存在相同的元素。那么可以直接用一个map来存储元素，key为元素值、val为对应的索引。进行操作时，找到对应key的索引，然后把这个key删去，以operation[i][1]为key、以山删去的key的索引为val重新插入到map中，最后再将map中的元素插入到数组中进行返回即可。

class Solution {
    unordered_map<int, int> m;
public:
    vector<int> arrayChange(vector<int>& nums, vector<vector<int>>& operations) {
        for(int i = 0; i < nums.size(); ++i){
            m[nums[i]] = i;
        }
        for(auto vec: operations){
            int idx = m[vec[0]];
            m.erase(vec[0]);
            m[vec[1]] = idx;
        }
        for(auto it: m){
            nums[it.second] = it.first;
        }
        return nums;
    }
};

• 优化：一样的思路，但是用一个静态数组代替map,减少由于插入和擦除导致复杂度过高的问题。

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

4. 设计一个文本编辑器

4.1 题目描述

请你设计一个带光标的文本编辑器，它可以实现以下功能：

• 添加：在光标所在处添加文本。
• 删除：在光标所在处删除文本（模拟键盘的删除键）。
• 移动：将光标往左或者往右移动。
  当删除文本时，只有光标左边的字符会被删除。光标会留在文本内，也就是说任意时候 0 <= cursor.position <= currentText.length 都成立。

请你实现 TextEditor 类：

• 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 个字符。

4.2 思路

1. 字符串直接模拟

  维护一个全局字符串str用于存放当前的文本，一个整型变量pos用于记录当前光标所在的位置。

• 插入：如果光标位置pos等于文本str的长度，即pos==str.length()时说明待插入字符串时加到当前文本的最后即可，否则则是插在光标位置str.insert(pos, text). 插入后更新光标位置pos += text.length().
• 删除：如果光标位置小于k，说明光标左侧没有足够的字符可供删除，因而文本更新为pos右侧的子字符串，并且将pos置于文本开头；否则说明删除k个字符后文本剩下左右两个子字符串(删掉了中间的字符串),那么更新文本为str = str.substr(0, pos-k) + str.substr(pos),并将光标位置更新为左侧字符串的末尾即pos-k.
• 左移：直接pos-=k,如果pos <= 0说明此时pos越界，则置为0并返回""；否则返回pos左侧字符串(最长为10)

• 右移：直接pos-=k,如果pos >= str.length()说明此时pos越界，则置为str.length(), 并返回pos左侧字符串(最长为10).

  class TextEditor {
      string str;
      int pos;
  public:
      TextEditor() {
          str =  "";
          pos = 0;
      }
      
      void addText(string text) {
          int len = str.length();
          str.insert(pos, text);
          pos += text.length();
      }
      
      int deleteText(int k) {
          int  ans = min(k, pos);
          if(pos < k){
              str = str.substr(pos);
              pos = 0;
          }else{
              str = str.substr(0, pos-k) + str.substr(pos);
              pos -= k;
          }
          return ans;
      }
      
      string cursorLeft(int k) {
          pos -= k;
          if(pos <= 0){
              pos = 0;
              return "";
          }
          return str.substr(pos-min(pos, 10), min(pos, 10));
      }
      
      string cursorRight(int k) {
          pos += k;
          if(pos > len){
              pos = len;
          }
          return str.substr(pos-min(pos, 10), min(pos, 10));
      }
  };

1. 链表模拟

  由于题目中text的长度以及左/右移的次数均小于40，因此可以直接用双向链表来模拟。

• 插入：链表插入比较简单，只要将插入位置前后两个节点的指针域更改为指向新节点即可，c++中直接用insert(cur, ch)即可实现在cur位置上插入ch字符，插入后光标位于插入节点的位置，因而无需对光标进行移动。

• 删除：链表删除也简单，修改待删除节点的前后两个节点的指针域指向并将该节点删除即可，c++中用erase

  class TextEditor {
      list<char> str;
      list<char>::iterator cur;
      string print(){
          string res = "";
          auto it = cur;
          for(int i = 0; i < 10 && it != str.begin(); ++i){
              it = prev(it);
              res += *it;
          }
          int l = 0, r = res.length()-1;
          while(l < r){
              char ch = res[l];
              res[l++] = res[r];
              res[r--] = ch;
          }
          return res;
      }
  public:
      TextEditor() {
          cur = str.begin();
      }
      
      void addText(string text) {
          for(char ch: text){
              str.insert(cur, ch);
          }
      }
      
      int deleteText(int k) {
          auto it = cur;
          int i;
          for(i = k; i >0 && it != str.begin(); --i){
              it = prev(it);
              it = str.erase(it);     // 返回的是被删除后当前位置的迭代器
          }
          return k - i;
      }
      
      string cursorLeft(int k) {
          for(int i = k; i > 0 && cur != str.begin(); --i){
              cur = prev(cur);
          }
          return print();
      }
      
      string cursorRight(int k) {
          for(int i = k; i > 0 && cur != str.end(); --i){
              cur = next(cur);
          }
          return print();
      }
  };

复盘

主要涉及了字符串以及std::list的操作：

1. 字符串操作

• substr(index, len): 获取从index开始的长度为len的子字符串，如果len大于剩余字符串长度，则否则剩余的字符串.
• substr(index): 返回自index开始到字符串末尾的子字符串.
• insert(index, str): 在index位置上插入字符串str.

1. std::list操作

• 插入：
  • insert(): 插入后迭代器位于插入元素的位置上，而原来的迭代器上的元素以及后继节点则均后移一位.
    • insert(it, elem): 在迭代器it的位置上插入新节点，节点元素为elem.
    • insert(it, n, elem): 在迭代器it的位置上连续插入n个elem元素.
  • emplace: 直接构造
    • emplace_back(elem): 在链表的末尾插入元素elem.
    • emplace_front(elem): 在链表的第一个元素前头插入元素elem.
    • emplace(it, elem): 同insert(it, elem).

• 删除：

  • clear(): 清除链表中的所有元素
  • remove(val): 清除链表中所有val的节点
  • remove_if(): 清楚满足条件的节点
  • unique(): 清楚链表中相邻位置相同的节点，仅保留第一个节点
  • erase(): 删除 list 容器中指定位置处的元素(erase(it))，也可以删除容器中某一段的多个元素(erase(it1, it2))
  • pop_back(): 删除链表末尾节点

  • pop_front(): 删除链表起始节点

    remove_if使用示例：

    >#include <iostream> 
    >#include <list> 
    >using namespace std;
    
    >bool odd(int n) {return n%2;}
    
    >void main(){
    list<int> l = {1,2,3,4,5,6,7,8,9};
    l.remove_if(odd);
    >}

• 反转/排序：
  • sort()
  • reverse()
• 移动：
  • advance(it, n): 将迭代器it后移n位，为负则向前移，无返回值.
  • prev(it, n): 与上边的功能类似，n为正则前移，为负则后移，缺省则为1即前移一位， 函数返回的结果为新的迭代器.
  • next(it, n): 与advance一致，但与prev一样有返回值.

    这里的移动函数实际上都是STL标准库中的迭代器辅助函数，定义于<iterator>头文件中并位于std命名空间中. advance和next可以采用任意的迭代器，而prev只能用双向迭代器和随机访问迭代器.

    • 前向迭代器：只可以作it++和++it的操作.
    • 双向迭代器：除了可以作++it、it++的操作，还可以作--it、it--的操作.
    • 随机访问迭代器：拥有双向迭代器的功能外，还可以进行it+=n等操作.

• 其他：
  • distance(p, q): 返回迭代器p后移多少次后与迭代器q一致。
  • iter_swap(p, q): 交换两个迭代器的值.