🏆 第 286 场力扣周赛

又刷新最好成绩了！
t3wrong是因为没考虑长度问题。

5268. 找出两数组的不同

给你两个下标从 0 开始的整数数组 nums1 和 nums2 ，请你返回一个长度为 2 的列表 answer ，其中：

• answer[0] 是 nums1 中所有 不 存在于 nums2 中的 不同 整数组成的列表。
• answer[1] 是 nums2 中所有 不 存在于 nums1 中的 不同 整数组成的列表。

注意：列表中的整数可以按 任意 顺序返回。

示例 1：
输入：nums1 = [1,2,3], nums2 = [2,4,6] 输出：[[1,3],[4,6]] 解释： 对于 nums1 ，nums1[1] = 2 出现在 nums2 中下标 0 处，然而 nums1[0] = 1 和 nums1[2] = 3 没有出现在 nums2 中。因此，answer[0] = [1,3]。 对于 nums2 ，nums2[0] = 2 出现在 nums1 中下标 1 处，然而 nums2[1] = 4 和 nums2[2] = 6 没有出现在 nums2 中。因此，answer[1] = [4,6]。
示例 2：
输入：nums1 = [1,2,3,3], nums2 = [1,1,2,2] 输出：[[3],[]] 解释： 对于 nums1 ，nums1[2] 和 nums1[3] 没有出现在 nums2 中。由于 nums1[2] == nums1[3] ，二者的值只需要在 answer[0] 中出现一次，故 answer[0] = [3]。 nums2 中的每个整数都在 nums1 中出现，因此，answer[1] = [] 。

提示：

• 1 <= nums1.length, nums2.length <= 1000
• -1000 <= nums1[i], nums2[i] <= 1000

思路：
哈希

class Solution {
    public List<List<Integer>> findDifference(int[] nums1, int[] nums2) {
        Set<Integer> s1 = new HashSet<>();
        Set<Integer> s2 = new HashSet<>();
        for (int x : nums1) {
            s1.add(x);
        }
        for (int x : nums2) {
            s2.add(x);
        }
        List<Integer> l1 = new ArrayList<>();
        List<Integer> l2 = new ArrayList<>();
        List<List<Integer>> res = new ArrayList<>();
        for (int x : s1) {
            if (!s2.contains(x))
                l1.add(x);
        }
        for (int x : s2) {
            if (!s1.contains(x))
                l2.add(x);
        }
        res.add(l1);
        res.add(l2);
        return res;
    }
}

5236. 美化数组的最少删除数

给你一个下标从 0 开始的整数数组 nums ，如果满足下述条件，则认为数组 nums 是一个 美丽数组 ：

• nums.length 为偶数
• 对所有满足 i % 2 == 0 的下标 i ，nums[i] != nums[i + 1] 均成立

注意，空数组同样认为是美丽数组。
你可以从 nums 中删除任意数量的元素。当你删除一个元素时，被删除元素右侧的所有元素将会向左移动一个单位以填补空缺，而左侧的元素将会保持 不变 。
返回使 nums 变为美丽数组所需删除的 最少 元素数目。

示例 1：
输入：nums = [1,1,2,3,5] 输出：1 解释：可以删除 nums[0] 或 nums[1] ，这样得到的 nums = [1,2,3,5] 是一个美丽数组。可以证明，要想使 nums 变为美丽数组，至少需要删除 1 个元素。
示例 2：
输入：nums = [1,1,2,2,3,3] 输出：2 解释：可以删除 nums[0] 和 nums[5] ，这样得到的 nums = [1,2,2,3] 是一个美丽数组。可以证明，要想使 nums 变为美丽数组，至少需要删除 2 个元素。

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 105

思路：
贪心

class Solution {
    public int minDeletion(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return 1;
        int cnt = 0;
        for (int i = 0, j = 1; j < n; j++) {
            if (nums[i] == nums[j]) {
                cnt++;
            } else {
                i = j + 1;
                j++;
            }
        }
        if ((n - cnt) % 2 != 0)
                cnt++;
        return cnt;
    }
}

5253. 找到指定长度的回文数

给你一个整数数组 queries 和一个 正 整数 intLength ，请你返回一个数组 answer ，其中 answer[i] 是长度为 intLength 的 正回文数 中第_ _queries[i] 小的数字，如果不存在这样的回文数，则为 -1 。
回文数 指的是从前往后和从后往前读一模一样的数字。回文数不能有前导 0 。

示例 1：
输入：queries = [1,2,3,4,5,90], intLength = 3 输出：[101,111,121,131,141,999] 解释： 长度为 3 的最小回文数依次是： 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 201, … 第 90 个长度为 3 的回文数是 999 。
示例 2：
输入：queries = [2,4,6], intLength = 4 输出：[1111,1331,1551] 解释： 长度为 4 的前 6 个回文数是： 1001, 1111, 1221, 1331, 1441 和 1551 。

提示：

• 1 <= queries.length <= 5 * 104
• 1 <= queries[i] <= 109
• 1 <= intLength <= 15

思路：
构造回文串
注意长度限制

class Solution {
    public long[] kthPalindrome(int[] q, int len) {
        int n = q.length;
        if (len == 1) {
            long[] res = new long[n];
            for (int i = 0; i < n; i++) {
                if (q[i] > 0 && q[i] <= 9)
                    res[i] = q[i];
                else
                    res[i] = -1;
            }
            return res;
        }
        long[] res = new long[n];
        StringBuilder sb = new StringBuilder();
        sb.append(1);
        int minus = (len + 1) / 2 - 1;
        while (minus > 0) {
            sb.append(0);
            minus--;
        }
        long s = Long.parseLong(sb.toString());
        // System.out.println(s);
        for (int i = 0; i < n; i++) {
            int idx = q[i];
            StringBuilder sb2 = new StringBuilder();
            long v = s + idx - 1;
            if (len % 2 == 1) {
                long s2 = v / 10;
                sb2.append(v);
                sb2.append(new StringBuilder().append(s2).reverse().toString());
                if (sb2.length() > len) {
                    res[i] = -1;
                    continue;
                }
                res[i] = Long.parseLong(sb2.toString());
            } else {
                sb2.append(v);
                sb2.append(new StringBuilder().append(v).reverse().toString());
                if (sb2.length() > len) {
                    res[i] = -1;
                    continue;
                }
                res[i] = Long.parseLong(sb2.toString());
            }
        }
        return res;
    }
}

5269. 从栈中取出 K 个硬币的最大面值和

一张桌子上总共有 n 个硬币 栈 。每个栈有 正整数 个带面值的硬币。
每一次操作中，你可以从任意一个栈的 顶部 取出 1 个硬币，从栈中移除它，并放入你的钱包里。
给你一个列表 piles ，其中 piles[i] 是一个整数数组，分别表示第 i 个栈里 从顶到底 的硬币面值。同时给你一个正整数 k ，请你返回在 恰好 进行 k 次操作的前提下，你钱包里硬币面值之和 最大为多少 。

示例 1：

输入：piles = [[1,100,3],[7,8,9]], k = 2 输出：101 解释： 上图展示了几种选择 k 个硬币的不同方法。 我们可以得到的最大面值为 101 。
示例 2：
输入：piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7 输出：706 解释： 如果我们所有硬币都从最后一个栈中取，可以得到最大面值和。

提示：

• n == piles.length
• 1 <= n <= 1000
• 1 <= piles[i][j] <= 105
• 1 <= k <= sum(piles[i].length) <= 2000

思路：
分组背包

class Solution {
    public int maxValueOfCoins(List<List<Integer>> p, int k) {
        int n = p.size();
        int[][] f = new int[n + 1][k + 1];
        for (int i = 1; i <= n; i++) {
            int len = p.get(i - 1).size();
            for (int j = 0; j <= k; j++) {
                int sum = 0;
                for (int l = 0; l <= len; l++) {
                    if (j >= l)
                        f[i][j] = Math.max(f[i - 1][j - l] + sum, f[i][j]);
                    if (l != len)
                        sum += p.get(i - 1).get(l);
                }
            }
        }
        return f[n][k];
    }
}