讨论/题目交流/🏆 第 178 场力扣周赛/
🏆 第 178 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 有多少小于当前数字的数字
4 分 - 通过投票对团队排名
5 分 - 二叉树中的列表
7 分 - 使网格图至少有一条有效路径的最小代价

展开讨论

大家好,我的博客是: http://erik-chen.github.io/,欢迎交流!

第一题. 有多少小于当前数字的数字

思路

维护一个字典,用来储存每个num和它的排序(注意并列的情况)

代码

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. 如果字母AB在前k位都是一样的,那么前面k个chr值都一样。如果第k+1位,AB多,那么依照上面的法则,A排在B的前面。
  3. 如果都一样,我们就在chr值后面加上字母本身,因为A<B,所以A排在B的前面

代码

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匹配的问题

代码

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

代码

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
1
展开全部 21 讨论