本文是力扣第128场双周赛的题解分享。
考察知识点
数据结构：数组、哈希表
解题思路
维护一个哈希表，用来储存每个num和它的排序（注意并列的情况）
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
nums2 = sorted(nums) // 对nums排序
mapping = {} // mapping储存num和其序号的键值对
for i, num in enumerate(nums2): // 遍历排序后的数组
if i > 0 and nums2[i] == nums2[i-1]:// 如果某一位跟前一位的值相等，那么它的序号跟前一位一样（并列）
mapping[nums2[i]] = mapping[nums2[i-1]]
else: // 如果某一位跟前一位的值不等，那么以index为序号
mapping[nums2[i]] = i
res = []
for num in nums:
res.append(mapping[num]) // res用来储存返回值
return res
|
考察知识点
数据结构：数组、字符串
算法：排序
其它：字典序
解题思路
其实就是对votes[0]里的每一个字母进行排序，关键是排序的依据是什么？Python有现成的sort函数，那么参数key是什么呢？
1. 比较字母A比字母B在所有str的第1位，哪个出现次数多
2. 如果字母A和字母B在所有str的前k位出现次数都一样多，那么比较第k+1位，哪个出现次数多
3. 如果都一样多，就以字典序排序
所以怎么利用以上的规则，把key表示出来呢？
这里采取了把出现字数压缩成chr值的办法，然后依据字典序的方法来排序
1. 如果字母A在所有str的第1位出现5次，B出现4次，那么我们把A标记为chr(1000-5)，B标记为chr(1000-4)。因为chr(1000-5) < chr(1000-4)，所以A排在B的前面
2. 如果字母A和B在前k位都是一样的，那么前面k个chr值都一样。如果第k+1位，A比B多，那么依照上面的法则，A排在B的前面。
3. 如果都一样，我们就在chr值后面加上字母本身，因为A<B，所以A排在B的前面
代码
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def rankTeams(self, votes: List[str]) -> str:
mapping = {} // mapping储存key值
for word in votes:
for i, letter in enumerate(word):
if letter not in mapping:
mapping[letter] = [1000] * len(word) // 初始化key值
mapping[letter][i] -= 1 // 如果A在第i位多出现一次，就在第i位的chr值-=1，提高其比较的优先级
for letter in mapping:
mapping[letter] = ''.join((chr(x) for x in mapping[letter])) + letter // 为了利用字典序，须转换为字符串
return ''.join(sorted(votes[0], key=lambda x: mapping[x])) // 进行排序
|
考察知识点
数据结构：二叉树、链表
算法：深度优先搜索
解题思路
1. 外层递归解决链表的头和tree的某个node匹配的问题，匹配成功后进入内层递归
2. 内层递归解决链表的每个node和tree的每层node匹配的问题
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
// 外层递归
def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
if root:
if head.val == root.val:
if self.f(head, root):
return True
return self.isSubPath(head, root.left) or self.isSubPath(head, root.right)
return False
// 内层递归
def f(self, node, root):
if not node.next:
return True
if root.left and root.left.val == node.next.val and self.f(node.next, root.left):
return True
if root.right and root.right.val == node.next.val and self.f(node.next, root.right):
return True
return False
|
考察知识点
数据结构：二维数组
算法：广度优先搜索
其他：辅助变量
解题思路
1. 因为需要计算改变数，因此想到BFS
2. queue储存所有当前这步可以search到的地方
3. visited储存所有历史上search过的地方
4. new_queue储存当前的基础上，改变一个箭头，可以search到的地方
5. 用new_queue代替queue，同时用count记数，进行BFS
6. 当search到右下角，返回count
代码
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:
def minCost(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
count = 0
queue = [(0, 0)]
visited = {(0, 0)}
while True:
for i, j in queue:
if grid[i][j] == 1:
if j+1 < n and (i,j+1) not in visited:
queue.append((i,j+1))
visited.add((i,j+1))
elif grid[i][j] == 2:
if j-1 >=0 and (i,j-1) not in visited:
queue.append((i,j-1))
visited.add((i,j-1))
elif grid[i][j] == 3:
if i+1 < m and (i+1,j) not in visited:
queue.append((i+1,j))
visited.add((i+1,j))
else:
if i-1 >=0 and (i-1,j) not in visited:
queue.append((i-1,j))
visited.add((i-1,j))
if (m-1, n-1) in visited:
return count
count += 1
new_queue = []
for i,j in queue:
for p, q in zip((i-1,i+1,i,i),(j,j,j-1,j+1)):
if (p, q) not in visited and 0<=p<m and 0<=q<n:
new_queue.append((p,q))
visited.add((p,q))
queue = new_queue
|
