On the shoulders of giants.

weekly-contest-187

旅行终点站

给你一份旅游线路图,该线路图中的旅行线路用数组 paths 表示,其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站,即没有任何可以通往其他城市的线路的城市

题目数据保证线路图会形成一条不存在循环的线路,因此只会有一个旅行终点站。

示例 1:

输入:paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
输出:"Sao Paulo" 
解释:从 "London" 出发,最后抵达终点站 "Sao Paulo" 。本次旅行的路线是 "London" -> "New York" -> "Lima" -> "Sao Paulo" 。

示例 2:

输入:paths = [["B","C"],["D","B"],["C","A"]]
输出:"A"
解释:所有可能的线路是:
"D" -> "B" -> "C" -> "A". 
"B" -> "C" -> "A". 
"C" -> "A". 
"A". 
显然,旅行终点站是 "A" 。

示例 3:

输入:paths = [["A","Z"]]
输出:"Z"

提示:

  • 1 <= paths.length <= 100
  • paths[i].length == 2
  • 1 <= cityAi.length, cityBi.length <= 10
  • cityA!= cityBi
  • 所有字符串均由大小写英文字母和空格字符组成。
题解

对应有向图中出度为 0 的节点。

时间复杂度:\(O(n)\)

class Solution {
public:
    string destCity(vector<vector<string>>& paths) {
        map<string, int> out;
        for(auto path : paths) {
            if(out.find(path[1]) == out.end()) out[path[1]] = 0;
            out[path[0]]++;
        }
        string result;
        for(auto name : out) {
            if(name.second == 0) result = name.first;
        }
        return result;
    }
};

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

给你一个由若干 01 组成的数组 nums 以及整数 k。如果所有 1 都至少相隔 k 个元素,则返回 True ;否则,返回 False

示例 1:

输入:nums = [1,0,0,0,1,0,0,1], k = 2
输出:true
解释:每个 1 都至少相隔 2 个元素。

示例 2:

输入:nums = [1,0,0,1,0,1], k = 2
输出:false
解释:第二个 1 和第三个 1 之间只隔了 1 个元素。

示例 3:

输入:nums = [1,1,1,1,1], k = 0
输出:true

示例 4:

输入:nums = [0,1,0,1], k = 1
输出:true

提示:

  • 1 <= nums.length <= 10^5
  • 0 <= k <= nums.length
  • nums[i] 的值为 01
题解

直接遍历模拟即可。

时间复杂度:\(O(n)\)

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

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

给你一个整数数组 nums ,和一个表示限制的整数 limit,请你返回最长连续子数组的长度,该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit

如果不存在满足条件的子数组,则返回 0

示例 1:

输入:nums = [8,2,4,7], limit = 4
输出:2 
解释:所有子数组如下:
[8] 最大绝对差 |8-8| = 0 <= 4.
[8,2] 最大绝对差 |8-2| = 6 > 4. 
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4.
[2,4] 最大绝对差 |2-4| = 2 <= 4.
[2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4. 
因此,满足题意的最长子数组的长度为 2 。

示例 2:

输入:nums = [10,1,2,4,7,2], limit = 5
输出:4 
解释:满足题意的最长子数组是 [2,4,7,2],其最大绝对差 |2-7| = 5 <= 5 。

示例 3:

输入:nums = [4,2,2,2,4,4,2,2], limit = 0
输出:3

提示:

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • 0 <= limit <= 10^9
题解

如果区间 \([x,y]\),是一个合法,那么 \([x+1,y]\) 不会更优(对答案)。

如果区间 \([x,y]\),不是合法的,那么 \([x,y+1]\) 不也是合法。

所以,当区间 \([x,y]\) 合法时,我们让 y 右移。

当区间 \([x,y]\) 不是合法时,我们让 x 右移。

就是 滑动窗口 的基本思想。

时间复杂度:\(O(n)\)

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        int n = nums.size(), result = 1;
        vector<int> q(n);
        map<int, int> total;
        int lef = 0, rig = -1;
        while(rig + 1 < n) {
            total[nums[++rig]]++;
            while(!total.empty()) {
                int Min = total.begin()->first;
                int Max = (--total.end())->first;
                if(limit < Max - Min) {
                    int x = --total[nums[lef++]];
                    if(x == 0) total.erase(nums[lef - 1]);
                } else break;
            }
            result = max(result, rig - lef + 1);
        }
        return result;
    }
};

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

给你一个 m * n 的矩阵 mat,以及一个整数 k ,矩阵中的每一行都以非递减的顺序排列。

你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个 最小 数组和。

示例 1:

输入:mat = [[1,3,11],[2,4,6]], k = 5
输出:7
解释:从每一行中选出一个元素,前 k 个和最小的数组分别是:
[1,2], [1,4], [3,2], [3,4], [1,6]。其中第 5 个的和是 7 。  

示例 2:

输入:mat = [[1,3,11],[2,4,6]], k = 9
输出:17

示例 3:

输入:mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
输出:9
解释:从每一行中选出一个元素,前 k 个和最小的数组分别是:
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]。其中第 7 个的和是 9 。 

示例 4:

输入:mat = [[1,1,10],[2,2,9]], k = 7
输出:12

提示:

  • m == mat.length
  • n == mat.length[i]
  • 1 <= m, n <= 40
  • 1 <= k <= min(200, n ^ m)
  • 1 <= mat[i][j] <= 5000
  • mat[i] 是一个非递减数组
题解

注意到 k 比较小,我们直接用 BFS ,找到第 k 个取出的值。

时间复杂度:\(O(km)\)

class Solution {
public:
    struct Inform {
        vector<int> pos;
        int sum;
        bool operator < (const Inform& tmp) const {
            return sum > tmp.sum;
        }
    };
    int kthSmallest(vector<vector<int>>& mat, int k) {
        int n = mat.size(), m = mat[0].size(), sum = 0, Kth = 0;
        map<vector<int>, bool> vis;
        priority_queue<Inform> q;
        for(auto nums : mat) sum += nums[0];
        q.push((Inform){vector<int> (n, 0), sum});
        while(!q.empty()) {
            if(++Kth == k) break;
            vector<int> u = q.top().pos;
            sum = q.top().sum;
            q.pop();
            for(int i = 0; i < n; i++) {
                if(u[i] + 1 < m) {
                    vector<int> v(u);
                    v[i]++;
                    if(vis[v] == true) continue;
                    int ans = sum - mat[i][v[i] - 1] + mat[i][v[i]];
                    q.push((Inform){v, ans});
                    vis[v] = true;
                }
            }
        }
        return q.top().sum;
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注