Question

2422. 使用合并操作将数组转换为回文序列

English Version

题目描述

给定一个由 正整数 组成的数组 nums。

可以对阵列执行如下操作，次数不限:

• 选择任意两个 相邻 的元素并用它们的 和 替换 它们。
  • 例如，如果 nums = [1,2,3,1]，则可以应用一个操作使其变为 [1,5,1]。

返回_将数组转换为 回文序列 所需的 最小 操作数。_

 

示例 1:

输入: nums = [4,3,2,1,2,3,1]
输出: 2
解释: 我们可以通过以下 2 个操作将数组转换为回文:
- 在数组的第 4 和第 5 个元素上应用该操作，nums 将等于 [4,3,2,3,3,1].
- 在数组的第 5 和第 6 个元素上应用该操作，nums 将等于 [4,3,2,3,4].
数组 [4,3,2,3,4] 是一个回文序列。
可以证明，2 是所需的最小操作数。

示例 2:

输入: nums = [1,2,3,4]
输出: 3
解释: 我们在任意位置进行 3 次运算，最后得到数组 [10]，它是一个回文序列。

 

提示:

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 106

解法

方法一：贪心 + 双指针

定义两个指针 $i$ 和 $j$，分别指向数组的首尾，用变量 $a$ 和 $b$ 分别表示首尾两个元素的值，变量 $ans$ 表示操作次数。

如果 $a \lt b$，我们将指针 $i$ 向右移动一位，即 $i \leftarrow i + 1$，然后将 $a$ 加上指针 $i$ 指向的元素的值，即 $a \leftarrow a + nums[i]$，同时将操作次数加一，即 $ans \leftarrow ans + 1$。

如果 $a \gt b$，我们将指针 $j$ 向左移动一位，即 $j \leftarrow j - 1$，然后将 $b$ 加上指针 $j$ 指向的元素的值，即 $b \leftarrow b + nums[j]$，同时将操作次数加一，即 $ans \leftarrow ans + 1$。

否则，说明 $a = b$，此时我们将指针 $i$ 向右移动一位，即 $i \leftarrow i + 1$，将指针 $j$ 向左移动一位，即 $j \leftarrow j - 1$，并且更新 $a$ 和 $b$ 的值，即 $a \leftarrow nums[i]$ 以及 $b \leftarrow nums[j]$。

循环上述过程，直至指针 $i \ge j$，返回操作次数 $ans$ 即可。

时间复杂度 $O(n)$，其中 $n$ 为数组的长度。空间复杂度 $O(1)$。

class Solution:
  def minimumOperations(self, nums: List[int]) -> int:
    i, j = 0, len(nums) - 1
    a, b = nums[i], nums[j]
    ans = 0
    while i < j:
      if a < b:
        i += 1
        a += nums[i]
        ans += 1
      elif b < a:
        j -= 1
        b += nums[j]
        ans += 1
      else:
        i, j = i + 1, j - 1
        a, b = nums[i], nums[j]
    return ans

class Solution {
  public int minimumOperations(int[] nums) {
    int i = 0, j = nums.length - 1;
    long a = nums[i], b = nums[j];
    int ans = 0;
    while (i < j) {
      if (a < b) {
        a += nums[++i];
        ++ans;
      } else if (b < a) {
        b += nums[--j];
        ++ans;
      } else {
        a = nums[++i];
        b = nums[--j];
      }
    }
    return ans;
  }
}

class Solution {
public:
  int minimumOperations(vector<int>& nums) {
    int i = 0, j = nums.size() - 1;
    long a = nums[i], b = nums[j];
    int ans = 0;
    while (i < j) {
      if (a < b) {
        a += nums[++i];
        ++ans;
      } else if (b < a) {
        b += nums[--j];
        ++ans;
      } else {
        a = nums[++i];
        b = nums[--j];
      }
    }
    return ans;
  }
};

func minimumOperations(nums []int) int {
  i, j := 0, len(nums)-1
  a, b := nums[i], nums[j]
  ans := 0
  for i < j {
    if a < b {
      i++
      a += nums[i]
      ans++
    } else if b < a {
      j--
      b += nums[j]
      ans++
    } else {
      i, j = i+1, j-1
      a, b = nums[i], nums[j]
    }
  }
  return ans
}