class Solution {
public:
int minimumOperations(vector<int>& nums) {
}
};
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 <= 1051 <= nums[i] <= 106原站题解
rust 解法, 执行用时: 12 ms, 内存消耗: 3.5 MB, 提交时间: 2023-10-17 20:07:26
impl Solution {
pub fn minimum_operations(mut nums: Vec<i32>) -> i32 {
let mut res = 0;
let mut left = 0;
let mut right = nums.len() - 1;
while left < right {
if nums[left] == nums[right] {
left += 1;
right -= 1;
} else if nums[left] < nums[right] {
res += 1;
nums[left + 1] += nums[left];
left += 1;
} else {
res += 1;
nums[right - 1] += nums[right];
right -= 1;
}
}
return res;
}
}
java 解法, 执行用时: 4 ms, 内存消耗: 57.2 MB, 提交时间: 2023-10-17 20:06:55
class Solution {
public int minimumOperations(int[] nums) {
int left = 0;
int n = nums.length;
int right = n-1;
long diff = 0L;
int op = 0;
while(left<=right){
if(diff!=0L) ++op;
long change = 0;
if(diff<=0L) change += nums[left++];
if(diff>=0L) change -= nums[right--];
diff+=change;
}
if(diff!=0L) ++op;
return op;
}
}
golang 解法, 执行用时: 108 ms, 内存消耗: 9.2 MB, 提交时间: 2023-10-17 20:06:27
func minimumOperations(nums []int) int {
n := len(nums)
diff,ans,left,right := 0,0,0,n-1
for left<=right{
if diff == 0{
diff += nums[left]-nums[right]
left+=1
right-=1
}else if diff<0{
diff += nums[left]
left += 1
ans++
}else{
diff -= nums[right]
right-=1
ans++
}
}
if diff!=0{
ans++
}
return ans;
}
java 解法, 执行用时: 51 ms, 内存消耗: 57.4 MB, 提交时间: 2023-10-17 20:06:09
class Solution {
public int minimumOperations(int[] nums) {
Deque<Integer> deque = Arrays.stream(nums).boxed().collect(Collectors.toCollection(ArrayDeque::new));
int count = 0;
while (deque.size() > 1) {
// 如果一样的话，说明获取到两个一样的
if (deque.peekFirst().equals(deque.peekLast())) {
count += 2;
deque.removeLast();
deque.removeFirst();
}
// 如果不相等，小数那一侧两个数字相加
// 主要是需要证明这个想法的正确性
else if (deque.peekFirst() < deque.peekLast()) {
deque.addFirst(deque.removeFirst() + deque.removeFirst());
}
else {
deque.addLast(deque.removeLast() + deque.removeLast());
}
}
return nums.length - deque.size() - count;
}
}
cpp 解法, 执行用时: 116 ms, 内存消耗: 81 MB, 提交时间: 2023-10-17 20:05:42
class Solution {
public:
int minimumOperations(vector<int>& nums) {
int n = nums.size();
int ans = 0;
int i = 0, j = n - 1;
long long pre = nums.front(), suf = nums.back();
while (i < j) {
if (pre < suf) {
i++;
pre += nums[i];
ans++;
}
else if (pre > suf) {
j--;
suf += nums[j];
ans++;
}
else {
i++;
j--;
pre = nums[i];
suf = nums[j];
}
}
return ans;
}
};
python3 解法, 执行用时: 124 ms, 内存消耗: 27.7 MB, 提交时间: 2023-10-17 20:05:28
class Solution:
def minimumOperations(self, nums: List[int]) -> int:
n = len(nums)
ans = 0
i, j = 0, n - 1
pre, suf = nums[0], nums[-1]
while i < j:
if pre < suf:
i += 1
pre += nums[i]
ans += 1
elif pre > suf:
j -= 1
suf += nums[j]
ans += 1
else:
i += 1
j -= 1
pre = nums[i]
suf = nums[j]
return ans