目录

1、找出数组的K-or值 - 位运算 + 模拟

2、数组的最小相等和 - 分情况讨论

3、使数组变美的最小增量运算数 - 动态规划dp

---

1、找出数组的K-or值 - 位运算 + 模拟

100111. 找出数组中的 K-or 值

思路：

根据范围，我们可以枚举0~30位，然后在每一位时统计nums中满足该位为1的个数，如果个数≥k，则将2^i加入结果

class Solution {public int findKOr(int[] nums, int k) {int res=0;for(int i=0;i<31;i++){int t=0; //记录第i位为1的个数for(int x:nums) t+=(x>>i)&1;if(t>=k) res+=Math.pow(2,i);}return res;}
}

2、数组的最小相等和 - 分情况讨论

100102. 数组的最小相等和

思路：

这题让我想起天梯赛L1-3有一个水族馆还是什么门票的题，分类讨论麻了

这题我自己面向样例编程，写出来了，但是return -1情况写的稀烂

要求最小相等和，也就是让0的位置替换成1，以此保证和最小

• 记nums1和为s1、含0个数z1
• 记nums2和为s2、含0个数z2

我们知道：如果 s1!=s2 但是 z1!=0&&z2!=0 ，那么两者肯定可以相等，因为0位置可以替换任何正整数，最小相等和也就是max（s1+z1，s2+z2）

所以我们只需要再讨论一下两者怎么替换都不相等的情况即可（return -1的情况）

设mins为两者较小和，maxs为两者较大和

• 若 较小和数组内无0，那么小的永远不可能等于大的
• 若 两数组和不等且两者都无0，则两者和定死了，永远不可能相等

class Solution {public long minSum(int[] nums1, int[] nums2) {long s1=0,s2=0;boolean zero1=false,zero2=false;for(int i:nums1){if(i==0) {zero1=true;s1++;}s1+=i;} for(int i:nums2){if(i==0) {zero2=true;s2++;}s2+=i;} if(s1>s2&&zero2==false || s1<s2&&zero1==false || s1!=s2&&zero1==false&&zero2==false)return -1;return Math.max(s1,s2);}
}

3、使数组变美的最小增量运算数 - 动态规划dp

 100107. 使数组变美的最小增量运算数

 

思路：

dp[i]定义：修改n[i]，并把 n[0,i] 变成美丽数组的最小递增运算数

则答案为 min（dp[n-1],dp[n-2],dp[n-3]）

优化：

由于每个dp[i]只与其前三项有关，我们可以用滚动数组将时间复杂度优化到O(1)

class Solution {public long minIncrementOperations(int[] nums, int k) {int n=nums.length;long[] dp=new long[n]; //dp[i]定义：修改n[i]，并把n[0,i]变成美丽数组的最小递增运算数//初始化前三个元素for(int i=0;i<3;i++) dp[i]=Math.max(0,k-nums[i]); //如果n[i]>k，则操作数+0for(int i=3;i<n;i++)dp[i]=Math.max(0,k-nums[i])+Math.min(dp[i-1],Math.min(dp[i-2],dp[i-3]));return Math.min(dp[n-1],Math.min(dp[n-2],dp[n-3]));}
}

class Solution {public long minIncrementOperations(int[] nums, int k) {int n=nums.length;long[] dp=new long[3]; //dp[i]定义：修改n[i]，并把n[0,i]变成美丽数组的最小递增运算数//初始化前三个元素for(int i=0;i<3;i++) dp[i]=Math.max(0,k-nums[i]); //如果n[i]>k，则操作数+0for(int i=3;i<n;i++){long cur=Math.max(0,k-nums[i])+Math.min(dp[0],Math.min(dp[1],dp[2]));dp[0]=dp[1];dp[1]=dp[2];dp[2]=cur;}return Math.min(dp[0],Math.min(dp[1],dp[2]));}
}