leetcode150周赛

写在前面

第一次做leetcode 周赛,体验还是非常好的

因为没有即使起床导致我没有写完题其实是因为我太菜了

第 150 场周赛

题目

A. 拼写单词

给你一份『词汇表』(字符串数组) words 和一张『字母表』(字符串) chars

假如你可以用 chars 中的『字母』(字符)拼写出 words 中的某个『单词』(字符串),那么我们就认为你掌握了这个单词。

注意:每次拼写时,chars 中的每个字母都只能用一次。

返回词汇表 words 中你掌握的所有单词的 长度之和

示例 1:

1
2
3
4
输入:words = ["cat","bt","hat","tree"], chars = "atach"
输出:6
解释:
可以形成字符串 "cat" 和 "hat",所以答案是 3 + 3 = 6。

示例 2:

1
2
3
4
输入:words = ["hello","world","leetcode"], chars = "welldonehoneyr"
输出:10
解释:
可以形成字符串 "hello" 和 "world",所以答案是 5 + 5 = 10。

提示:

  1. 1 <= words.length <= 1000
  2. 1 <= words[i].length, chars.length <= 100
  3. 所有字符串中都仅包含小写英文字母

签到题目,我们先把chars 给保存起来,然后与words中的每一个数组进行比较即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
def countCharacters(self, words: List[str], chars: str) -> int:
ans = 0
dic = dict()
for c in chars :
if not c in dic :
dic[c]=1
else :
dic[c]+=1
for s in words :
cur = dict()
for c in s :
if not c in cur :
cur[c]=1
else :
cur[c]+=1
ok = 1
for c in cur :
if not c in dic or dic[c] < cur[c] :
ok=0
if ok == 1 :
ans+=len(s)
return ans

B.最大层内元素和

给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层,而根节点的子节点位于第 2 层,依此类推。

请你找出层内元素之和 最大 的那几层(可能只有一层)的层号,并返回其中 最小 的那个。

示例:

img

1
2
3
4
5
6
7
输入:[1,7,0,7,-8,null,null]
输出:2
解释:
第 1 层各元素之和为 1,
第 2 层各元素之和为 7 + 0 = 7,
第 3 层各元素之和为 7 + -8 = -1,
所以我们返回第 2 层的层号,它的层内元素之和最大。

提示:

  1. 树中的节点数介于 110^4 之间
  2. -10^5 <= node.val <= 10^5

用一个数组保存每一层的和 ,dfs即可

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
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:

def dfs(self, cur : TreeNode,dep : int,dic :dict) -> None:
if not cur :
return
if not dep in dic :
dic[dep]=cur.val
else :
dic[dep]+=cur.val
self.dfs(cur.left,dep+1,dic)
self.dfs(cur.right,dep+1,dic)
def maxLevelSum(self, root: TreeNode) -> int:
dic=dict()
self.dfs(root,1,dic)
ans =1

for dep in dic :
if dic[ans] < dic[dep] :
ans=dep
return ans

C. 地图分析

你现在手里有一份大小为 N x N 的『地图』(网格) grid,上面的每个『区域』(单元格)都用 01 标记好了。其中 0 代表海洋,1 代表陆地,你知道距离陆地区域最远的海洋区域是是哪一个吗?请返回该海洋区域到离它最近的陆地区域的距离。

我们这里说的距离是『曼哈顿距离』( Manhattan Distance):(x0, y0)(x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1|

如果我们的地图上只有陆地或者海洋,请返回 -1

示例 1:

img

1
2
3
4
输入:[[1,0,1],[0,0,0],[1,0,1]]
输出:2
解释:
海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大,最大距离为 2。

示例 2:

img

1
2
3
4
输入:[[1,0,0],[0,0,0],[0,0,0]]
输出:4
解释:
海洋区域 (2, 2) 和所有陆地区域之间的距离都达到最大,最大距离为 4。

提示:

  1. 1 <= grid.length == grid[0].length <= 100
  2. grid[i][j] 不是 0 就是 1

我们反过来求,如果从一个陆地点出发,如果它的周围是陆地,那这个点其实是没有可以忽略掉的

相反,如果是海洋,那么我们就可以把答案+1,然后继续从这个海洋点继续出发,所能找到的最远的海洋节点就是答案

我们采用bfs,所能bfs的层数便是答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
def maxDistance(self, grid: List[List[int]]) -> int:
res = 0
d =[(1,0),(-1,0),(0,1),(0,-1)]
n = len(grid)
m = len(grid[0])
q = []
for i in range(n) :
for j in range(m) :
if grid[i][j]== 1 :
q.append((i,j,0))

while q :
i,j,res = q.pop(0)

for dx,dy in d:
x = i+ dx
y = j+ dy
if x > -1 and x < n and y >-1 and y < m and grid[x][y]==0 :
grid[x][y]=1
q.append((x,y,res+1))
return res if not res == 0 else -1

D. 按字典序排在最后的子串

给你一个字符串 s,找出它的所有子串并按字典序排列,返回排在最后的那个子串。

示例 1:

1
2
3
输入:"abab"
输出:"bab"
解释:我们可以找出 7 个子串 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。按字典序排在最后的子串是 "bab"。

示例 2:

1
2
输入:"leetcode"
输出:"tcode"

提示:

  1. 1 <= s.length <= 10^5
  2. s 仅含有小写英文字符。

容易发现的是,我们只需要算后缀就可以了,因为对于非后缀的子串,是一定比对应后缀小的

我们跑一遍后缀数组,直接输出答案即可

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
47
48
49
50
51
52
53
54
class Solution {
public:



char s[100000+10];
int t1[100000+10];
int t2[100000+10];
int c[100000+10];
int sa[100000+10];
int n;
void build_sa(int m){
int *x=t1;
int *y=t2;
for(int i=0;i<m;i++) c[i]=0;
for(int i=0;i<n;i++) c[x[i]=s[i]]++;
for(int i=1;i<m;i++) c[i]+=c[i-1];
for(int i=n-1;i>=0;i--) sa[--c[x[i]]]=i;

//
for(int k=1;k<=n;k<<=1){
//
int p=0;
for(int i=n-k;i<n;i++) y[p++]=i;
for(int i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;

for(int i=0;i<m;i++) c[i]=0;
for(int i=0;i<n;i++) c[x[y[i]]]++;
for(int i=1;i<m;i++) c[i]+=c[i-1];
for(int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]= y[i];
//
p=1;
swap(x,y);
x[sa[0]]=0;
for(int i=1;i<n;i++){
x[sa[i]]= y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p-1:p++;
}
if(p>=n) break;
m=p;

}
}
string lastSubstring(string s) {
n=s.size();
for(int i=0;i<n;i++){
this->s[i]=s[i];
}
this->s[n]='\0';
build_sa(256);
string ans="";
int d=sa[n-1];
return s.substr(d,n);
}
};

不知道为什么,有这样的代码可以过同样的写法c++Mle,java TLE.

1
2
3
4
5
6
7
class Solution:
def lastSubstring(self, s: str) -> str:
n= len(s)
ans=""
for i in range(n):
ans=max(ans,s[i:])
return ans

看来python应该是有优化的

总结

这次的比赛其实比较简单主要是题目比较套路

没有全做一方面是时间不够,而来还是题意理解得不是很清楚,C题写了一个奇怪的做法,想到正解的时候却是已经完了

以后尽量每周都打一下吧