526互联

[LeetCode] 2422. Merge Operations to Turn Array Into a Palindrome

发布时间 2023-07-20 04:35:26作者: CNoodle

You are given an array nums consisting of positive integers.

You can perform the following operation on the array any number of times:

  • Choose any two adjacent elements and replace them with their sum.
    • For example, if nums = [1,2,3,1], you can apply one operation to make it [1,5,1].

Return the minimum number of operations needed to turn the array into a palindrome.

Example 1:

Input: nums = [4,3,2,1,2,3,1]
Output: 2
Explanation: We can turn the array into a palindrome in 2 operations as follows:
- Apply the operation on the fourth and fifth element of the array, nums becomes equal to [4,3,2,3,3,1].
- Apply the operation on the fifth and sixth element of the array, nums becomes equal to [4,3,2,3,4].
The array [4,3,2,3,4] is a palindrome.
It can be shown that 2 is the minimum number of operations needed.

Example 2:

Input: nums = [1,2,3,4]
Output: 3
Explanation: We do the operation 3 times in any position, we obtain the array [10] at the end which is a palindrome.

Constraints:

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

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

题意是给一个 nums 数组，你只能合并两个相邻的数字并用其加和代替，求需要几次操作能使最后的 nums 成为一个回文序列。

思路是贪心 + 双指针。从数组的左右两边开始看，

  • 如果 nums[left] == nums[right]，两边数字一样，left++, right--，继续比较中间的元素
  • 如果 nums[left] != nums[right]，两边数字不一样，此时需要合并，谁较小就让谁与其邻居元素合并，并移动指针
  • 当 left 指针与 right 指针相遇的时候，返回一共合并了几次

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public int minimumOperations(int[] nums) {
 3         int res = 0;
 4         int left = 0;
 5         int right = nums.length - 1;
 6         while (left < right) {
 7             if (nums[left] < nums[right]) {
 8                 nums[left + 1] += nums[left];
 9                 left++;
10                 res++;
11             } else if (nums[left] > nums[right]) {
12                 nums[right - 1] += nums[right];
13                 right--;
14                 res++;
15             } else {
16                 left++;
17                 right--;
18             }
19         }
20         return res;
21     }
22 }

 

LeetCode 题目总结