Leedcode第235场周赛

Leedcode第235场周赛

Louis 885 2021-04-04

自从补习代码基础列入临时紧急事项清单，就没有一天睡过安稳觉。经过一段时间的刷题练习之后，觉得练习强度还是不够，于是开始参加周赛，并且更新周赛系列的文章。

文章中会出现该周赛的题目&我的解法&大佬的解法。

周赛连接： 第 235 场周赛

截断句子

题目连接：截断句子

我的解法：

标准思路，遍历字符串，遇到空格就截断，并且存一个单词。

class Solution {
public:
    string truncateSentence(string s, int k) {
        string ret = "";
        string temp = "";
        for (char a : s){
            if(k == 0){
                ret.pop_back();
                return ret;
            }
            if(a == ' '){
                //放入ret
                ret += temp;
                ret += " ";
                temp.clear();
                k--;
                //tmp 要先放入空格
            }else{
                temp += a;
            }
        }
        ret += temp;
        return ret;
    }
};

提交时忽略了k等于单词数的时候，将最后一个单词放入输出。罚时5 min。

更好的答案：

class Solution {
public:
    string truncateSentence(string s, int k) {
        for (int index = 0 ; index < s.size() ; index ++){
            if (s[index] == ' '){
                //找到一个空格
                k --;
                if (k == 0){
                    return s.substr(0, index);
                }
            }
        }
        return s;
    }
};

本质上是数单词的空格，不用使用tmp和ret保存单词，直接使用原字符串 统计路过的单词，用原字符串切割输出即可

查找用户活跃分钟数

题目连接：查找用户活跃分钟数

我的解法：

  1. 读一遍输入，存活跃的分钟和用户id，使用set去重
  2. 统计各个用户的活跃时间
  3. 输出结果
class Solution {
public:
    vector<int> findingUsersActiveMinutes(vector<vector<int>> &logs, int k) {
        //先是遍历统计
        //活跃的分钟，活跃的用户id
        map<int, unordered_set<int>> activity_list;
        //顺便存一份各个用户的活跃时间
        map<int, int> activity_time;
        for (auto log : logs) {
            //找一下用户有没有已经操作
            if (activity_list.find(log[1]) == activity_list.end()) {
                activity_list.insert({log[1], {}});
            }
            if (activity_list[log[1]].count(log[0]) == 1) {
                //有操作
                continue;
            } else {
                //无操作
                if (activity_time.find(log[0]) != activity_time.end()) {
                    activity_time[log[0]]++;
                } else {
                    activity_time.insert({log[0], 1});
                }
                activity_list[log[1]].insert(log[0]);
            }
        }
        //再遍历统计结果
        //遍历字典，统计用户数字
        vector<int> ret(k);
        for (const auto &temp : activity_time) {
            if (temp.second > k) {
                continue;
            } else {
                ret[temp.second - 1]++;
            }
        }
        return ret;
    }
};

提交的时候由于没有处理输入的log数小于k的场景，罚了5min

别人的解法：

同样是使用unordered_set去重，但是插入字典的时候不需要判断，直接调用[]来插入即可。

不用另外建一个map来存放数据，直接用set的size即可。

class Solution {
public:
    vector<int> findingUsersActiveMinutes(vector<vector<int>>& logs, int k) {
        unordered_map<int, unordered_set<int>> cnt;
        for (auto &v : logs) {
            cnt[v[0]].insert(v[1]);
        }
        vector<int> ans(k);
        for (auto &p : cnt)
            ans[p.second.size() - 1]++;
        return ans;
    }
};

作者：吴自华
链接：https://leetcode-cn.com/circle/discuss/4dT5t6/view/KG5Sgz/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

绝对值差和

题目链接：绝对差值和

我的解法：

  1. 把最大差值的找出来

  2. 然后再遍历一遍，找一个最佳的替代数字

  3. 累加输出

class Solution {
public:
    int minAbsoluteSumDiff(vector<int> &nums1, vector<int> &nums2) {
        vector<int> abs_v;
        int max_abs = 0;
        int max_abs_index = 0;
        //遍历一遍，找最大差值
        for (int i = 0; i < nums1.size(); i++) {
            abs_v.push_back(abs(nums1[i] - nums2[i]));
            if (abs_v.back() > max_abs) {
                max_abs = abs_v.back();
                max_abs_index = i;
            }
        }

        //遍历第二遍，补最大差值
        nums1[max_abs_index];
        int min_abs = INT_MAX;
        for (int i = 0; i < nums1.size(); i++) {
            min_abs =  min(min_abs, abs(nums1[i] - nums2[max_abs_index]));
        }
        abs_v[max_abs_index] = min_abs;
        int ret = 0;
        for (int i : abs_v) {
            ret += i;
            if (ret >= pow(10, 9) + 7) {
                ret -= pow(10, 9) + 7;
            }
        }
        return ret;
    }

大佬解法：

typedef long long ll;
const ll MOD = 1e9 + 7;

class Solution {
public:
    int minAbsoluteSumDiff(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int> s(nums1);
        sort(s.begin(), s.end());
        ll tot = 0;
        for (int i = 0; i < n; ++i)
            tot += abs(nums1[i] - nums2[i]);
        ll ans = tot;
        for (int i = 0; i < n; ++i) {
            auto it = lower_bound(s.begin(), s.end(), nums2[i]);
            int delta = INT_MAX;
            if (it != s.end())
                delta = abs(nums2[i] - *it);
            if (it != s.begin())
                delta = min(delta, abs(nums2[i] - *prev(it)));
            ans = min(ans, tot - abs(nums1[i] - nums2[i]) + delta);
        }
        return ans % MOD;
    }
};

作者：吴自华
链接：https://leetcode-cn.com/circle/discuss/4dT5t6/view/KG5Sgz/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

尾声

第二题调整的时间太长，导致第三题在时间结束后的30min才pass，不过第一次参赛，还行还行，再接再厉.

周赛结果是2700名左右，下周是万德专场，冲鸭！！！

Leetcode