第 187 场周赛

Posted on | In , | |
Words count in article: 394 | Reading time ≈ 2

5400. 旅行终点站

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        unordered_map<string, int> mp;
        for(auto p: paths) {
            mp[p[0]]++;
        }
        for(auto p: paths) {
            if(mp[p[1]] == 0) return p[1];
        }
        return "";
    }
};

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool kLengthApart(vector<int>& nums, int k) {
        int c = k;
        for(int i=0; i<nums.size(); i++) {
            if(nums[i] == 0) c++;
            else {
                if(c < k) return false;
                c = 0; 
            }
        }
        return true;
    }
};

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        int maxlen = 0, minnum = INT_MAX, maxnum = INT_MIN, len = 0;
        for(int i=0, j=0; j<nums.size(); ) {
            minnum = min(nums[j], minnum);
            maxnum = max(nums[j], maxnum);
            if(abs(maxnum-minnum) > limit) {
                i++;
                j = i;
                minnum = INT_MAX, maxnum = INT_MIN;
                len = 0;
            } else {
                len++;
                j++;
                maxlen = max(maxlen, len);
            }
        }
        return maxlen;
    }
};

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    vector<vector<int>> temp;
    int m, n;
    int kthSmallest(vector<vector<int>>& mat, int k) {
        temp = mat;
        m = mat.size(), n = mat[0].size();
        int left = 0, right = 0;
        for(int i=0; i<m; i++) left += mat[i][0], right += mat[i].back();
        int init = left;
        while(left <right) {
            int mid = (left + right) >> 1;
            int num = 1;
            dfs(mid, 0, init, num, k);
            if(num >= k) right = mid;
            else left = mid+1;
        }
        return left;
    }
    void dfs(int mid, int index, int sum, int& num, int k) {
        if(sum > mid || index == m || num > k) return;
        dfs(mid, index+1, sum, num, k);
        for(int i=1; i<n; i++) {
            if(sum + temp[index][i]-temp[index][0] <= mid) {
                num ++;
                dfs(mid, index+1, sum+temp[index][i]-temp[index][0], num, k);
            } else break;
        }
    }
};
Donate? comment?