leetcode每日一题1664生成平衡数组的方案数(中等，动态规划)

时间长不做动态规划的题目&＃xff0c;现在突然看过去有些生疏&＃xff0c;第一眼看到这个题目想了一下暴力&＃xff0c;然后突然注意到了题目的难度是中等&＃xff0c;力扣里面的中等难度的题目都是没有暴力可以做出来的&＃xff0c;目前我做这么多题来看的话&＃xff0c;第一眼我只用了一个数组来看&＃xff0c;发现很麻烦&＃xff0c;必须对i的值进行偶数奇数的判断&＃xff0c;进行两次结果分析&＃xff0c;非常的麻烦&＃xff0c;索性我就用了两个数组来进行存储&＃xff0c;空间浪费了&＃xff0c;但是目的很明确&＃xff0c;思路也简单了很多&＃xff0c;消去任意一个位置的数组其实就是将当前位置的后续部分的奇偶性进行了调换&＃xff0c;所以我们只需要将整个数组的奇偶性存入四个数组分别是&＃xff0c;正序奇偶&＃xff0c;和反序奇偶&＃xff0c;对于最后的关系进行判断&＃xff0c;然后对第一个数字和最后一个数字进行单独判断即可&＃xff0c;时间有点浪费了&＃xff0c;但是思路很明确

给你一个整数数组 nums 。你需要选择 恰好 一个下标&＃xff08;下标从 0 开始&＃xff09;并删除对应的元素。请注意剩下元素的下标可能会因为删除操作而发生改变。

比方说&＃xff0c;如果 nums &＃61; [6,1,7,4,1] &＃xff0c;那么&＃xff1a;

选择删除下标 1 &＃xff0c;剩下的数组为 nums &＃61; [6,7,4,1] 。

选择删除下标 2 &＃xff0c;剩下的数组为 nums &＃61; [6,1,4,1] 。

选择删除下标 4 &＃xff0c;剩下的数组为 nums &＃61; [6,1,7,4] 。

如果一个数组满足奇数下标元素的和与偶数下标元素的和相等&＃xff0c;该数组就是一个 平衡数组 。

请你返回删除操作后&＃xff0c;剩下的数组 nums 是 平衡数组 的 方案数 。



示例 1&＃xff1a;

输入&＃xff1a;nums &＃61; [2,1,6,4]

输出&＃xff1a;1

解释&＃xff1a;

删除下标 0 &＃xff1a;[1,6,4] -> 偶数元素下标为&＃xff1a;1 &＃43; 4 &＃61; 5 。奇数元素下标为&＃xff1a;6 。不平衡。

删除下标 1 &＃xff1a;[2,6,4] -> 偶数元素下标为&＃xff1a;2 &＃43; 4 &＃61; 6 。奇数元素下标为&＃xff1a;6 。平衡。

删除下标 2 &＃xff1a;[2,1,4] -> 偶数元素下标为&＃xff1a;2 &＃43; 4 &＃61; 6 。奇数元素下标为&＃xff1a;1 。不平衡。

删除下标 3 &＃xff1a;[2,1,6] -> 偶数元素下标为&＃xff1a;2 &＃43; 6 &＃61; 8 。奇数元素下标为&＃xff1a;1 。不平衡。

只有一种让剩余数组成为平衡数组的方案。

示例 2&＃xff1a;

输入&＃xff1a;nums &＃61; [1,1,1]

输出&＃xff1a;3

解释&＃xff1a;你可以删除任意元素&＃xff0c;剩余数组都是平衡数组。

示例 3&＃xff1a;

输入&＃xff1a;nums &＃61; [1,2,3]

输出&＃xff1a;0

解释&＃xff1a;不管删除哪个元素&＃xff0c;剩下数组都不是平衡数组。



提示&＃xff1a;

1 <&＃61; nums.length <&＃61; 105

1 <&＃61; nums[i] <&＃61; 104

int waysToMakeFair(int* nums, int numsSize){
if(numsSize&＃61;&＃61;1)
{
return 1;
}
int sum0&＃61;0,sum1&＃61;0,sum&＃61;0,i,j,flag&＃61;0,x0,x1;
int dp[numsSize][2],x[numsSize][2]; //0奇数1偶数
memset(dp,0,sizeof(dp));
memset(x,0,sizeof(x));
for(i&＃61;0;i {
if(i%2&＃61;&＃61;0){
sum0&＃43;&＃61;nums[i];
}else{
sum1&＃43;&＃61;nums[i];
}
x[i][0]&＃61;sum0;
x[i][1]&＃61;sum1;
}
dp[0][0]&＃61;sum0;
dp[0][1]&＃61;sum1;
x0&＃61;sum0;
x1&＃61;sum1;
sum&＃61;sum1&＃43;sum0;
sum0-&＃61;nums[0];
for(i&＃61;1;i {
if(i%2&＃61;&＃61;0){
dp[i][0]&＃61;sum0;
sum0-&＃61;nums[i];
dp[i][1]&＃61;sum1;
}else{
dp[i][1]&＃61;sum1;
sum1-&＃61;nums[i];
dp[i][0]&＃61;sum0;
}
}
int p,q;
for(i&＃61;1;i {
if((sum-nums[i])%2&＃61;&＃61;0)
{
p&＃61;dp[i&＃43;1][0]&＃43;x[i-1][1];
q&＃61;dp[i&＃43;1][1]&＃43;x[i-1][0];
printf("i&＃61;%d p&＃61;%d q&＃61;%d\n",i,p,q);
if(p&＃61;&＃61;q)
{
printf("i&＃61;%d\n",i);
flag&＃43;&＃43;;
}
}
}
if(dp[1][0]&＃61;&＃61;dp[1][1])
{
flag&＃43;&＃43;;
}
if(numsSize%2&＃61;&＃61;1)
{
x0-&＃61;nums[numsSize-1];
}else{
x1-&＃61;nums[numsSize-1];
}
if(x0&＃61;&＃61;x1)
{
flag&＃43;&＃43;;
}
return flag;
}