leetcode-weekly-contest-302

刷题

发布日期: 2022-07-17

Problem List

[1] 数组能形成多少数对
[2] 数位和相等数对的最大和
[3] 裁剪数字后查询第 K 小的数字
[4] 使数组可以被整除的最少删除次数

1. 数组能形成多少数对

1.1 题目描述

给你一个下标从 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 个数字。

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

1.2 思路

哈希表统计数字出现个数，然后遍历哈希表，每个数出现的次数/2就是这个数可以组成的数对数，求和就是整个数组可以组成的数对总数n,最后返回{n, (int)nums.size()-2*ans}即可。

class Solution {
public:
    vector<int> numberOfPairs(vector<int>& nums) {
        map<int, int> m;
        for(int i: nums)    ++m[i];
        int ans = 0;
        for(auto [val, cnt] : m)    ans += cnt / 2;
        return {ans, (int)nums.size()-(2*ans)};
    }
};

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

2.1 题目描述

给你一个下标从 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
解释：
满足条件的数对 (i, j) 为：

(0, 2) ，两个数字的数位和都是 9 ，相加得到 18 + 36 = 54 。

(1, 4) ，两个数字的数位和都是 7 ，相加得到 43 + 7 = 50 。
所以可以获得的最大和是 54 。

2.2 思路

遍历整个数组，求每一个数的数位和，并插入到map，这里map定义为map<int, vector<int>>，方便后续对具有同一数位和的数进行排序。遍历后对map进行遍历，并将值进行降序排序，然后返回最大两个数的加和，而答案就是所有map中两个数加和中的最大值。

class Solution {
    int get(int a) {
        int ret = 0;
        while(a) {
            ret += a%10;
            a /= 10;
        }
        return ret;
    }
public:
    int maximumSum(vector<int>& nums) {
        map<int, vector<int>> m;
        for(int i: nums) {
            m[get(i)].emplace_back(i);
        }  
        int ans = -1;
        for(auto [val, vec]: m) {
            if(vec.size() < 2)  continue;
            vector<int> tmp(vec);
            sort(tmp.begin(), tmp.end(), greater<int>());
            ans = max(ans, tmp[0]+tmp[1]);
        }  
        return ans;
    }
};

另一种写法(from AcWing)

class Solution {
public:
    int maximumSum(vector<int>& nums) {
        map<int, int> hash;
        int res = -1;
        for(int num: nums) {
            int x = 0, y = num;
            while(y)    x += y%10, y /= 10;
            if(hash.count(x))   res = max(res, hash[x]+num), hash[x] = max(hash[x], num);  
        }
        return res;
    }
};

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

3.1 题目描述

给你一个下标从 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 个数位后，nums = [“2”,”3”,”1”,”4”] 。最小的数字是 1 ，下标为 2 。

裁剪到剩 3 个数位后，nums 没有变化。第 2 小的数字是 251 ，下标为 2 。

裁剪到剩 2 个数位后，nums = [“02”,”73”,”51”,”14”] 。第 4 小的数字是 73 ，下标为 1 。

裁剪到剩 2 个数位后，最小数字是 2 ，下标为 0 。
注意，裁剪后数字 “02” 值为 2 。

示例2：

输入： nums = [“24”,”37”,”96”,”04”], queries = [[2,1],[2,2]]
输出： [3, 0]
解释：

裁剪到剩 1 个数位，nums = [“4”,”7”,”6”,”4”] 。第 2 小的数字是 4 ，下标为 3 。
有两个 4 ，下标为 0 的 4 视为小于下标为 3 的 4 。

裁剪到剩 2 个数位，nums 不变。第二小的数字是 24 ，下标为 0 。

3.2 思路

直接模拟即可，然后对处理后的vector进行排序，这里创建一个id数组来存储原vector的下标，然后引用原vector对id数组进行排序，即可获得按降序排序的数组对应的下标。

class Solution {
    int handle(vector<string>& vec, vector<int> query) {
        int n = vec.size(), size = vec[0].size();
        if(query[1] < size) {
            for(int i = 0; i < n; ++i) {
                vec[i] = vec[i].substr(size-query[1]);
            }
        }
        vector<int> id(n);
        iota(id.begin(), id.end(), 0);
        sort(id.begin(), id.end(), [&](int i, int j){
            if(vec[i] == vec[j])    return i < j;
            return vec[i] < vec[j];
        });
        return id[query[0]-1];
    }
public:
    vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& queries) {
        vector<int> ret;
        for(vector<int> query: queries) {
            vector<string> tmp(nums);
            ret.emplace_back(handle(tmp, query));
        }
        return ret;
    }
};

更快的写法：不使用substr，将原数组转换为pair，其中first为原数组元素，second为原数组元素对应的下标，然后对这个数组的first按倒数trim个字符进行排序即可。(from AcWing)

class Solution {
public:
    vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& queries) {
        int n = nums.size(), m = queries.size(), len = nums[0].length();
        vector<pair<string, int>> strs(n);
        for(int i = 0; i < n; ++i)  strs[i] = {nums[i], i};
        vector<int> ret;
        for(auto &vec: queries) {
            int trim = vec[1], index = vec[0];
            sort(strs.begin(), strs.end(), [&](pair<string, int>& a, pair<string, int>& b) {
                for(int i = len - trim; i < len; ++i) 
                    if((a.first)[i] < (b.first)[i]) return true;
                    else if((a.first)[i] > (b.first)[i])    return false;
                return a.second < b.second;
            });
            ret.emplace_back(strs[index-1].second);
        }
        return ret;
    }
};

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

4.1 题目描述

给你两个正整数数组 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 中的所有元素。
没有任何办法可以达到这一目的。

4.2 思路

题目的意思就是遍历nums,找到一个最小的可以整除numsDivide中的每一个数的数，然后返回nums数组中小于这个数的个数。

要求是求一个能够整除numsDivide中的所有数，那个这个数就必须是所有数的公约数，因而把问题转换为：求numsDivide数组的最大公约数tmp，并在nums数组中找到这么一个值，它可以整除tmp,如果能找到这个数，那么就返回nums中小于tmp的元素个数，否则返回-1.

因此，我们首先求numsDivide的最大公约数tmp，然后将nums按升序进行排序，遍历排序后的nums，当检测到nums[i]可以整除tmp，也就是tmp%nums[i]==0时，说明当前这个nums[i]就是我，我们要找的那个数，那么需要删除的就是比这个数小的元素，也就是i。当i为数组长度时说明没有找到这个数使得nums[i]可以整除numsDivide中的所有数，返回-1。

遍历nums数组时，可以额外进行判断，当nums[i] > val,此时显然就已经找不到一个数可以满足要求，直接返回-1.

class Solution {
    int gcd(int a, int b) {
        if(!b)  return a;
        return gcd(b, a%b);
    }
public:
    int minOperations(vector<int>& nums, vector<int>& numsDivide) {
        sort(nums.begin(), nums.end());
        int tmp = numsDivide[0];
        for(int i = 1; i < numsDivide.size(); ++i) 
            tmp = gcd(tmp, numsDivide[i]);
        int index = 0;
        for(; index < nums.size(); ++index) {
            if(nums[index] > tmp)   return -1;    
            else if(tmp % nums[index] == 0) break;
        }
        return index==nums.size() ? -1 : index;
    }
};