修改两个元素的最小分数

题目描述

给你一个下标从 0 开始的整数数组 nums 。

• nums 的 最小 得分是满足 0 <= i < j < nums.length 的 |nums[i] - nums[j]| 的最小值。
• nums的 最大 得分是满足 0 <= i < j < nums.length 的 |nums[i] - nums[j]| 的最大值。
• nums 的分数是 最大 得分与 最小 得分的和。
  我们的目标是最小化 nums 的分数。你 最多 可以修改 nums 中 2 个元素的值。

请你返回修改 nums 中 至多两个 元素的值后，可以得到的 最小分数 。

|x| 表示 x 的绝对值。

样例

样例输入

nums = [1,4,3]
nums = [1,4,7,8,5]

样例输出

0
解释：将 nums[1] 和 nums[2] 的值改为 1 ，nums 变为 [1,1,1] 。|nums[i] - nums[j]| 的值永远为 0 ，所以我们返回 0 + 0 = 0 。

3
解释：
将 nums[0] 和 nums[1] 的值变为 6 ，nums 变为 [6,6,7,8,5] 。
最小得分是 i = 0 且 j = 1 时得到的 |nums[i] - nums[j]| = |6 - 6| = 0 。
最大得分是 i = 3 且 j = 4 时得到的 |nums[i] - nums[j]| = |8 - 5| = 3 。
最大得分与最小得分之和为 3 。这是最优答案。

提示

• $3<=nums.length<=10^5$
• $1<=nums[i]<=10^9$

思路

思路题，可以任意改变两个数的值，题中又需要将得分达到最大值，所以区间两个数的最小差值一定为0。而后将数组排序，只需求min(nums[n-1] - nums[2], nums[n-2] - nums[1], nums[n-3] - nums[0]);

代码实现

class Solution {public int minimizeSum(int[] nums) {Arrays.sort(nums);int n = nums.length;return Math.min(Math.min(nums[n-3] - nums[0] , nums[n-2] - nums[1]), nums[n-1] - nums[2]);}
}

最小无法得到的或值

题目描述

给你一个下标从 0 开始的整数数组 nums 。

如果存在一些整数满足 0 <= index1 < index2 < … < indexk < nums.length ，得到 nums[index1] | nums[index2] | … | nums[indexk] = x ，那么我们说 x 是 可表达的 。换言之，如果一个整数能由 nums 的某个子序列的或运算得到，那么它就是可表达的。

请你返回 nums 不可表达的 最小非零整数 。

样例

样例输入

nums = [2,1]
nums = [5,3,2]

样例输出

4
解释：1 和 2 已经在数组中，因为 nums[0] | nums[1] = 2 | 1 = 3 ，所以 3 是可表达的。由于 4 是不可表达的，所以我们返回 4 。

1
解释：1 是最小不可表达的数字。

提示

• $1<=nums.length<=10^5$
• $1<=nums[i]<=10^9$

思路

同样还是思维题，因为需要最小nums数组不能表达出的数，那该数的二进制形式只能为1000...格式。又因或运算只会变大或者不变，nums不能表达即表示nums中的所有数都不等于该数。

代码实现

class Solution {public int minImpossibleOR(int[] nums) {for(int i = 0; i <= 30; i++){boolean ok = true;// 此处还可以使用set进行优化，但竞赛的时候没写出来for(int num : nums){if(num ==  (1 << i)){ok = false;break;}}if(ok) return 1 << i;}return -1;}
}