上周的双周赛~

又成双题选手了~

2283. Check if Number Has Equal Digit Count and Digit Value

Analysis

这个简单题很奇怪...大概意思是如果所有的下标i在字符串num中出现的次数与num[i] - '0'相等，就返回 true，反之返回 false。
感觉怪的很...出题人是不是不知道怎么出简单题了？😂

Code

这是当时提交通过的代码：

class Solution {
public:
    bool digitCount(string num) {
        vector<int> cnt(10);
        for(char &ch: num) {
            cnt[ch - '0']++;
        }
        for(int i = 0; i < num.length(); i++) {
            if(num[i] - '0' != cnt[i]) return false;
        }
        return true;
    }
};

题目其实看了挺久的，生怕 WA 了。
实际上，这里也可以换成位运算：

class Solution {
public:
    bool digitCount(string num) {
        vector<int> cnt(10);
        for(char &ch: num) {
            cnt[ch & 15]++;
        }
        for(int i = 0; i < num.length(); i++) {
            if((num[i] & 15) != cnt[i]) return false;
        }
        return true;
    }
};

注意运算符的优先级。

2284. Sender With Largest Word Count

Analysis

这个题实际上是两个题的结合版，一个是统计单词，一个是分割单词。所以，这个题算是在考 hash 和 split。

Code

这是当时提交通过的代码：

class Solution {
public:
    string largestWordCount(vector<string>& messages, vector<string>& senders) {
        map<string, int> mp;
        int n = messages.size(), mmax = INT_MIN;
        for(int i = 0; i < n; i++) {
            int cnt = 0;
            bool flag = true;
            for(char &ch: messages[i]) {
                if(flag && ch != ' ') {
                    cnt++;
                    flag = false;
                } else if(ch == ' ') flag = true;
            }
            mp[senders[i]] += cnt;
            mmax = max(mmax, mp[senders[i]]);
        }
        string ret = "";
        for(auto it = mp.rbegin(); it != mp.rend(); it++) {
            if(it->second == mmax) {
                ret = it->first;
                break;
            }
        }
        return ret;
    }
};

因为题目规定大写字母的字典序小于小写字母，所以要挑出题目规定的字典序最大的那个人。题目虽然说了开头和结尾没有多余的空格，但是中间没保证，所以没有直接统计空格数，而是当遇到单词时统计。另外，注意反向迭代器的遍历操作。
看了其他人的题解，发现这题压根没有中间有多余空格的用例...😂
所以，改简单一点：

class Solution {
public:
    string largestWordCount(vector<string>& messages, vector<string>& senders) {
        map<string, int> mp;
        int n = messages.size(), mmax = INT_MIN;
        for(int i = 0; i < n; i++) {
            int cnt = 0;
            bool flag = true;
            for(char &ch: messages[i]) {
                if(ch == ' ') cnt++;
            }
            mp[senders[i]] += ++cnt;
            mmax = max(mmax, mp[senders[i]]);
        }
        string ret = "";
        for(auto it = mp.rbegin(); it != mp.rend(); it++) {
            if(it->second == mmax) {
                ret = it->first;
                break;
            }
        }
        return ret;
    }
};

2285. Maximum Total Importance of Roads

Analysis

这个题有点意思，大致题意是如何安排结点的值才能使得每条路上结点和的总和最大。
当时一眼看到题目，以为是最短路的逆思维——最长路，想了一会，没什么具体的思路，就放弃了。
现在看了提示后，发现这个题其实跟最短路没有关系，算是涉及到图的结点的度的贪心题。
为了使结果能达到最大，需要按照结点的度来给结点安排值，度越大的结点其值就越大，这样在最终计算时，才能得到最大值。

Code

思路是统计 + 排序 + 贪心，看了提示后才想到的：

class Solution {
public:
    long long maximumImportance(int n, vector<vector<int>>& roads) {
        vector<int> cities(n);
        for(auto &v: roads) {
            cities[v[0]]++;
            cities[v[1]]++;
        }
        vector<int> indices(n);
        iota(indices.begin(), indices.end(), 0);
        sort(indices.begin(), indices.end(), [&](int i, int j) { return cities[i] > cities[j]; });
        int val = n;
        for(int i = 0; i < n; i++) {
            cities[indices[i]] = val--;
        }
        long long ret = 0;
        for(auto &v: roads) {
            ret += (cities[v[0]] + cities[v[1]]);
        }
        return ret;
    }
};

先统计结点的度，然后再按照结点度的大小对下标排序，再按照度的大小给结点赋值，最后累加所有道路的重要性即可。这种对下标排序的方法是第一次参加周赛时，从大佬写的第三个题的题解学来的。
实际上，这个题完全可以不用按照度给下标排序，对度排序后直接做计算就可以了，因为每个结点被计算的次数就是其度的值，所以可以写的简单一些：

class Solution {
public:
    long long maximumImportance(int n, vector<vector<int>>& roads) {
        vector<int> degree(n + 1);
        for(auto &v: roads) {
            degree[v[0]]++;
            degree[v[1]]++;
        }
        sort(degree.begin(), degree.end());
        long long ret = 0;
        for(int i = 0; i <= n; i++) {
            ret += i * (long long)degree[i];
        }
        return ret;
    }
};