讨论/题目交流/🏆 第 187 场力扣周赛/
🏆 第 187 场力扣周赛
展开讨论
力扣 (LeetCode)发起于 2020-05-03

旅行终点站

思路

  1. 存一下,刷一下,找一下剩下的

答题

    string destCity(vector<vector<string>>& paths) {
        vector<string> start;
        unordered_set<string> end;
        for (auto& p : paths) {
            start.push_back(p[0]);
            end.insert(p[1]);
        }
        for (auto& s : start) {
            end.erase(s);
        }
        return *end.begin();
    }

是否所有 1 都至少相隔 k 个元素

思路

  1. 记录间隔,当遇到 0 的时候间隔 + 1
  2. 如果没到 k 个 0 就刷出来个 1 ,返回 false

答题

    bool kLengthApart(vector<int>& nums, int k) {
        int t = k;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 1 && t < k) return false;
            t = (nums[i] == 0) ? t + 1 : 0;
        }
        return true;
    }

绝对差不超过限制的最长连续子数组

思路

  1. 使用滑动窗口保持符合条件的子数组,记录最长长度
  2. 怎样确定子数组是否符合条件,需要知道两个关键数据
    21. 子数组中的最大值
    22. 子数组中的最小值
  3. 需要对滑入窗口的数据记录,滑出的数据删除,并且使这些记录方便的算出最大值和最小值
    31. 使用 map / multiset 可以在滑入滑出的时候方便的增减对应数据
    32. 同时 map / multiset 本身是有序的,可以方便的找出最大值最小值

答题

    int longestSubarray(vector<int>& nums, int limit) {
        map<int, int> m;
        int ans = 0;
        int i = 0;
        for (int j = 0; j < nums.size(); j++) {
            m[nums[j]]++;

            if (m.rbegin()->first - m.begin()->first <= limit) {
                ans = max(ans, j - i + 1);
                continue;
            }

            m[nums[i]]--;
            if (m[nums[i]] == 0) {
                m.erase(nums[i]);
            }
            i++;
        }
        return ans;
    }
    int longestSubarray(vector<int>& nums, int limit) {
        multiset<int> s;
        int ans = 0;
        int i = 0;
        for (int j = 0; j < nums.size(); j++) {
            s.insert(nums[j]);

            if (*s.rbegin() - *s.begin() <= limit) {
                ans = max(ans, j - i + 1);
                continue;
            }

            s.erase(s.find(nums[i]));
            i++;
        }
        return ans;
    }

有序矩阵中的第 k 个最小数组和

???

  1. 妈妈问我为什么老是做不出来 T4
  2. 二哥:暴力
  3. 我:爆炸
  4. 请大家督促我学习 T4
  5. 抄作业

思路一:@scut_dell 二哥的暴力

  1. 使用 vector<int> ans 记录各个行选一个数相加的和
    11. 记录的方法是,先保存第一行各数
    12. 然后把第二行的各数拿出来,组合相加
    13. 对其排列,超过 k 个就不需要保留了
    14. 相加之后记录回 ans ,下次拿出第三行各数,与其组合相加
  2. 返回第 k 个最小数组和

答题

    int kthSmallest(vector<vector<int>>& mat, int k) {
        vector<int> ans(mat[0]);
        for (int i = 1; i < mat.size(); ++i) {
            multiset<int> st;
            for (int x : ans) {
                for (int y : mat[i]) {
                    st.insert(x + y);
                }
            }
            ans.assign(st.begin(), st.end());
            ans.resize(min(k, (int)ans.size()));
        }
        return ans.back();
    }

思路二:@newbie-19 newbie 哥的 二分

  1. 与 小张刷题计划 一样的思路,先二分找答案,再验证答案
  2. 但是我觉得牛逼的是这个 dfs ,把找答案个数算的明明白白,我的理解就是个 “二维” dfs
  3. 当前 idx 行的数字调整,每调整一个数,都把后续 idx dfs 一遍
  4. 这样就不用记录每行到底现在选择的是哪个数,我一直卡在这里

答题

    int kthSmallest(vector<vector<int>>& mat, int k) {
        int l = 0;
        int r = 0;
        for (int i = 0; i < mat.size(); i++) {
            l += mat[i].front();
            r += mat[i].back();
        }

        int base = l;
        while (l < r) {
            int mid = l + (r - l) / 2;
            int cnt = 1;
            dfs(mat, k, mid, 0, base, cnt);
            if (cnt < k) {
                l = mid + 1;
            }
            else {
                r = mid;
            }
        }
        return r;
    }

    void dfs(vector<vector<int>>& mat, int k, int maxSum, int idx, int sum, int& cnt) {
        if (idx == mat.size()) return;
        if (sum > maxSum || cnt > k) return;

        dfs(mat, k, maxSum, idx + 1, sum, cnt);

        for (int j = 1; j < mat[idx].size(); j++) {
            int temp = sum + mat[idx][j] - mat[idx][0];
            if (temp > maxSum) break;
            cnt++;
            dfs(mat, k, maxSum, idx + 1, temp, cnt);
        }
    }

致谢

感谢您的观看,希望对您有帮助,欢迎热烈的交流!

如果感觉还不错就点个赞吧~

这是 我的leetcode ,帮助我收集整理题目,可以方便的 visual studio 调试,欢迎关注,star

3
展开全部 18 讨论