5147. 递减元素使数组呈锯齿状

给你一个整数数组 nums，每次 操作 会从中选择一个元素并 将该元素的值减少 1。

如果符合下列情况之一，则数组 A 就是 锯齿数组：

  • 每个偶数索引对应的元素都大于相邻的元素，即 A[0] > A[1] < A[2] > A[3] < A[4] > ...
  • 或者，每个奇数索引对应的元素都大于相邻的元素，即 A[0] < A[1] > A[2] < A[3] > A[4] < ...

返回将数组 nums 转换为锯齿数组所需的最小操作次数。

<—more—>

示例 1：

  1. 输入：nums = [1,2,3]
  2. 输出：2
  3. 解释：我们可以把 2 递减到 0，或把 3 递减到 1。

示例 2：

输入：nums = [9,6,1,6,2]
输出：4

提示：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 1000

思路：

分两次判断，一次判断情况1，也就是偶数索引大于奇数索引，一次判断情况2。小心越界就可以了。

class Solution0 {
public:
    int movesToMakeZigzag(vector<int>& nums) {
        if (nums.size() <= 1)
            return 0;
        int res1 = 0;
        for (int i = 0; i < nums.size(); i+=2)
        {
            int min_nearst = -1;
            if (i + 1 < nums.size() && i - 1 >= 0)
                min_nearst = min(nums[i + 1], nums[i - 1]);
            else if (i + 1 < nums.size())
                min_nearst = nums[i + 1];
            else if (i - 1 >= 0)
                min_nearst = nums[i - 1];
            res1 += max(nums[i] - min_nearst + 1, 0);
        }
        int res2 = 0;
        for (int i = 1; i < nums.size(); i += 2)
        {
            int min_nearst = -1;
            if (i + 1 < nums.size() && i - 1 >= 0)
                min_nearst = min(nums[i + 1], nums[i - 1]);
            else if (i + 1 < nums.size())
                min_nearst = nums[i + 1];
            else if (i - 1 >= 0)
                min_nearst = nums[i - 1];
            res2 += max(nums[i] - min_nearst + 1, 0);
        }
        return min(res1, res2);
    }
};

5148. 二叉树着色游戏

有两位极客玩家参与了一场「二叉树着色」的游戏。游戏中，给出二叉树的根节点 root，树上总共有 n 个节点，且 n 为奇数，其中每个节点上的值从 1 到 n 各不相同。

游戏从「一号」玩家开始（「一号」玩家为红色，「二号」玩家为蓝色），最开始时，

「一号」玩家从 [1, n] 中取一个值 x（1 <= x <= n）；

「二号」玩家也从 [1, n] 中取一个值 y（1 <= y <= n）且 y != x。

「一号」玩家给值为 x 的节点染上红色，而「二号」玩家给值为 y 的节点染上蓝色。

之后两位玩家轮流进行操作，每一回合，玩家选择一个他之前涂好颜色的节点，将所选节点一个 未着色 的邻节点（即左右子节点、或父节点）进行染色。

如果当前玩家无法找到这样的节点来染色时，他的回合就会被跳过。

若两个玩家都没有可以染色的节点时，游戏结束。着色节点最多的那位玩家获得胜利 ✌️。

现在，假设你是「二号」玩家，根据所给出的输入，假如存在一个 y 值可以确保你赢得这场游戏，则返回 true；若无法获胜，就请返回 false。

示例：

weekly contest 148 - 图1

输入：root = [1,2,3,4,5,6,7,8,9,10,11], n = 11, x = 3
输出：True
解释：第二个玩家可以选择值为 2 的节点。

提示：

  • 二叉树的根节点为 root，树上由 n 个节点，节点上的值从 1 到 n 各不相同。
  • n 为奇数。
  • 1 <= x <= n <= 100

思路：

首先最重要的是读懂题目。开局时候，一号玩家和二号玩家各选择一个节点，然后每一回合，玩家选择一个他之前涂好颜色的节点，将所选节点一个未着色的邻节点（即左右子节点、或父节点）进行染色。

（以下内容都是废话，如果读懂题目的人可以无视，因为我一开始以为选择的节点只能是上次自己选择节点的邻节点，而不是选择过的节点的邻节点，所以绕了半天） 所以玩家在之后的环节选择节点的时候，只要是之前自己选择过的节点的邻节点就可以选择。比如玩家A在选了节点3之后，接下来可以选择1、6、7之间的一个。假设接下来选了节点6，那么之后可以选择1、7之中的一个，而不是没得选。

因此假设一号玩家选择了点A，那么点A的邻节点会有1、2、3个。

  • 一号玩家选择节点8：此时只有一个邻节点4，这是二号玩家选择邻节点4，获胜
  • 一号玩家选择节点1：此时有两个邻节点，2和3。如果二号玩家选择3，则失败；如果选择2，则获胜。选择的依据是以节点2为根节点的子树大小比节点3为根节点的子树大小要大，因此选大的那个
  • 一号玩家选择节点3：此时有三个邻节点，1、6和7。同上一种情况，如果选6或者7，则失败；选1，则获胜

我的想法是分情况判断，分别是一号玩家首先选择的节点有父节点和没有父节点两种情况。

  • 如果没有父节点，则一号玩家选择的节点是整个树的根节点，此时二号玩家可以选择左右子树其中的一个，选择策略是选最大的那个
  • 如果有父节点，则二号玩家可以选择左子树，右子树，或者该节点的父节点。如果选择左右子树，那么二号玩家可以染色的最多数量就是左右子树的大小，如果选择父节点，那么二号玩家可以染色的最多数量就是整个树的大小 - 以一号玩家选择节点为根节点的子树大小。

代码：

class Solution {
public:
    bool btreeGameWinningMove(TreeNode* root, int n, int x) {
        if (root->val == x) // 一号玩家选择节点为根节点的情况
        {
            int len = max(size(root->left), size(root->right));
            return len > (n - len);
        }
        else
        {
            TreeNode* player1 = new TreeNode(-1);
            player1 = find(root, x);
            int len = max(max(size(player1->left), size(player1->right)), n - size(player1));
            return len > (n - len);
        }
    }

    TreeNode* find(TreeNode* root, int x) // 返回val为x的节点
    {
        if (!root)
            return nullptr;
        if (root->val == x)
            return root;
        else
        {
            TreeNode* find_left = find(root->left, x);
            TreeNode* find_right = find(root->right, x);
            if (find_left)
                return find_left;
            if (find_right)
                return find_right;
            return nullptr;
        }
    }

    int size(TreeNode* root) // 求树大小
    {
        if (!root)
            return 0;
        else
            return 1 + size(root->left) + size(root->right);
    }
};

5149. 快照数组

实现支持下列接口的「快照数组」- SnapshotArray：

  • SnapshotArray(int length) - 初始化一个与指定长度相等的 类数组 的数据结构。初始时，每个元素都等于 0。
  • void set(index, val) - 会将指定索引 index 处的元素设置为 val。
  • int snap() - 获取该数组的快照，并返回快照的编号 snap_id（快照号是调用 snap() 的总次数减去 1）。
  • int get(index, snap_id) - 根据指定的 snap_id 选择快照，并返回该快照指定索引 index 的值。

示例：

输入：["SnapshotArray","set","snap","set","get"]
     [[3],[0,5],[],[0,6],[0,0]]
输出：[null,null,0,null,5]
解释：
SnapshotArray snapshotArr = new SnapshotArray(3); // 初始化一个长度为 3 的快照数组
snapshotArr.set(0,5);  // 令 array[0] = 5
snapshotArr.snap();  // 获取快照，返回 snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // 获取 snap_id = 0 的快照中 array[0] 的值，返回 5

提示：

  • 1 <= length <= 50000
  • 题目最多进行50000 次set，snap，和 get的调用 。
  • 0 <= index < length
  • 0 <= snap_id <我们调用 snap() 的总次数
  • 0 <= val <= 10^9

思路：

首先，排除暴力法，也就是每snap一次保存一次array的方法，会爆内存。

再次，我想到了保存每次改动的内容，但是这种方法需要一个初始数组，get的时候要用初始数组加上改动的内容来获取值，会超时。

最后没做出来，看了一下前几名的做法。

大家都用了同一种做法，就是对snap和set分别设置一个计数器snap_cnt和set_cnt进行计数，每进行一次snap或者set，都要给对应的计数器进行加1操作，同时设置一个vector<int> snap_log来保存每次snap时候的当前set_cnt，每次snap的时候，就把当前的set_cntpush到snap_log中。这样如果要进行get操作的时候，根据snap_id就可以索引到已经做过的改动。

还需要一个数据结构来保存做过的改动，这里使用vector<vector<pair<int, int>>> history（c++这个语法真的好长啊。。）每次set的时候，把相关的改动保存到history中。history的长度和初始化的数组长度相同，history[index]对应数组在index索引上的历史修改内容，pair<int, int>保存{set_cnt, val}。

但是这里有个trick，就是snap_cnt是多余的，因为完全可以通过snap_log.size()计算得到。

代码：

class SnapshotArray {
private:
    using pii = pair<int, int>;
    vector<vector<pii>> _history;
    vector<int> _snap_log;
    int _set_cnt = 0;
public:
    SnapshotArray(int length) {
        _history.resize(length);
        _snap_log.clear();
        _set_cnt = 0;
        for (auto &it : _history)
        {
            it.clear();
            it.push_back(pii(0, 0));
        }
    }

    void set(int index, int val) {
        _set_cnt++;
        _history[index].push_back(make_pair(_set_cnt, val));
    }

    int snap() {
        _snap_log.push_back(_set_cnt);
        return _snap_log.size()-1;
    }

    int get(int index, int snap_id) {
        int set_index = _snap_log[snap_id];
        return (upper_bound(_history[index].begin(), _history[index].end(), make_pair(set_index , -1), [](pii a, pii b) {return a.first < b.first; })-1)->second;
    }
};

5150. 段式回文

不会做