正文索引 [隐藏]

传送门

T1：截断句子

思路

签到题，用python会比cpp简单很多。直接按空格split然后分片就行。

代码

class Solution(object):
    def truncateSentence(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: str
        """
        ss = s.split(" ")
        if k == len(ss):
            return s
        ans = " ".join(ss[:k])
        return ans

赛后感觉写的太冗长了，可以精简成一句：

class Solution(object):
    def truncateSentence(self, s, k):
        return " ".join(s.split()[: k])

T2： 查找用户活跃分钟数

思路

hash计数。用一个set来给logs去重，然后用map计数，最后根据出现次数在ans数组里累计就行了。

代码

class Solution {
public:
    vector<int> findingUsersActiveMinutes(vector<vector<int>>& logs, int k) {
        set<pair<int, int>> mys;
        unordered_map<int, int> mp;
        vector<int> ans(k);
        
        for (auto el : logs) {
            mys.insert(make_pair(el[0], el[1]));
        }
        
        for (auto el : mys) {
            mp[el.first]++;
        }
        
        for (auto el : mp) {
            ans[el.second-1]++;
        }
        
        return ans;
    }
};

T3： 绝对差值和

思路

要使最后答案尽可能得小，那就要找到改前与改后值差距最大的来改。我们的思路很清晰：针对所有的nums2，在nums1中找到那个与它最接近的值来算出abs，再从所有这样的abs中得到最小的那个作为答案。

这题数据是1e5，显然直接O(n²)是不可能的。这里可以用二分。

复制一个nums1，在这个复制数组tmp上对每个nums2做lower_bound。因为题设有绝对值，所以我们在找“ 最接近的值 ”时应该同时考虑数轴两边，大于它小于它的都可以算作“接近它”。根据lower_bound的性质，设pos为得到的目标下标，pos-1一定就是“第一个小于val的值的下标”，因为lower_bound本身得到的是“第一个大于等于val的值的下标”。

能在有效时间内枚举每一个nums2，只需要统计它们中的最小值就可以了，最后答案别忘了模1e9+7。

代码

class Solution {
public:
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        if (nums1 == nums2) return 0;
        
        typedef long long ll;
        const int MOD = 1e9 + 7;
        ll diff = 0;

        for (int i = 0; i < nums1.size(); i++) {
            diff += 1ll * abs(nums1[i] - nums2[i]);
        }

        vector<int> tmp(nums1);
        sort(tmp.begin(), tmp.end());
        ll mini = diff;
        for (int i = 0; i < nums1.size(); i++) {
            /*    二分查找第一个   *\
            \* 大于等于nums2[i]的值*/
            int pos = lower_bound(
                tmp.begin(), 
                tmp.end(),
                nums2[i]
            ) - tmp.begin();

            // 检查第一个大于等于nums2[i]的值
            if (pos != nums1.size()) {
                int a = abs(nums1[i] - nums2[i]);
                int b = abs(tmp[pos] - nums2[i]);
                mini = min(mini, diff - a + b);
            }

            // 检查第一个小于nums2[i]的值
            // 二者取其小
            if (pos > 0) {
                /* ---------------------------- *\
                 * lowerbound找到了第一个大于等于
                 * nums2[i]的值,所以在它之前的一个
                 * 位子上一定是第一个小于nums2[i]的
                 * 值.那么往前位移一格就行了      
                \* ---------------------------- */
                pos--;
                int a = abs(nums1[i] - nums2[i]);
                int b = abs(tmp[pos] - nums2[i]);
                mini = min(mini, diff - a + b);
            }
        }

        return mini % MOD;
    }
};

T4： 序列中不同最大公约数的数目

思路

代码