Leetcode 第395场周赛问题和解法

题目

找出与数组相加的整数 I

给你两个长度相等的数组nums1和nums2。

数组nums1中的每个元素都与变量x所表示的整数相加。如果x为负数，则表现为元素值的减少。

在与x相加后，nums1和nums2相等。当两个数组中包含相同的整数，并且这些整数出现的频次相同时，两个数组相等。

返回整数x。

示例：
输入：nums1=[2,6,4],nums2=[9,7,5]

输出：3

解释：

与3相加后，nums1和nums2相等。

解题思路

根据题意能得出x=min(nums2)-min(nums1)

class Solution {
    public int addedInteger(int[] nums1, int[] nums2) {
        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;
        for (int i = 0; i < nums1.length; i++) {
            min1 = Math.min(min1, nums1[i]);
            min2 = Math.min(min2, nums2[i]);
        }
        return min2 - min1;
    }
}

找出与数组相加的整数 II

给你两个整数数组nums1和nums2。

从nums1中移除两个元素，并且所有其他元素都与变量x所表示的整数相加。如果x为负数，则表现为元素值的减少。

执行上述操作后，nums1和nums2相等。当两个数组中包含相同的整数，并且这些整数出现的频次相同时，两个数组相等。

返回能够实现数组相等的最小整数x。

示例：

输入：nums1=[4,20,16,12,8],nums2=[14,18,10]

输出：-2

解释：

移除nums1中下标为[0,4]的两个元素，并且每个元素与-2相加后，nums1变为[18,14,10]，与nums2相等。

解题思路

O(nlogn) 排序+判断子序列

class Solution {
    public int minimumAddedInteger(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        // 枚举保留 nums1[2] 或者 nums1[1] 或者 nums1[0]
        // 倒着枚举是因为 nums1[i] 越大答案越小，第一个满足的就是答案
        for (int i = 2; i > 0; i--) {
            int diff = nums2[0] - nums1[i];
            // 在 {nums1[i] + diff} 中找子序列 nums2
            int j = 0;
            for (int k = i; k < nums1.length; k++) {
                if (j < nums2.length && nums2[j] == nums1[k] + diff && ++j == nums2.length) {
                    // nums2 是 {nums1[i] + diff} 的子序列
                    return diff;
                }
            }
        }
        // 题目保证答案一定存在
        return nums2[0] - nums1[0];
    }
}

数组最后一个元素的最小值

给你两个整数n和x。你需要构造一个长度为n的正整数数组nums，对于所有0<=i<n-1，满足nums[i+1]大于nums[i]，并且数组nums中所有元素的按位AND运算结果为x。

返回nums[n-1]可能的最小值。

示例1：

输入：n=3,x=4

输出：6

解释：

数组nums可以是[4,5,6]，最后一个元素为6。

解题思路

位运算

class Solution {
    public long minEnd(int n, int x) {
        n--; // 先把 n 减一，这样下面讨论的 n 就是原来的 n-1
        long ans = x;
        int i = 0, j = 0;
        while ((n >> j) > 0) {
            // x 的第 i 个比特值是 0，即「空位」
            if ((ans >> i & 1) == 0) {
                // 空位填入 n 的第 j 个比特值
                ans |= (long) (n >> j & 1) << i;
                j++;
            }
            i++;
        }
        return ans;
    }
}

找出唯一性数组的中位数

给你一个整数数组nums。数组nums的唯一性数组是一个按元素从小到大排序的数组，包含了nums的所有非空子数组中不同元素的个数。

换句话说，这是由所有0<=i<=j<nums.length的distinct(nums[i…j])组成的递增数。

其中，distinct(nums[i…j])表示从下标i到下标j的子数组中不同元素的数量。

返回nums唯一性数组的中位数。

注意，数组的中位数定义为有序数组的中间元素。如果有两个中间元素，则取值较小的那个。

示例 1：

输入：nums = [1,2,3]

输出：1

解释：

nums 的唯一性数组为 [distinct(nums[0…0]), distinct(nums[1…1]), distinct(nums[2…2]), distinct(nums[0…1]), distinct(nums[1…2]), distinct(nums[0…2])]，即 [1, 1, 1, 2, 2, 3] 。唯一性数组的中位数为 1 ，因此答案是 1 。

解题思路

二分答案+滑动窗口

class Solution {
    public int medianOfUniquenessArray(int[] nums) {
        int n = nums.length;
        long k = ((long) n * (n + 1) / 2 + 1) / 2;
        int left = 0;
        int right = n;
        while (left + 1 < right) {
            int mid = (left + right) / 2;
            if (check(nums, mid, k)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }

    private boolean check(int[] nums, int upper, long k) {
        long cnt = 0;
        int l = 0;
        HashMap<Integer, Integer> freq = new HashMap<>();
        for (int r = 0; r < nums.length; r++) {
            freq.merge(nums[r], 1, Integer::sum);
            while (freq.size() > upper) {
                int out = nums[l++];
                if (freq.merge(out, -1, Integer::sum) == 0) {
                    freq.remove(out);
                }
            }
            cnt += r - l + 1;
            if (cnt >= k) {
                return true;
            }
        }
        return false;
    }
}