LeetcodeWk185

写在前面

太久没有做过周赛题了,偶尔来做一做,感觉真是越来越菜了

第 187 场周赛

题目

A. 旅行终点站

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

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

由于答案确定,所以答案必然是没有出度的点,我们用一个set来存所有有出度的点即可

1
2
3
4
5
6
7
8
9
class Solution {
public:
string destCity(vector<vector<string>>& paths) {
set<string> M;
for(auto lis : paths) M.insert(lis[0]);
for(auto lis : paths) if(!M.count(lis[1])) return lis[1];
return " ";
}
};

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

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

示例 1:

img

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

示例 2:

img

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

示例 3:

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

示例 4:

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

提示:

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

直接判断每个1和前面一个1的距离即可

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public boolean kLengthApart(int[] nums, int k) {
int pre=-1000000;
for(int i=0;i<nums.length;i++){
if(nums[i]==1){
if(i-pre-1 < k) return false;
pre=i;
}
}
return true;
}
}

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

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

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

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入: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:

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

示例 3:

1
2
输入: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

使用双指针即可,我们使用单调队列来维护区间的最大值和最小值,再确定l之后,我们直接往后找最大的r,由于这个l越大,r也越大,所以我们枚举对于每个l的r即可

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
31
32
33
34
class Solution {
public int longestSubarray(int[] nums, int limit) {
int maxl=0;
int maxr=-1;
int minl=0;
int minr=-1;
int []arr=nums;
int n=arr.length;
int [] maxq=new int[n+10];
int [] minq=new int[n+10];
int max=0;
int min=0;
int ans=1;
int l=0;int r=-1;
while(r<n){
while(r<n && arr[maxq[maxl]] - arr[minq[minl]] <=limit){
r++;
if(r==n) break;
int x= arr[r];
while(maxl<=maxr && arr[maxq[maxr]] <= x ) maxr--;
while(minl<=minr && arr[minq[minr]] >= x ) minr--;
maxq[++maxr]=r;
minq[++minr]=r;
}
ans= Math.max(r-l,ans);
while(arr[maxq[maxl]] - arr[minq[minl]] > limit){
l++;
if(maxq[maxl]<l) maxl++;
if(minq[minl]<l) minl++;
}
}
return ans;
}
}

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

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

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

示例 1:

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

示例 2:

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

示例 3:

1
2
3
4
输入: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:

1
2
输入: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非常的小,所以我们直接从最小的值开始枚举即可

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
struct Node {
vector<int> lis;
int v;
friend bool operator < (const Node & a,const Node &b){
return a.v > b.v;
}
Node(vector<int> lis,int v){
this->lis=lis;
this->v=v;
}
};
int kthSmallest(vector<vector<int>>& mat, int k) {
priority_queue<Node> Q;
set<vector<int> > S;
int ans=0;
int n=mat.size();
int m=mat[0].size();
vector<int> arr;
for(int i=0;i<n;i++){
arr.push_back(0);
ans+= mat[i][0];
}
Node beg(arr,ans);
Q.push(beg);
for(int d=0;d<k;d++){
auto cur=Q.top();Q.pop();
if(S.count(cur.lis)) {d--;continue;}
S.insert(cur.lis);
ans= cur.v;
auto lis=cur.lis;
if(d==k-1) break;
for(int i=0;i<n;i++){
if(lis[i]<m-1){
auto l=cur.lis;
auto v = cur.v;
l[i]++;
v = v + mat[i][l[i]] -mat[i][l[i]-1];
Q.push(Node(l,v));
}
}
}
return ans;
}
};

总结

太久没做了,还是有些生疏了,第三题写了好久,然后第四题脑抽了写了更久