每日一题 2023_1_29_problem1664

题目

给你一个整数数组 nums 。你需要选择 恰好 一个下标（下标从 0 开始）并删除对应的元素。请注意剩下元素的下标可能会因为删除操作而发生改变。

比方说，如果 nums = [6,1,7,4,1] ，那么：

• 选择删除下标 1，剩下的数组为 nums = [6,7,4,1]。
• 选择删除下标 2，剩下的数组为 nums = [6,1,4,1]。
• 选择删除下标 4，剩下的数组为 nums = [6,1,7,4]。

如果一个数组满足奇数下标元素的和与偶数下标元素的和相等，该数组就是一个 $\lceil \text{平衡数组} \rfloor$。

解答

方法一: 动态规划

思路与算法

首先题目给出一个从 $0$ 开始的长度为 $n$ 的整数数组 $nums$, 并且给出 $\lceil \text{平衡数组} \rfloor$ 的定义: 数组中奇数下标元素和偶数下标元素的和相等. 现在我们可以选择一个位置 $i$, $0 \leq i < n$ 的元素删除 (注意删除i之后的下标可能会因此发生改变).我们需要求出所有删除该下标元素后的数组为 $\lceil \text{平衡数组} \rfloor$ 的下标数目.

我们设 $preOdd[i]$ 表示位置, $0 \leq i < n$ 前所有奇数位置元素的和, $preEven[i]$ 表示位置 $i$ 前所有偶数位置元素的和, $sufOdd[i]$ 表示位置 $i$ 后所有奇数位置元素的和, $sufEven[i]$ 表示 $i$后所有偶数位置元素的和, 以下是状态转移方程式:

• 当 $i$ 为奇数时:
  • $preOdd[i + 1] = preOdd[i] + nums[i], i + 1 < n$
  • $sufOdd[i] = sufOdd[i - 1] - nums[i], i - 1 \geq 0$
  • $preEven[i + 1] = preEven[i], i + 1 \leq n$
  • $sufEven[i] = sufEven[i - 1], i - 1 \geq 0$
• 当 $i$ 为偶数时:
  • $preEven[i + 1] = preEven[i] + nums[i], i + 1 < n$
  • $sufEven[i] = suf[i - 1] - nums[i], i - 1 < n$
  • $preOdd[i + 1] = preOdd[i], i + 1 < n$
  • $sufOdd[i] = sufOdd[i - 1], i - 1 \geq 0$

其中边界条件为: 当 $i = 0$ 时, $preOdd[0] = 0$, $preEven[0] = 0$, $sufOdd[0] = \sum_{n}^{2i + 1} nums[2i + 1]$, $sufEven[0] = \sum_{2i}^{n} nums[2i]$.

不失一般性, 现在我们将下标 $i$ 的元素进行删除, 显而易见下表 $i$ 之前的下标元素会成为偶数下表元素, 偶数下标元素会成为奇数下标元素. 所以删除后数组中全部奇数下标元素和为 $preOdd[i] + sufEven[i]$, 若两者相等则说明删除下标 $i$ 后的数组为 $\lceil \text{平衡数组} \rfloor$. 那么我们尝试删除每一个下表 $i$, $0 \leq i < n$, 来统计能生成 $\lceil \text{平衡数组} \rfloor$ 的下标即可. 又因为 $preOdd[i]$, $preEven[i]$, $sufOdd[i]$, $sufEven[i]$ 求解都与前一个数有关, 因此我们可以用 $\lceil \text{滚动数组} \rfloor$ 的技巧来进行优化.

代码

  class Solution {
public:
    int waysToMakeFair(vector<int>& nums) {
        // classic dynamic programming
        int oddpre = 0, evenpre = 0;
        int oddsuf = 0, evensuf = 0;
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (i & 1)
            {
                oddpre += nums[i];
            }
            else
            {
                evenpre += nums[i];
            }
        }
        for (int i = nums.size() - 1; i >= 0; --i)
        {
            if (i & 1)
            {
                oddpre -= nums[i];
            }
            else
            {
                evenpre -= nums[i];
            }
            if (oddpre + oddsuf == evenpre + evensuf)
            {
                ++ans;
            }
            /*** if deleted, then switch
            int tmp = oddsuf;
            oddsuf = evensuf;
            evensuf = tmp;
            if (i & 1)
            {
                oddsuf += nums[i];
            }
            else
            {
                evensuf += nums[i];
            }
            tmp = oddsuf;
            oddsuf = evensuf;
            evensuf = tmp;
            ***/
            //
            if (!(i & 1))
            {
                oddsuf += nums[i];
            }
            else
            {
                evensuf += nums[i];
            }
        }
        return ans;
    }
};

总结

动态规划的简单运用，应该熟练掌握。