1.数组能形成多少数对

6120. 数组能形成多少数对

题目描述

思路分析

这道题比较简单，用哈希表保存每个数字的个数，那么对数就是个数除以2，剩余个数就是取余2，循环哈希表得到结果

时间复杂度O(n)，空间复杂度O(n)

题目代码

class Solution {
public:
    vector<int> numberOfPairs(vector<int>& nums) {
        unordered_map<int,int> m;
        int cnt=0,remain=0;
        for(auto it:nums)m[it]++;
        
        for(auto it:m)cnt+=it.second/2,remain+=it.second%2;
        return {cnt,remain};
    }
};
1
2
3
4
5
6
7
8
9
10
11

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

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

题目描述

思路分析

这道题思路也比较简单，遍历一遍按照数位和将值存入哈希表，然后遍历哈希表取出最大的两个值
因为要取出最大的两个值，所以需要进行排序
第一种是在遍历前排序，第二种是在遍历哈希表的时候排序都可以，个人偏向后面一种，时间更短。

题目代码

class Solution {
public:
    int sum(int i)
    {
        int res=0;
        while(i)res+=i%10,i/=10;
        return res;
    }
    int maximumSum(vector<int>& nums) {
        //sort(nums.begin(),nums.end());
        int res=-1;
        unordered_map<int,vector<int>> m;
        
        for(auto it:nums)m[sum(it)].push_back(it);
        
        for(auto it:m)
        {
            vector<int> mid=it.second;
            if(mid.size()<2)continue;
            sort(mid.begin(),mid.end());
            int size=mid.size();
            res=max(res,mid[size-1]+mid[size-2]);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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

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

题目描述

思路分析

我的做法是首先预处理哈希表
哈希表保存的是每个位数的所有字符串的信息（字符串信息用vector保存，然后里面保存字符串和字符串当前的位置）
因为字符串大小我们可以通过排序完成，位置随着字符串排序而排
最后遍历询问数组只需找到哈希表相应位置即可。

题目代码

class Solution {
public:
    vector<int> smallestTrimmedNumbers(vector<string>& nums, vector<vector<int>>& queries) {
        int size_n=nums[0].size();
        unordered_map<int,vector<pair<string,int>>> m;

        // 预处理 <位数<字符串，位置>>
        for(int i=0;i<nums.size();i++)
        {
            int weishu=1;
            string mid;
            for(int j=size_n-1;j>=0;j--)
            {
                mid=nums[i][j]+mid;
                m[weishu++].push_back({mid,i});
            }
        }
        
        vector<int> res;
        for(auto it:queries)
        {
            int weishu=it[1],daxiao=it[0];
            auto v=m[weishu];
            sort(v.begin(),v.end());
            res.push_back(v[daxiao-1].second);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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

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

题目描述

思路分析

1.因为要整除所有numsDivide 所以我们可以遍历求出数组所有数的最大公因数
2.因为要求出最小值，所以我们排序从小到大进行排除

题目代码

class Solution {
public:
    int minOperations(vector<int>& nums, vector<int>& numsDivide) {
        sort(nums.begin(),nums.end());
        
        //  求最大公因数
        int gong=numsDivide[0];
        for(int i=1;i<numsDivide.size();i++)
            gong=__gcd(gong,numsDivide[i]);

        int res=0;
        for(auto it:nums)
            if(gong%it!=0)res++;
            else return res;
        
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

感想与总结

这次比赛题目头一次将所有题做完了，但是这次题目按以往来说很简单了（尤其是hard题，感觉跟简单题差不多，因为以为很难就没敢做，第三题思路想错了就去看了看第四题，以前第四题根本就不看的），所以很多时候还是每道题都要观看一下。
第三题也是小失误，一来没注意范围就选择用int类型，结果后面一看肯定要爆int，当然就不能用数值来存