跳转至

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

题目描述

给定一个由 正整数 组成的数组 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)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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
}

评论