这周主要刷往期周赛题。今天刷下来最大的感想，是多想想再写。很多细节如果一开始没注意，后面再改会很浪费时间。事实上两个中等题如果静下心来想，大多能写出来。

1. 可被三整除的偶数的平均值

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

周赛简单题，能被3整除的偶数，即模6为0的数，遍历一遍即可。

代码

class Solution {
public:
    int averageValue(vector<int>& nums) {
        int sum=0;
        int res=0;
        int count=0;
        int numsLen=nums.size();
        for (int i=0;i<numsLen;++i) {
            if (nums[i]%6==0) {
                ++count;
                sum+=nums[i];
            }
        }
        if (count!=0) res=sum/count;
        return res;
    }
};

2. 最流行的视频创作者

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

用两个map，mp1存储每个作者对应的流行度，以及mp2每个作者对应的播放量最高的作品序号（i）。

先一轮循环初始化每个作者mp2为-1。

接着一轮循环累加每个作者的流行度，更新最高流行度记录。顺便更新每个作者最火的作品序号。这里注意下，如果播放量相同，记录视频ID字典序靠前的一个。所以写一个辅助函数dir，返回两个字符串中字典序靠前的一个。

再来一轮遍历mp1，如果流行度跟最高流行度相等，就把作者和作者对应的最火的的视频加入最终返回的答案变量ans中。

时间复杂度应该比O(n)高一些。

代码

class Solution {
private:
    string dir(const string& a,const string& b) {
        string c=a,d=b;
        if (a.size()>b.size()) {
            c=b;
            d=a;
        }
        for (int i=0;i<c.size();++i) {
            if (int(c[i])<int(d[i])) return c;
            else if (int(c[i])>int(d[i])) return d;
        }
        return c;
    }
public:
    vector<vector<string>> mostPopularCreator(vector<string>& creators, vector<string>& ids, vector<int>& views) {
        vector<vector<string>> ans; //答案
        map<string,long> mp1; //作者对应流行度
        map<string,int> mp2; //作者播放量最高的作品序号
        long highest=0; //最高的播放量
        int n=ids.size();
        for (int i=0;i<n;++i) {
            mp2[creators[i]]=-1;
        }

        for (int i=0;i<n;++i) {
            mp1[creators[i]]+=views[i]; //统计每个作者的流行度
            highest=mp1[creators[i]]>highest?mp1[creators[i]]:highest;
            if (mp2[creators[i]]==-1) mp2[creators[i]]=i;
            else {
                if (views[mp2[creators[i]]]<views[i]) mp2[creators[i]]=i;
                else if (views[mp2[creators[i]]]==views[i]) {
                    if (dir(ids[mp2[creators[i]]],ids[i])==ids[i]) mp2[creators[i]]=i;
                }
            }
        }

        for (auto elem:mp1) {
            if (elem.second==highest) ans.push_back(vector<string>{elem.first,ids[mp2[elem.first]]});
        }
        return ans;
    }
};

3. 美丽整数的最小增量

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

打草稿观察一下就能发现规律。流程也不难处理，但有几处细节要注意。

首先建议使用list存储各位数字。因为n的上限比较大，如果使用数组，要么一开始就分配上 限空间，要么慢慢扩容。前者容易碰到溢出问题，且每次都用最大空间，也很浪费；后者囿于vector本身的性质，扩容时有较大消耗。所以使用这里使用list，便于

代码

class Solution {
public:
    long long makeIntegerBeautiful(long long n, int target) {
        list<int> nums;
        int sum=0;
        int len=0;
        long long ans=0;
        while (n!=0) {
            sum+=n%10;
            nums.push_back(n%10);
            n/=10;
        }
        nums.push_back(0);

        if (sum==target) return ans;
        int i=0;
        for (auto iter=nums.begin();sum>target;++iter,++i) {
            if (*iter==0) continue;
            sum-=*iter-1;
            auto iter2=iter;
            int next=1;
            ++iter2;
            while (next==1) {
                ++(*iter2);
                if (*iter2==10) {
                    *iter2=0;
                    ++iter2;
                    sum-=9;
                } else next=0;
            }
            ans+=pow(10,i)*(10-*iter);
        }
        return ans;
    }
};

4. 差值数组不同的字符串

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

往期竞赛题。思路没问题，做法也没问题，但一个细节没注意又浪费了我的时间。竞赛时犯这种低级错误太不应该了。我先把difference初始化了，后面添加元素时没有用下标，而是push_back。太蠢了。

代码

class Solution {
public:
    string oddString(vector<string>& words) {
        int n=words[0].size();
        int m=n-1;
        int l=words.size();
        vector<vector<int>> difference;
        for (int i=0;i<l;++i) {
            vector<int> temp;
            for (int j=1;j<n;++j) {
                temp.push_back(int(words[i][j])-int(words[i][j-1]));
            }
            difference.push_back(temp);
        }
        int ans=-1;
        if (difference[0]!=difference[1]) {
            if (difference[0]==difference[2]) ans=1;
            else ans =0;
        }
        else {
            for (int i=1;i<l;++i) {
                if (difference[i]!=difference[0]) {
                    ans=i;
                    break;
                }
            }
        }
        return words[ans];

    }
};

5. 距离字典两次编辑以内的单词

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

暴力法，时间复杂度O(mnl)，m和n是两个字符串数组长度，l是字符串长度。

没想到暴力法几乎双百。以后竞赛里还是首先考虑暴力法吧。

代码

class Solution {
public:
    vector<string> twoEditWords(vector<string>& queries, vector<string>& dictionary) {
        vector<string> ans;
        int m=queries.size(),n=dictionary.size();
        for (int i=0;i<m;++i) {
            for (int j=0;j<n;++j) {
                if (queries[i].size()!=dictionary[j].size()) continue;
                int distance=0;
                for (int k=0;k<queries[i].size();++k) {
                    if (queries[i][k]!=dictionary[j][k]) {
                        ++distance;
                        if (distance>2) break;
                    }
                }
                if (distance<=2) {
                    ans.push_back(queries[i]);
                    break;
                }
            }
        }
        return ans;
    }
};

6. 摧毁一系列目标

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

效率不佳，但至少能跑。打草稿后发现其实就是把原始数组取模，然后看哪个数字出现的最多（可能有多个），将其对应位置的原始数字凑到一起，取最小的即可。应该还有优化空间。

代码

class Solution {
public:
    int destroyTargets(vector<int>& nums, int space) {
        vector<int> nums_copy=nums;
        for (int i=0;i<nums_copy.size();++i) nums_copy[i]=nums_copy[i]%space;
        map<int,int> mp;
        for (auto num:nums_copy) ++mp[num];
        int king=nums_copy[0];
        map<int,int> kings;
        for (auto elem:mp) king=elem.second>mp[king]?elem.first:king;
        for (auto elem:mp) if (elem.second==mp[king]) kings[elem.first]=1;
        vector<int> record;
        for (int i=0;i<nums_copy.size();++i) {
            if (kings[nums_copy[i]]==1) record.push_back(nums[i]);
        }
        int ans=INT_MAX;
        for (auto elem:record) ans=elem<ans?elem:ans;
        return ans;
    }
};

7. 下一个更大元素 IV

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

必须承认用了取巧的做法。常规的暴力法时间复杂度是n的平方，在面对最后几个特殊的用例时必然超时，于是我稍微剪了下枝，一下使得超时变成用时超过90%通过者。

代码

class Solution {
public:
    vector<int> secondGreaterElement(vector<int>& nums) {
        vector<int> ans;
        int n=nums.size();
        if (n==1) return vector<int>{-1};
        if (n==2) return vector<int> {-1,-1};
        for (int i=0;i<n-2;++i) {
            // 这个判断语句用于剪枝
            if (i>0&&((nums[i]==nums[i-1])||nums[i]-nums[i-1]==-1)) {
                ans.push_back(ans[i-1]);
                continue;
            }
            bool flag=false;
            int sign=-1;
            for (int j=i+1;j<n;++j) {
                if (nums[j]>nums[i]) {
                    if (flag==false) {
                        flag=true;
                        continue;
                    } else {
                        sign=nums[j];
                        break;
                    }
                }
            }
            ans.push_back(sign);
        }
        ans.push_back(-1);
        ans.push_back(-1);
        return ans;
    }
};

8. 判断两个事件是否存在冲突

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

先写个辅助函数用于判断两个时间那个在时间线上更靠后，然后利用这个函数将两个事件按起始时间对齐一下，再判断先发生事件的终止时间，是否大于等于后发生事件的起始时间。

代码

class Solution {
private:
    bool isGreatOrEqual(string& a,string& b) {
        int h1=(int(a[0])-98)*10+int(a[1])-98;
        int m1=(int(a[3])-98)*10+int(a[4])-98;
        int h2=(int(b[0])-98)*10+int(b[1])-98;
        int m2=(int(b[3])-98)*10+int(b[4])-98;
        if (h1==h2) return m1>=m2;
        else return h1>h2;
    }
public:
    bool haveConflict(vector<string>& event1, vector<string>& event2) {
        if (isGreatOrEqual(event1[0],event2[0])) {
            return isGreatOrEqual(event2[1],event1[0]);
        } else return isGreatOrEqual(event1[1],event2[0]);
    }
};

9. 最大公因数等于 K 的子数组数目

难度

• Easy
• Medium
• Hard

完成情况

• 独立完成
• 参考思路
• 参考答案

思路

跟本周周赛的一个题几乎完全一样，只不过最小公倍数换成了最大公因数。我一开始以为这个变化会导致原有解法失效，但却几乎完全一样。

代码

class Solution {
private:
    int gcd(int a,int b) {
        if (a<b) {
            int temp=a;
            a=b;
            b=temp;
        }
        if (b!=0) {
            return gcd(b,a%b);
        }
        else return a;
    }
public:
    int subarrayGCD(vector<int>& nums, int k) {
        int ans=0;
        int n=nums.size();
        for (int i=0;i<n;++i) {
            int init=nums[i];
            for (int j=i;j<n;++j) {
                init=gcd(init,nums[j]);
                if (init%k!=0) break;
                if (init==k) ++ans;
            }
        }
        return ans;
    }
};