LeetCode.187场周赛

5400. 旅行终点站

用map标记一下即可。

class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        map<string,string> h;
        map<string,bool> p;
        
        int n = paths.size();
        
        for(int i = 0; i<n; i++){
            p[paths[i][0]] = false;
            p[paths[i][1]] = false;
        }
        for(int i = 0; i<n; i++){
            p[paths[i][0]] = true;
            
        }
        string ans;
        for(auto x:p){
            if(x.second == false) ans = x.first;
        }
        return ans;
    }
};

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

遍历一遍。

class Solution {
public:
    bool kLengthApart(vector<int>& nums, int k) {
        int n = nums.size();
        if(!k) return true;
        
        bool ans = true;
        int t = -1;
        for(int i = 0; i<n; i++){
            if(nums[i] == 1){
                if(t == -1){
                    t = i;
                }else{
                    if(i-t-1<k){
                        ans = false;
                        break;
                    }else{
                        t = i;
                    }
                }
            }
        }
        return ans;
    }
};

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

双指针，首先，让R指针一直往右走，且区间[L,R]满足题目条件，直到遇到某一数使条件无法满足，舍弃右指针R，让左指针L向右移动，令R=L，从L重新开始更新区间。(数据好像不是很强)

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        int n = nums.size();
        int l = 0,r = 0,ans = 0, len = 0;
        int Min = 2e9, Max = -2e9;
        for(; r < n ;){
            int num = nums[r];
            Max = max(Max,num);
            Min = min(Min,num);

            if(abs(Max - Min) <= limit){
                len ++;
                r++;
                ans = max(ans,len);
            }else{
                l++;
                r = l;
                Min = 2e9,Max = -2e9;
                len = 0;
            }
        }
        return ans;
    }
};

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

(看了二分的题解后改的)，首先找到最小数组和Left和最大数组和Right，然后二分，每次利用dfs判断数组和小于等于mid的数组有多少个。

const int N = 50;
bool st[N][N];
class Solution {
public:
    vector<int> a;
    int n,m,w;
    //cnt表示当前比mid小的序列的个数，sum表示当前选择的序列元素之和
    void dfs(vector<vector<int>>& t,int step,int& cnt,int sum,int mid){
        if(step == n|| cnt >=w || sum>mid) return ;
        dfs(t,step+1,cnt,sum,mid);
        for(int i = 1; i<m; i++){
            if(sum-t[step][0] + t[step][i] <= mid) {
                cnt ++;
                dfs(t,step+1,cnt,sum-t[step][0] + t[step][i],mid);
            }else
                break;
        }
        return ;
    }
    int kthSmallest(vector<vector<int>>& mat, int k) {
        n = mat.size(), m = mat[0].size();
        w = k;
        int left = 0,right = 0;
        for(int i = 0; i<n; i++){
            left += mat[i][0];
            right += mat[i][m-1];
        }
        int cnt = 1;
        int low = left;
        while(left<right){
            int mid = (left+right)>>1;
            cnt = 1;
            dfs(mat,0,cnt,low,mid);
            if(cnt >= k) right = mid;
            else left = mid+1;
        }
        return left;
    }
};