Leetcode第281次周赛解题报告

打比赛的时候LEETCODE服务器崩了，结果走了段时间回来时候做迟了。
其实题目的思路都非常简单，只是反应太慢了，还是不熟练，好几道题因为没有认真审题走了几次弯路。

6012. 统计各位数字之和为偶数的整数个数
打大暴力过了，事实上可以判断进位

class Solution {
public:
    bool ok(int x) {
        int s = 0;
        while(x != 0) {
            s += x % 10;
            x /= 10;
        }
        return s%2==0;
    }
    int countEven(int num) {
        int ans = 0;
        for(int i = 1;i <= num;i++) {
            ans += ok(i);
        }
        return ans;
    }
};

6013. 合并零之间的节点
遍历链表，每遇到一个0记录一下当前的和，然后将该计数器置0
最后产生一个新的链表

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var mergeNodes = function(head) {
    let cnt = 0
    let ans = new ListNode()
    let sum = 0
    let res = []
    while(head!==null) {
        if(head.val==0) {
            res.push(sum)
            sum = 0
        }else{
            sum += head.val
        }
        head = head.next
    }
    let x = ans
    for(let i = 1;i < res.length;i++){
        x.next = new ListNode(res[i])
        x = x.next
    }
    return ans.next
};

6014. 构造限制重复的字符串
这道题写的时候理解错题意了，先写了一发DFS，发现并不是所有的字母都要被用到

其实策略就是取当前最大的剩余字母repeat次，假如还有除了该字母的其他字母，就插入一个进去，直至没有可以插入的字母。

class Solution {
private:
    vector<int> cnt;
    vector<int> ans;
    int size;
    int repeatL;
public:
    bool dfs(int pos,int last,int repeat){
        if(pos == size) return true;
        for(int i = 26;i >= 0;i--){
            if(cnt[i]>0) {
                int newrep = repeat + 1;
                if(last!=i) {
                    newrep = 1;
                }else{
                    if(repeat==repeatL) continue;
                }
                ans[pos] = i;
                cnt[i]-=1;
                bool res = dfs(pos+1,i,newrep);
                if(res) return true;
                cnt[i]+=1;
            }
        }
        return false;
    }
    string repeatLimitedString(string s, int repeatLimit) {
        repeatL = repeatLimit;
        size = s.size();
        ans = vector<int>(size,-1);
        cnt = vector<int>(27,0);
        for(auto  i:s) {
            cnt[i-'a']++;
        }
        //dfs(0,-1,0);
        string a = "";
        //for(auto i : ans) {
            //a.append(1,char('a'+i));
        //}
        for(int i = 26;i >= 0;i--) {
            while(cnt[i] > 0){
                int rep = min(cnt[i],repeatLimit);
                a.append(rep,char('a'+i));
                cnt[i]-=rep;
                if(cnt[i] > 0) {
                    int x = -1;
                    for(int j = i-1;j >= 0;j--) {
                        if(cnt[j]>0) {
                            x = j;
                            break;
                        }
                    }
                    if(x==-1) return a;
                    a.append(1,char('a'+x));
                    cnt[x]--;
                }
            }
        }
        return a;
    }
};

6015. 统计可以被 K 整除的下标对数目
服了 重写完第三题以后这题没来得及交。
暴力方法：两两比较，最后加和。
最后观察了二十分钟发现能够使题设成立的两个数(a,b)有如下规律
gcd(a,k) * gcd(b,k) % k == 0 => a * b % k == 0
k的取值是较小的，因此只需要对比各个数和K的gcd然后计算组合数即可

class Solution {
public:
    long long coutPairs(vector<int>& nums, int k) {
        long long ans = 0;
        int n = nums.size();
        unordered_map<long long, long long> gcMap;
        for (int num : nums)
            gcMap[__gcd(num, k)]++;
        for (auto [k1, v1] : gcMap)
            for (auto [k2, v2] : gcMap) {
                if (k1 * k2 % k == 0) {
                    if (k1 < k2)
                        ans += v1 * v2;
                    else if (k1 == k2)
                        ans += v1 * (v1 - 1) / 2;
                }
            }
        return ans;
    }
};