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

T1:旅行终点站

很简单,只要判断是否存在paths[j][0]和paths[i][1]相同就行了,如果存在,则说明path[i][1]不是终点站。因为答案是唯一的,所以如果不存在相同的话直接输出就行了。

class Solution {
    public String destCity(List<List<String>> paths) {
        int length=paths.size();
        for(int i=0;i<length;i++){
            boolean isresult=true;
            for(int j=0;j<length;j++){
                if(i==j)continue;
                if(paths.get(i).get(1).equals(paths.get(j).get(0))){
                    isresult=false;
                    break;
                }
            }
            if(isresult)return paths.get(i).get(1);
        }
        return "";
    }
}

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

个人感觉比T1还简单。一遍扫描,记录上一个“1”的位置,然后判断是否相隔k即可。注意计算间隔为下标差-1。

class Solution {
    public boolean kLengthApart(int[] nums, int k) {
        int length=nums.length;
        int latest=-1;
        for(int i=0;i<length;i++){
            if(nums[i]==1){
                if(latest>=0&&i-latest-1<k)
                    return false;
                latest=i;
            }
        }
        return true;
    }
}

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

绝对差=最大值-最小值。由于是连续子数组,因此,如果能动态维护最大值和最小值即可。可以用线段树、堆等方法来进行动态维护。
我这里选用了好写(但其实极端情况下可能和直接遍历复杂度差不多)的方法:新进入的数和最值判断大小并替换,出去的数如果等于最值则需要重新遍历。看来用例里没有这种极端的情况。
盲目遍历应该是不行的,比较保险还是线段树或者rmq。我的这个代码是超出了最值再进行遍历,可能对于某些测试用例也会耗时不少。但一般来讲,出去的数超出最值通常是窗口比较短的情况,而窗口比较长的话则不容易超出最值。其实不建议像我这么写。
(不想绑定手机,所以在这里回复了 @relaxhan )

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        int length=nums.length;
        int left=0,right=0,max=nums[0],min=nums[0];
        int result=right-left;
        right++;
        while(right<length){
            if(nums[right]>max)max=nums[right];
            if(nums[right]<min)min=nums[right];
            if(max-min<=limit){
                if(right-left>result)
                    result=right-left;
            }
            else{
                left++;
                if(nums[left-1]==max){
                    max=nums[left];
                    for(int i=left+1;i<=right;i++)
                        if(nums[i]>max)
                            max=nums[i];
                }
                if(nums[left-1]==min){
                    min=nums[left];
                    for(int i=left+1;i<=right;i++)
                        if(nums[i]<min)
                            min=nums[i];
                }
            }
            right++;
        }
        return result+1;
    }
}

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

本题有一点非常重要:k <= min(200, n ^ m)。也就是说,k最大也就200。因此我们最多只需要列举200种最小情况即可。
因此我们可以想到贪心的方法:取前(i-1)行的前k个最小值,将其与第i行的n个值分别相加,我们会得到k*n个值。然后,我们取最小的k个值进行下一步计算,直到最后一行计算完毕,最终第k个值即为所求结果。
时间复杂度:O(m*k*n*log(k*n))。

class Solution {
    public int kthSmallest(int[][] mat, int k) {
        int m=mat.length;
        int n=mat[0].length;
        int[] arr=new int[n];
        int length=arr.length;
        for(int i=0;i<length;i++)
            arr[i]=mat[0][i];
        for(int i=1;i<m;i++){
            int[]temp=new int[length*n];
            for(int j1=0;j1<length;j1++)
                for(int j2=0;j2<n;j2++)
                    temp[j1*n+j2]=arr[j1]+mat[i][j2];
            Arrays.sort(temp);
            arr=new int[Math.min(k,temp.length)];
            length=arr.length;
            for(int j=0;j<length;j++)
                arr[j]=temp[j];
        }
        return arr[k-1];
    }
}
7

旅行终点站

思路

  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

今天的评测机很快

4

第四题竟然有个200的限制条件,啊这。。。

2

第四题尝试了许久还是不行,唉……还需要多加磨练

1

看来评论区就只有我一个是废物

1

有一说一,建议lc周赛平台提交时只反馈每次提交的结果是正确还是错误+错误类型,不反馈出现错误的测试点以及预期结果,这样一方面能够保证比赛的感觉,同时更好地防止硬编码测试用例等现象的出现!!

1

第三题
枚举子数组的右端点 二分+rmq计算出最远的左端点即可

class Solution {
public:
    static const int maxn=1e5+10;
    int a[maxn];
    int dpmax[maxn][20],dpmin[maxn][20];
void rmq_init (int n) {
    for (int i = 0; i < n; i++) dpmax[i][0] =dpmin[i][0]= a[i];
    for (int j = 1; (1<<j) <= n; j++) {
        for (int i = 0; i+(1<<j)-1 < n; i++) {
            dpmax[i][j] = max (dpmax[i][j-1], dpmax[i+(1<<(j-1))][j-1]);
            dpmin[i][j] = min (dpmin[i][j-1], dpmin[i+(1<<(j-1))][j-1]);
        }
    }
}
    long long sum[maxn];
void init(int n){
    sum[0]=0;
    for (int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i-1];
}
int rmqmax (int l, int r) {
    int k = 0;
    while ((1<<(k+1)) <= r-l+1) k++;
    return max (dpmax[l][k], dpmax[r-(1<<k)+1][k]);
}
int rmqmin (int l, int r) {
    int k = 0;
    while ((1<<(k+1)) <= r-l+1) k++;
    return min (dpmin[l][k], dpmin[r-(1<<k)+1][k]);
}
    int longestSubarray(vector<int>& nums, int limit) {
        for (int i=0;i<nums.size();i++) a[i]=nums[i];
        rmq_init(nums.size());
        init(nums.size());
        long long Max = 0;
        int n=nums.size();
        for (int i=0;i<n;i++){
            int l=0,r=i;
            while (l<r){
                //cout<<l<<" "<<r<<endl;
                int mid = (l+r)>>1;
                //cout<<"mid="<<mid<<endl;
                //cout<<"rmq="<<rmqmax(mid,i)<<" "<<rmqmin(mid,i)<<endl;
                if (rmqmax(mid,i)-rmqmin(mid,i)<=limit){
                    r=mid;
                }
                else{
                    l=mid+1;
                }
            }
           // cout<<"l="<<l<<" r="<<r<<endl;
            l=min(l,r);
           // cout<<"i="<<i<<"l="<<l<<endl;
            Max = max(Max,1LL*i-l+1);
        }
        return Max;
    }
};

第四题
注意到每个矩阵元素不超过5000,则答案不超过200000,且答案具有单调性
因此二分答案,check则是直接dp dp(i,j)表示用了前i行,和为j的方案数

class Solution {
public:
    int n,m;
    int a[50][50];
    int sum[50];
    long long dp[40+2][200000+10];
    int check(int mid,int k){
        for (int i=0;i<=n;i++){
            for (int j=1;j<=mid;j++) dp[i][j]=0;
        }
        dp[0][0]=1;
        for (int i=1;i<=n;i++){
            for (int mask=0;mask<=mid;mask++){
                if (dp[i-1][mask]==0) continue;
                for(int j=1;j<=m;j++){
                    if (mask+a[i][j]>mid) continue;
                    dp[i][mask+a[i][j]]=(dp[i][mask+a[i][j]]+dp[i-1][mask]);
                    if (dp[i][mask+a[i][j]]>k) dp[i][mask+a[i][j]]=k;
                    if (dp[i][mask+a[i][j]]==k){
                        if (sum[n]-sum[i]+mask+a[i][j]<=mid) return true;
                    }
                }
            }
        }
        long long res=0;
        for (int i=1;i<=mid;i++){
            res+=dp[n][i];
            if (res>=k) return true;
        }
        return false;
    }
    int kthSmallest(vector<vector<int>>& mat, int k) {
        n=mat.size();
        m=mat[0].size();
        for (int i=0;i<n;i++){
            for (int j=0;j<m;j++){
                a[i+1][j+1] =mat[i][j]; 
            }
        }
        sum[0]=0;
        for (int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i][1];
        int r;
        for (int i=1;i<=n;i++) r+=a[i][m];
        int l=sum[n];
        while (l<r){
            int mid=(l+r)>>1;
            if (check(mid,k)){
                r=mid;
            }
            else{
                l=mid+1;
            }
        }
        for(int i=min(l,r);i<=max(l,r);i++){
            if (check(i,k)) return i;
        }
        return 0;
    }
};
1

原以为第三题n^2的时间复杂度会超时没敢写,结果发现不会超时。

1

做得有点慢,还是思维不够敏捷,需要多练