leetcode conttest 302

确实最简单的周赛，4个题目都可以暴力。

6120. 数组能形成多少数对

题目

给你一个下标从 0 开始的整数数组 nums 。在一步操作中，你可以执行以下步骤：

从 nums 选出两个相等的整数
从 nums 中移除这两个整数，形成一个数对
请你在 nums 上多次执行此操作直到无法继续执行。

返回一个下标从 0 开始、长度为 2 的整数数组 answer 作为答案，其中 answer[0] 是形成的数对数目，answer[1] 是对 nums 尽可能执行上述操作后剩下的整数数目。

示例 1：

输入：nums = [1,3,2,1,3,2,2]
输出：[3,1]
解释：
nums[0] 和 nums[3] 形成一个数对，并从 nums 中移除，nums = [3,2,3,2,2] 。
nums[0] 和 nums[2] 形成一个数对，并从 nums 中移除，nums = [2,2,2] 。
nums[0] 和 nums[1] 形成一个数对，并从 nums 中移除，nums = [2] 。
无法形成更多数对。总共形成 3 个数对，nums 中剩下 1 个数字。

示例 2：

输入：nums = [1,1]
输出：[1,0]
解释：nums[0] 和 nums[1] 形成一个数对，并从 nums 中移除，nums = [] 。
无法形成更多数对。总共形成 1 个数对，nums 中剩下 0 个数字。

示例 3：

输入：nums = [0]
输出：[0,1]
解释：无法形成数对，nums 中剩下 1 个数字。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 100

地址

https://leetcode.cn/problems/maximum-number-of-pairs-in-array/

题意

哈希统计

思路

简单题目，直接统计数目中出现重复元素的个数即可, 统计所有可能的偶数对。
复杂度分析：

时间复杂度：$O(n)$。
空间复杂度：$O(n)$。

代码

class Solution {
public:
    vector<int> numberOfPairs(vector<int>& nums) {
        int x = *max_element(nums.begin(), nums.end());
        vector<int> cnt(x + 1);
        vector<int> ans(2);
        for (auto v : nums) {
            cnt[v]++;
        }
        for (int i = 0; i <= x; i++) {
            ans[0] += cnt[i] / 2;
        }
        ans[1] = nums.size() - ans[0] * 2;
        return ans;
    }
};

6164. 数位和相等数对的最大和

题目

给你一个下标从 0 开始的数组nums，数组中的元素都是正整数。请你选出两个下标 i 和 j（i != j），且 nums[i] 的数位和与 nums[j] 的数位和相等。

请你找出所有满足条件的下标 i 和 j ，找出并返回 nums[i] + nums[j] 可以得到的最大值。

示例 1：

输入：nums = [18,43,36,13,7]
输出：54
解释：满足条件的数对 (i, j) 为：
- (0, 2) ，两个数字的数位和都是 9 ，相加得到 18 + 36 = 54 。
- (1, 4) ，两个数字的数位和都是 7 ，相加得到 43 + 7 = 50 。
所以可以获得的最大和是 54 。

示例 2：

输入：nums = [10,12,19,14]
输出：-1
解释：不存在满足条件的数对，返回 -1 。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 109

地址

https://leetcode.cn/problems/max-sum-of-a-pair-with-equal-sum-of-digits

题意

动态规划

思路

设 $dp[x]$ 表示数位和为 $x$ 值最大的数，我们依次遍历每个数 $x$，并计算 $x$ 的数位和为 $sum[x]$，此时我们计算 $sum[x]$，对于 $x$ 则以 $x$ 为其中一个数的最大的和为 $x + dp[sum[x]]$，同时我们更新 $dp[x] = \max(dp[x],x)$。
复杂度分析：

时间复杂度：时间复杂度为 $O(n)$，$n$ 表示数组的长度。
空间复杂度：$O(n)$。

代码

class Solution {
public:
    int maximumSum(vector<int>& nums) {
        unordered_map<int, int> cnt;
        int ans = -1;
        for (auto x : nums) {
            int sum = 0;
            int val = x;
            while (x != 0) {
                sum += (x % 10);
                x /= 10;
            }
            if (cnt.count(sum)) {
                ans = max(ans, val + cnt[sum]); 
                cnt[sum] = max(cnt[sum], val);
            } else {
                cnt[sum] = val;
            }
        }
        return ans;
    }
};

6121. 裁剪数字后查询第 K 小的数字

题目

给你一个下标从 0 开始的字符串数组 nums ，其中每个字符串长度相等且只包含数字。

再给你一个下标从 0 开始的二维整数数组 queries ，其中 queries[i] = [ki, trimi] 。对于每个 queries[i] ，你需要：

将 nums 中每个数字裁剪到剩下最右边 trimi 个数位。
在裁剪过后的数字中，找到 nums 中第 ki 小数字对应的下标。如果两个裁剪后数字一样大，那么下标更小的数字视为更小的数字。
将 nums 中每个数字恢复到原本字符串。
请你返回一个长度与 queries 相等的数组 answer，其中 answer[i] 是第 i 次查询的结果。

提示：

裁剪到剩下 x 个数位的意思是不断删除最左边的数位，直到剩下 x 个数位。
nums 中的字符串可能会有前导 0 。

示例 1：

输入：nums = ["102","473","251","814"], queries = [[1,1],[2,3],[4,2],[1,2]]
输出：[2,2,1,0]
解释：
1. 裁剪到只剩 1 个数位后，nums = ["2","3","1","4"] 。最小的数字是 1 ，下标为 2 。
2. 裁剪到剩 3 个数位后，nums 没有变化。第 2 小的数字是 251 ，下标为 2 。
3. 裁剪到剩 2 个数位后，nums = ["02","73","51","14"] 。第 4 小的数字是 73 ，下标为 1 。
4. 裁剪到剩 2 个数位后，最小数字是 2 ，下标为 0 。
   注意，裁剪后数字 "02" 值为 2 。

示例 2：

输入：nums = ["24","37","96","04"], queries = [[2,1],[2,2]]
输出：[3,0]
解释：
1. 裁剪到剩 1 个数位，nums = ["4","7","6","4"] 。第 2 小的数字是 4 ，下标为 3 。
   有两个 4 ，下标为 0 的 4 视为小于下标为 3 的 4 。
2. 裁剪到剩 2 个数位，nums 不变。第二小的数字是 24 ，下标为 0 。

提示：

1 <= nums.length <= 100
1 <= nums[i].length <= 100
nums[i] 只包含数字。
所有 nums[i].length 的长度相同。
1 <= queries.length <= 100
queries[i].length == 2
1 <= ki <= nums.length
1 <= trimi <= nums[0].length

地址

https://leetcode.cn/problems/query-kth-smallest-trimmed-number

题意

暴力排序

思路

由于题目给的数量级较小，实际我们直接模拟排序即可，按照题目要求，每次查询时，将要求长度的后缀按照字典序进行排序即可，非常简单；
感觉数量级还可以再高一点, 此时可以用基数排序进行优化。基数排序对后缀进行排序，时间复杂度为 $O(mn|S|)$，$n$ 表示查询的次数，$m$ 表示字符串数组的长度 $|S|$ 表示字符集。当然更优化的算法可以采用后缀数组排序。
复杂度分析：

时间复杂度：暴力模拟的时间复杂度为 $O(qnm\log m)$, $q$ 表示给定的字符串的长度, $n$ 表示查询的次数，$m$ 表示字符串数组的长度。
空间复杂度：$O(qm)$，$q$ 表示给定的字符串的长度, $m$ 表示字符串数组的长度。

代码

直接排序

class Solution {
public:
    vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& queries) {
        int m = nums.size();
        int n = queries.size();
        int len = nums[0].size();        
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            int k = queries[i][0], trim = queries[i][1];
            vector<pair<string, int>> suffix;
            for (int j = 0; j < m; j++) {
                suffix.emplace_back(nums[j].substr(len - trim), j);
            }
            sort(suffix.begin(), suffix.end());
            ans[i] = suffix[k - 1].second;
        }
        return ans;
    }
};

基数排序

class Solution {
public:
    vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& queries) {
        int m = nums.size();
        int n = queries.size();
        int len = nums[0].size();      
        vector<vector<int>> suffix(len + 1);
        for (int i = 0; i < m; i++) {
            suffix[0].emplace_back(i);
        }
        for (int i = 1; i <= len; i++) {
            vector<vector<int>> cnt(10);
            for (int j = 0; j < m; j++) {
                int index = suffix[i-1][j];
                char c = nums[index][len - i];
                cnt[c - '0'].emplace_back(index);
            }
            for (int j = 0; j < 10; j++) {
                for (auto x : cnt[j]) {
                    suffix[i].emplace_back(x);
                }
            }
        }  
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            int k = queries[i][0], trim = queries[i][1];
            ans[i] = suffix[trim][k - 1];
        }
        return ans;
    }
};

6122. 使数组可以被整除的最少删除次数

题目

给你两个正整数数组 nums 和 numsDivide 。你可以从 nums 中删除任意数目的元素。

请你返回使 nums 中最小元素可以整除 numsDivide 中所有元素的最少删除次数。如果无法得到这样的元素，返回 -1 。

如果 y % x == 0 ，那么我们说整数 x 整除 y 。

示例 1：

输入：nums = [2,3,2,4,3], numsDivide = [9,6,9,3,15]
输出：2
解释：
[2,3,2,4,3] 中最小元素是 2 ，它无法整除 numsDivide 中所有元素。
我们从 nums 中删除 2 个大小为 2 的元素，得到 nums = [3,4,3] 。
[3,4,3] 中最小元素为 3 ，它可以整除 numsDivide 中所有元素。
可以证明 2 是最少删除次数。

示例 2：

输入：nums = [4,3,6], numsDivide = [8,2,6,10]
输出：-1
解释：
我们想 nums 中的最小元素可以整除 numsDivide 中的所有元素。
没有任何办法可以达到这一目的。

提示：

1 <= nums.length, numsDivide.length <= 105
1 <= nums[i], numsDivide[i] <= 109

地址

https://leetcode.cn/problems/minimum-deletions-to-make-array-divisible

题意

数学问题

思路

感觉是最简单的T4了。如果要被数组 $numsDivide$ 中所有的元素整除，则该数最大只能为数组中所有元素的最大公约数了 $maxgcd$, 如果 $nums$ 中的最小元素能够整除$maxgcd$，则表示当前 $nums$ 中的最小元素符合要求。

首先求出数组的最大公约数 $maxgcd$；
然后将数组 $nums$ 按照从小到大排序，我们依次尝试数组中的元素，能否被 $maxgcd$ 整除，如果可以整除返回即可。

复杂度分析：

时间复杂度：$O(m + n\log n)$，$n$ 表示数组 $nums$ 的长度，$m$ 表示数组 $numsDivide$ 的长度。
空间复杂度：$O(1)$。

代码

class Solution {
public:
    int minOperations(vector<int>& nums, vector<int>& numsDivide) {
        int m = nums.size();
        int n = numsDivide.size();
        sort(nums.begin(), nums.end());
        int maxGcd = numsDivide[0];
        for (int i = 1; i < n; i++) {
            maxGcd = __gcd(maxGcd, numsDivide[i]);
        }
        for (int i = 0; i < m; i++) {
            if ((maxGcd % nums[i]) == 0) {
                return i;
            }
        }
        return -1;
    }
};

欢迎关注和打赏，感谢支持！

关注我的博客: http://mikemeng.org/
关注我的知乎：https://www.zhihu.com/people/da-hua-niu
关注我的微信公众号: 公务程序猿

Tags: 力扣周赛

← leetcode biweekly conttest 83 leetcode conttest 301 →

扫描二维码，分享此文章