leetcode 第 235 场算法比赛

零、背景

这次比赛前三题太水了，第四题自己的思路对了，但是实现较复杂，被卡超时了，最后 STL vector 改成数组形式就过了。

比赛代码：https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/2/235

一、截断句子

题意：若干个单词组成一个句子字符串，单词之间使用一个空格分隔。
求输出前 k 个单词组成的句子。

思路：最笨的方法是先把句子转化为单词列表，取前 k 个，再拼接为句子字符串即可。

小技巧：直接查空格的个数，第 k 个空格设置为字符串结束符 \0 即可。
当然，其他语言，在要设置 \0 的位置，求前缀子串即可。

string truncateSentence(string s, int k) {
    int word_num = 0;
    for(auto& c: s){
        if(c == ' '){
            word_num++;
        }
        if(word_num == k){
            c = '\0';
        }
    }
    return s.c_str();
}

二、查找用户活跃分钟数

题意：给出每个用户 ID 的活跃时间，可以统计出每个用户的活跃次数（相同用户相同时间只记一次活跃）。
求活跃次数分别是 1 到 k 的用户个数。

思路：先正向统计每个用户的活跃次数，然后相反统计活跃次数对应的用户数。

vector<int> findingUsersActiveMinutes(vector<vector<int>>& logs, int k) {
    unordered_map<int, unordered_set<int>> m;
    for(auto& v: logs){
        m[v[0]].insert(v[1]);
    }
    vector<int> ans(k, 0);
    for(auto& p: m){
        int num = p.second.size();
        if(num > k) continue;
        ans[num-1]++;
    }
    return ans;        
}

三、绝对差值和

题意：给两个长度相同的数组 nums1 和 nums2。
定义绝对差值和：两个数组所有位置对应的两个数字的差绝对值之和。
现在增加一个选择：可以用 nums1 的任意一个元素，最多替换一次 nums1 的其他位置的元素。
求多了一个选择后，最小的绝对差值之和。

思路：由于是最多替换一次，可以理解为不替换和替换一次。

不替换，就是原数组计算出的答案。

替换一次，就需要考虑替换哪个位置，有 n 个位置。
确定位置后，还需要考虑替换哪个元素，又有 n 个元素。

总复杂度：O(n^2)

优化：确定位置后，替换元素的最优解是确定的。
如果先对 nums1 排序，在坐标轴上画出绝对值差，会发现这个曲线是类似于抛物线的 V 型曲线。

所以我们可以三份做这道题找到最优解。

当然，进一步分析这个绝对值差，会发现我们的目标是在数组中找一个离指定数字最近的元素。

那最近的元素的位置有啥特征呢？
显然，最近的是相等的元素，其次是第一个大于或第一个小于的元素。

所以我们可以直接使用二分查找找到大于等于和小于等于的元素，取最优值即可。

三分和二分的复杂度都是O(n log(n))

int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
    int n = nums1.size();
    set<int> s; // 类似于排序，并去重了

    ll base = 0;
    for(int i=0;i<n;i++){
        base += dis(nums1[i], nums2[i]);
        s.insert(nums1[i]);
    }


    ll ans = base;
    for(int i=0;i<n;i++){
        auto it = s.lower_bound(nums2[i]); // 第一个大于等于的
        if(it == s.end()) it--; // 没找到，取最后一个


        ll tmp = base - dis(nums1[i], nums2[i]) + dis(*it, nums2[i]) ;
        if(tmp < ans) ans = tmp;


        if(it != s.begin()) it--;  //第一个小于等于的
        tmp = base - dis(nums1[i], nums2[i]) + dis(*it, nums2[i]) ;
        if(tmp < ans) ans = tmp;
    }

    return ans % 1000000007;
}

四、序列中不同最大公约数的数目

题意：给 n 个数字，每个子序列可以求出一个最大公约数。
求所有子序列可以得到的不同的最大公约数个数。

思路：

方法一：排列组合

最简单的方法是排列组合求出所有子序列，即选与不选。

复杂度O(2^N)
通过测试用例：16 / 39
我做了不少剪枝优化，但还是超时了，必须的。

方法二：枚举最大公约数。

枚举每个最大公约数 max_gcd，判断数组中的子序列，是否可以求出最大公约数 max_gcd 即可。

显然可以推导出几个性质。

性质1：如果 max_gcd 是一个答案（是某个子序列的最大公约数），则那些元素的约数中肯定有 max_gcd（废话，是最大公约数了，肯定是约数）。
性质2：max_gcd 如果是某个子序列的答案，那么所有的约数有 max_gcd 的元素，组成子序列后，求出的最大公约数依旧是 max_gcd。

性质2 是啥意思呢？
举个例子大家就明白了。

假设数组是 [4, 8, 16]。
可以确定 max_gcd=4 是答案，因为子序列[4,8]的最大公约数是 4。 根据性质2，4 的所有倍数元素，即4,8,16 组成的子序列的最大公约数肯定也是 4。

性质2 可以使用反证法证明，这里就不再证明了。

有了性质2，我们就可以做这道题了。

枚举最大公约数，然后找到这个最大公约数的所有倍数元素，判断这些元素能否计算得到当前的最大公约数即可。

有点绕，还是以[4, 8, 16]为例，来解释下最后一句话是啥意思。

例如 2 ，找到的所有倍数元素是 4,8,16，求出的最大公约数是 4。
所以 2 不是答案。

那怎么找到一个数字的所有倍数元素呢？

我比赛的时候，想的是预处理所有数字，计算出每个元素的约数，建立约数到元素的映射关系。

最开始，我使用暴力方法找出所有的元素的所有约数。
复杂度：O(n^2)
通过测试用例：14 / 39
显然超时了。

后来，我预先打素数表，统计素约数的个数，再组合求出所有约数。
复杂度：O(n log(n))。
通过测试用例：37 / 39
发现还是超时了，可能申请了大量内存，常数有点高。

赛后，看第一名的代码，思想差不多，但是没想到可以直接可以使用素数筛法来做这道题。

简单来说就是不需要预选统计一个数字的倍数元素列表。
而是实时的判断指定数字的倍数，是不是在元素列表中。
复杂度计算：N/1 + N/2+ ... +N/N。
复杂度：O(n log(n))
关于这个公式的具体复杂度，比较难计算，大家当做近似上面的复杂度即可。

int countDifferentSubsequenceGCDs(vector<int>& nums) {
    int max_val = 0;
    for (const auto v : nums) {
        max_val = max(max_val, v);
    }
        
    vector<bool> is;
    is.resize(max_val+1, false);
    for (const auto v : nums) {
        is[v] = true;
    }

    int ans = 0;
    for(int i=1;i<=max_val;i++){
        int gcd_val = 0;
        for(int j = i; j <= max_val; j+=i){
            if(!is[j]) continue;
            
            if(gcd_val == 0){
                gcd_val = j;
            }else{
                gcd_val = gcd(gcd_val,  j);
            }
        }
        if(gcd_val == i){
            ans++;
        }
    }
    return ans;
}

求素约数方法优化：

复杂度：O(n log(n))。
通过测试用例：37 / 39
回头看看我的思路，复杂度没问题，就快要过了，有点不甘心。

于是我需要做一些优化，来防止数据量大时，导致在内存上消耗太多无关的时间。
具体来说就是，所有的 vector 换成定长数组，然后一提交，竟然通过了。

代码较长这里就不贴代码了，感兴趣的可以自己去看源码吧（文章头部有源码链接）。

五、最后

这次比赛前三题太水，第四题数据量比较大，卡耗时了，以后不再使用 vector，所有地方都使用定长数组吧。

回头看看最后一题，有点意思。

我的方法是正规思路，统计出每个数字的倍数元素。
方法是求出每个元素的素约数与个数，然后排列组合求出所有约数，约数到元素的反向关系储存下来。

比赛第一名的方法是素数筛法来直接拉求答案。
即对于枚举的每个约数，找到这个约数的所有倍数，对于倍数素数求 gcd，然后判断是否满足性质2。

怎么说呢，比赛第一名的方法虽然简单粗暴，但是确实很巧妙。
关键是这种思路我一般情况下是想不到的，难道这就是差距吗？

思考题：第三题如果是可以交换一次 nums1 数组两个位置的元素，又改怎么做呢？

加油，算法人。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code