项目建设情况_服务器安全证书验证失败_刷关键词怎么刷_seo网站优化方案案例

1526. 形成目标数组的子数组最少增加次数

描述

给你一个整数数组 target 和一个数组 initial ，initial 数组与 target  数组有同样的维度，且一开始全部为 0 。

请你返回从 initial 得到  target 的最少操作次数，每次操作需遵循以下规则：

• 在 initial 中选择 任意 子数组，并将子数组中每个元素增加 1 。

答案保证在 32 位有符号整数以内。

思路

差分数组。显然左边的正数可以与负数配对，尽量配对即可。

class Solution {
public:int minNumberOperations(vector<int>& target) {int n = target.size();for(int i = n - 1; i >= 1; i --) target[i] -= target[i - 1]; int res = 0, p = target[0];for(int i = 1; i < n; i ++){if(target[i] > 0) p += target[i];else p += target[i], res -= target[i];}return res + p;}
};

3229. 使数组等于目标数组所需的最少操作次数 - 力扣（LeetCode）

描述

给你两个长度相同的正整数数组 nums 和 target。

在一次操作中，你可以选择 nums 的任何子数组，并将该子数组内的每个元素的值增加或减少 1。

返回使 nums 数组变为 target 数组所需的 最少 操作次数。

思路

类似上一道题，维护操作次数以及免费操作次数。

class Solution {
public:long long minimumOperations(vector<int>& nums, vector<int>& target) {int n = nums.size();for(int i = 0; i < n; i ++){nums[i] = target[i] - nums[i];}for(int i = n - 1; i >= 1; i --){nums[i] -= nums[i - 1];}long long res = abs(nums[0]), s = nums[0]; for(int i = 1; i < n; i ++){if(nums[i] > 0){ // 需要减法if(s < 0) { // 存在免费减法if(abs(s) >= nums[i]) s += nums[i];else res += nums[i] - abs(s), s = (nums[i] - abs(s));}else if(s >= 0) {res += nums[i];s += nums[i];}}if(nums[i] < 0){ // 需要加法if(s > 0){if(s >= abs(nums[i])) s -= abs(nums[i]);else res += abs(nums[i]) - s, s = -(abs(nums[i]) - s);}else if(s <= 0){res += abs(nums[i]);s -= abs(nums[i]);}}// cout << i << ' ' << s << ' ' << res << '\n';}return res;}
};

豆包 MarsCode——智能编码，一触即发

问题描述

小M拥有一个长度为n的数组 a，由于他非常喜欢数字 w，他希望将所有数组中的数都变为 w。

小M每次操作可以选择一个区间 [l, r]，并将该区间内的所有数字都加 1（包括左右边界 l 和 r）。但为了让挑战更具趣味性，小M要求每次操作的l均不相同，r也均不相同。

小M现在想知道，有多少种不同的操作方案可以让数组中的所有数都变为 w。注意，如果所有操作的区间相同，则视为同一种操作方式，操作顺序不同并不会形成新的方案。

思路

这是一个 $O(n^2)$ 的思路。

差分数组之后，每个点作为左端点或右端点只能一次，所以差分数组的绝对值不可以超过 1。

如此一来，只有 1 , -1, 0

发现对于 1，只能作为左端点 ；1 只能作为右端点。

0 就比较特殊了，可以不操作它，假设操作了，必须作为一次左端点，在作为一次右端点。

因此设 $f_{i,j}$ 表示考虑 $1\sim i$ 元素，且还有 $j$ 个左端点没完成匹配的方案数。

最后数组应该是 0(1) 0 0 0 0 0 0 0(-1) 的形式。

注意差分数组多添加一个$d_{n+1}$ ，表示选择 [i, n] 区间加

#include <bits/stdc++.h>
using namespace std;// Edit your code here
int solution(int n, int w, const std::vector<int> &array) {vector<int> a(array);for(auto &nx : a){nx = w - nx;if(nx < 0) return 0;}a.push_back(0);for(int i = n; i >= 1; i --){a[i] -= a[i - 1];if(abs(a[i]) > 1) return 0;}if(abs(a[0]) > 1) return 0;vector<vector<int> > f(n + 1, vector<int> (n + 3, 0));if(a[0] == 1) f[0][1] = 1;else if(a[0] == 0) f[0][0] = 1;for(int i = 1; i <= n; i ++){for(int j = 0; j <= n + 1; j ++){if(a[i] == 0) {f[i][j] = f[i - 1][j] + j * f[i - 1][j];}if(j && a[i] > 0){f[i][j] = f[i - 1][j - 1];}if(j + 1 <= n + 1 && a[i] < 0){f[i][j] += f[i - 1][j + 1];}}   }return max(f[n][0], f[n][1]);
}int main() {// cout << solution(2, 2, {1, 1}) << '\n';// cout << solution(1, 1, {1}) << '\n';// cout << solution(3, 5, {5, 4, 5}) << '\n';return 0;
}