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

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

image.png

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

第一题
第一眼还以为要排序去重,第二眼发现数据量小,直接暴力

class Solution(object):
    def smallerNumbersThanCurrent(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        ans = []
        
        for v in nums:
            cnt = 0
            for t in nums:
                if t<v:
                    cnt += 1
            ans.append(cnt)
        
        return ans

第二题
就是自定义cmp函数,统计每个字母每种名次的数量,从高到低依次比较,如果都相同,再比较字典序
python不会写sort的自定义cmp,所以就手写插入排序了

class Solution(object):
    def rankTeams(self, votes):
        """
        :type votes: List[str]
        :rtype: str
        """
        Dict = dict() # rank可能更加合适,记录各个rank的数量
        n = len(votes[0])
        
        for v in votes[0]:
            Dict[v] = [0] * n # 初始化cnt
        
        for v in votes:
            for i in range(n):
                Dict[v[i]][i] += 1 # 统计各个名次的数量
        
        Ans = ""
        
        # 插入排序,每次选当前rank最高的,v记录rank最高的,选完后加入Ans,然后把Dict里该元素去掉
        for i in range(n):
            v = 0
            for j in range(n):
                if self.compare(votes[0][v], votes[0][j], Dict):
                    v = j
            Dict[votes[0][v]] = [0] * n
            Ans = Ans + votes[0][v]
            
        return Ans
    # 自定义cmp函数,先比较rank,都一样则比较字典序
    def compare(self, a, b, Dict):
        n = len(Dict[a])
        for i in range(n):
            if Dict[a][i] < Dict[b][i]:
                return True
            if Dict[a][i] > Dict[b][i]:
                return False
        return a > b

第三题:
类似于字符串匹配题,昨天刚做的leetcode 139,140,如果139和140会做这道题应该就很简单了,区别在于这道题可以从任意位置开始匹配,所以先把树的所有结点取出来,但由于只需要向下匹配一次,所以相比较而言又更加容易一点。

class Solution(object):
    def isSubPath(self, head, root):
        """
        :type head: ListNode
        :type root: TreeNode
        :rtype: bool
        """
        
        tree = [root]
        x = 0
        
        # 取出所有树节点
        while x < len(tree):
            if tree[x].left != None:
                tree.append(tree[x].left)
            if tree[x].right != None:
                tree.append(tree[x].right)    
            x += 1
        
        # 等价于从所有树节点开始匹配,每次失配的丢掉,匹配的留下,如果没有可以匹配的,则返回false,否则循环结束返回true
        while head != None:
            new_tree = []
            for v in tree:
                if v != None and v.val == head.val:
                    new_tree.append(v.left)
                    new_tree.append(v.right)
            if len(new_tree) == 0:
                return False
            tree = new_tree
            head = head.next
            
        return True

第四题
题目写得很唬人,“有效路径”其实本质还是最短路,可以把箭头对应的路径当作“捷径”,类似于游戏中的“传送门”,如果按箭头走,则时间为0,反之,不按箭头走时间为1(修改箭头),为了简化代码,按箭头走也可以加一条时间为1的路径(可以不选择“传送门”),这样就不需要特判了,把图构造好然后就是spfa了。

class Solution(object):
    def minCost(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        n = len(grid)
        m = len(grid[0])
        
        # 边
        edge = dict()
        
        for i in range(n*m):
            edge[i] = []
        
        # 四个方向
        direct = [[0,1], [0,-1], [1,0], [-1,0]]
        
        for i in range(n):
            for j in range(m):
                p = i*m+j
                d = direct[grid[i][j]-1]
                ni = i+d[0]
                nj = j+d[1]
                # 箭头边,边权为0
                if ni >= 0 and ni < n and nj >= 0 and nj < m:
                    q = ni*m+nj
                    edge[p].append([q, 0])
                # 非箭头边,边权为1,为了简便,箭头方向也加了一条,反正最短路会选箭头边,所以不影响
                for k in range(4):
                    d = direct[k]
                    ni = i+d[0]
                    nj = j+d[1]
                
                    if ni >= 0 and ni < n and nj >= 0 and nj < m:
                        q = ni*m+nj
                        edge[p].append([q, 1])
        
        # spfa模板
        dist = [n*m] * (n*m)
        dist[0] = 0
        vis = [0] * (n*m)
        q = [0]
        while len(q) > 0:
            x = q[0]
            q = q[1:]
            vis[x] = 0
            for y, d in edge[x]:
                if dist[x]+d < dist[y]:
                    dist[y] = dist[x]+d
                    if vis[y] == 0:
                        vis[y] = 1
                        q.append(y)
        
        return dist[n*m-1]

中间第二题提交的时候断网了几分钟,不然还能再进一名,气

21
展开全部 21 讨论