LeetCode Week Contest #235

A. Truncate Sentence

思路简单，按空格作为单词的分隔符，返回前k个单词（注意包含空格）

class Solution:
    def truncateSentence(self, s: str, k: int) -> str:
        return " ".join(s.split(' ')[:k])

B. Find the Users Active Minutes

本题实际上是一个implementation的题，思路简单。 为了代码的简洁，可以使用map<int, set<int>>该数据结构进行讨论。

#define vt std::vector
class Solution {
public:
    vector<int> findingUsersActiveMinutes(vector<vector<int>>& logs, int k) {
        vt<int> ans(k, 0);
        map<int, set<int>> ct;
        
        for (auto v: logs) ct[v[0]].insert(v[1]);
        for (auto [id, s]: ct) if (s.size() <= k) ++ ans[s.size() - 1];

        return ans;
    }
};

C. Minimum Absolute Sum Difference

这题要求你在数组num1中用任意一个元素替换另一个元素，使得\(\sum|nums1[i] - nums2[i]|\)的值最小。

显然，对于nums1中的每个值x，我们可以替换成：

• 大于等于x的最小数
• 小于等于x的最大数

这两种操作，用二分查找可以快速实现，时间复杂度为\(\mathcal{O(n\log n)}\)。

#define vt std::vector
#define all(x) x.begin(), x.end()
#define lb lower_bound
const int mod = 1e9 + 7;
class Solution {
public:
    int minAbsoluteSumDiff(vector<int>& f1, vector<int>& f2) {
        int n = f1.size();
        vt<int> f = f1;
        sort(all(f));
        int midx = -1, exc = -1, mxd = -1, cur;
        
        // type(iter) := std::vector<int>::iterator
        auto update = [&](auto iter, int i){
            int will = abs(*iter - f2[i]);
            int dlt = cur - will;
            if (dlt > mxd) mxd = dlt, midx = i, exc = *iter;
        };
        
        rep (i, 0, n){
            cur = abs(f1[i] - f2[i]);
            auto it = lb(all(f), f2[i]);
            int will, dlt;
            if (it != f.begin()) update(prev(it), i);
            if (it != f.end()) update(it, i);
        }

        f1[midx] = exc;
        ll sum = 0;
        rep (i, 0, n) sum += abs(f1[i] - f2[i]);
        return int(sum % mod);
    }
};

D. Number of Different Subsequence GCDs

这题刚开始看错了题目！！，请注意该题中的GCD的定义为：数组中所有元素的最大约数。

结合给定的数据范围1 <= nums.length <= 10^5; 1 <= nums[i] <= 2 * 10^5。可以给出如下思路：

• 首先设置use数组代表数字x是否存在
• 遍历每个元素i，令j <- j + i | j_0 = i，即在范围内所有可能出现的约数包含i的元素j。并在其存在的情况下计算他们的gcd并判断适合和i相同。

inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
const int maxn = 2e5 + 50;
int use[maxn];
class Solution {
public:
    int countDifferentSubsequenceGCDs(vector<int>& nums) {
        int n = nums.size(), ans = 0;
        memset(use, 0, sizeof(use));
        for (int x: nums) use[x] = 1;
        
        for (int i = 1; i <= 200000; ++ i){
            int cur = -1;
            for (int j = i; j <= 200000; j += i){
                if (use[j]){
                    if (cur == -1) cur = j;
                    else cur = gcd(cur, j);
                }
            }
            if (cur == i) ++ ans;
        }
        
        return ans;
    }
};

后记

今天早上没起来，就没有打实时的。VP的时候发现最后一题好难，结果最后发现看错了题目，我看的题目是：

假设数组\(a\)的gcd的含义为\(\gcd(a[1], \gcd(a[2], \gcd(\cdots)))\)。请统计数组\(b\)所有子序列不同gcd值的数量。

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 2 * 10^5

还不知道咋做，等会思考下有机会补坑。