讨论/题目交流/🏆 第 187 场力扣周赛/
🏆 第 187 场力扣周赛
展开讨论

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
展开全部 18 讨论