leetcode281周赛

竞赛链接

T1: 6012. 统计各位数字之和为偶数的整数个数

---

思路

暴力

Code

class Solution {
public:
    bool cheak(int x){
        int sum=0;
        while(x>0){
            sum+=(x%10);
            x/=10;
        }
        return sum%2==0;
    }
    int countEven(int num) {
        int ans=0;
        for(int i=2;i<=num;i++){
            if(cheak(i))
                ans++;
        }
        return ans;
    }
};

复杂度分析

时间复杂度：O(NlogN))
空间复杂度：O(1)

T2: 6013. 合并零之间的节点

---

思路

模拟

Code

class Solution {
public:
    ListNode* mergeNodes(ListNode* head) {
        vector<int>ans;
        int flag=0,sum=0;
        while(head){
            if(head->val==0&&flag==1){
                ans.emplace_back(sum);
                sum=0;
            }
            else if(head->val==0&&flag==0)
                flag++;
            else if(head->val!=0)
                sum+=head->val;    

            head=head->next;
        }
        ListNode* p=new ListNode(0);
        ListNode* h=p;
        for(auto& i:ans){
            p->next=new ListNode(i);
            p=p->next;
        }
        return h->next;
    }
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)

T3: 6014. 构造限制重复的字符串

---

思路

大根堆，从大往小取

Code

class Solution {
public:
    map<char,int>mp;
    priority_queue<int,vector<int>>q;
    string repeatLimitedString(string s, int re) {
        for(auto& i:s){
            mp[i]++;
        }    
        for(auto& i:mp){
            q.push(i.first-'a');
        }
        string ans="";
        while(1){
            if(ans==""){
                char a=q.top()+'a';
                if(mp[a]>=re){
                    for(int i=0;i<re;++i)
                        ans+=a;
                    mp[a]-=re;
                    if(mp[a]==0)
                        q.pop();
                }
                else{
                    for(int i=0;i<mp[a];++i)
                        ans+=a;
                    q.pop();
                    mp[a]=0;
                }
            }
            else{
                if(*ans.rbegin()!=(q.top()+'a')){
                    char a=q.top()+'a';
                    if(mp[a]>=re){
                        for(int i=0;i<re;++i)
                            ans+=a;
                        mp[a]-=re;
                        if(mp[a]==0)
                            q.pop();
                    }
                    else{
                        for(int i=0;i<mp[a];++i)
                            ans+=a;
                        q.pop();
                        mp[a]=0;
                    }
                }
                else{
                    char a=q.top()+'a';
                    q.pop();
                    if(q.empty()){
                        break;
                    }
                    char b=q.top()+'a';
                    ans+=b;
                    mp[b]--;
                    if(mp[b]==0)
                        q.pop();
                    q.push(a-'a');
                }
            }
            if(q.empty()){
                break;
            }
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：O(N\left|Σ\right|)
• 空间复杂度：O(N + \left|Σ\right|)

T4: 6015. 统计可以被 K 整除的下标对数目

---

思路

数学：gcd+根号筛（获取所有因数）

Code

class Solution {
public:
    int mp[100010],b[100010];
    void add(int x){
        for(int i = 1 ; i<=x/i ; i++){   
            if( x%i == 0) {             
                mp[i]++;
                if(i!=x/i)
                    mp[x/i]++;
            }
        }
    }
    long long coutPairs(vector<int>& nums, int k) {
        for(auto& i:nums)  //每个数的贡献为__gcd(i,k)
            i=__gcd(i,k);

        long long ans=0,cnt=0;
        for(auto& i:nums){
            ans+=mp[k/i];  //累加目标数k/i的数量
            add(i);   //累计每个数根号筛后的贡献
        }         
        return ans;
    }
};

复杂度分析

• 时间复杂度：O(NlogK+τ^2(K)),其中 τ(K) 为 K 的正因子个数
• 空间复杂度：O(τ(K))

个人总结

---

本次周赛，开局lc网络崩溃，等了10多分钟后才开始写，t2题看错题浪费一会时间，t3粗心wa了2次，t4又卡壳了，数论不熟悉呀。。