利用ps做兼职的网站,网站建设新报价图片,宁波十大互联网企业,美团推广平台2025. 分割数组的最多方案数
给你一个下标从 0 开始且长度为 n 的整数数组 nums 。分割 数组 nums 的方案数定义为符合以下两个条件的 pivot 数目#xff1a;
1 pivot nnums[0] nums[1] … nums[pivot - 1] nums[pivot] nums[pivot 1] … nums[n -1] 同时…2025. 分割数组的最多方案数
给你一个下标从 0 开始且长度为 n 的整数数组 nums 。分割 数组 nums 的方案数定义为符合以下两个条件的 pivot 数目
1 pivot nnums[0] nums[1] … nums[pivot - 1] nums[pivot] nums[pivot 1] … nums[n -1] 同时给你一个整数 k 。你可以将 nums 中 一个 元素变为 k 或 不改变 数组。
请你返回在 至多 改变一个元素的前提下最多 有多少种方法 分割 nums 使得上述两个条件都满足。 示例 1输入nums [2,-1,2], k 3
输出1
解释一个最优的方案是将 nums[0] 改为 k 。数组变为 [3,-1,2] 。
有一种方法分割数组
- pivot 2 我们有分割 [3,-1 | 2]3 -1 2 。
示例 2输入nums [0,0,0], k 1
输出2
解释一个最优的方案是不改动数组。
有两种方法分割数组
- pivot 1 我们有分割 [0 | 0,0]0 0 0 。
- pivot 2 我们有分割 [0,0 | 0]: 0 0 0 。
示例 3输入nums [22,4,-25,-20,-15,15,-16,7,19,-10,0,-13,-14], k -33
输出4
解释一个最优的方案是将 nums[2] 改为 k 。数组变为 [22,4,-33,-20,-15,15,-16,7,19,-10,0,-13,-14] 。
有四种方法分割数组。提示
n nums.length2 n 10510^5105−105-10^5−105 k, nums[i] 10510^5105
解题思路
对于 nums[0] nums[1] ... nums[pivot - 1] nums[pivot] nums[pivot 1] ... nums[n - 1]
我们把nums[0] nums[1] ... nums[pivot - 1] 称为front后半部分nums[pivot] nums[pivot 1] ... nums[n - 1]称为back整个数组的总和为sum。
维护一个数组的前缀和pre
当不改变数组的时候只有满足sum[i]*2sum的前缀和才能成为一种分隔方法当改变数组的一个元素的时候我们遍历所有的元素尝试将其改变维护两个map分别代表当前元素前面出现过的前缀和以及后面的前缀和。可以发现当我们尝试改变元素时是不会影响前面的前缀和而是会导致后面的前缀和产生变化d(d为目标元素k与原来元素的差值)。因此对于前边满足条件的前缀和我们的计算公式为sum[i]sumd-sum[i]而对于后面的前缀和计算公式为 sum[i]dsumd-(sum[i]d)
代码 class Solution {
public:int waysToPartition(vectorint nums, int k) {int res(0), n(nums.size());vectorlong long pre(n 1);maplong long, int ml;maplong long,int mr;for (int i 0; i n; i) {pre[i 1] pre[i] nums[i];if(i1n)mr[pre[i1]];}long long sum pre[n];if (sum%20)resmr[sum/2];for (int i 1; i n; i) {long long dk-nums[i-1],new_sumsumd;if (new_sum%20){resmax(res,ml[new_sum/2]mr[new_sum/2-d]);}ml[pre[i]];mr[pre[i]]--;}return res;}
};
