Leetcode_174周赛

Leetcode周赛174
1.方阵中战斗力最弱的 K 行3
2.数组大小减半4
3.分裂二叉树的最大乘积5
4.跳跃游戏 V 6

一小时完成三题。最后一题没看，最后一题解法Po出。
1.方阵中战斗力最弱的 K 行3

class Solution(object):
    def kWeakestRows(self, mat, k):
        """
        :type mat: List[List[int]]
        :type k: int
        :rtype: List[int]
        """
        res=[i for i in range(len(mat))]
        newmat=[[mat[i].count(1),i] for i in range(len(mat))]
        for i in range(len(mat)-1):
            for j in range(i+1,len(mat)):
                if newmat[i][0]>newmat[j][0]:
                    temp=newmat[j]
                    newmat[j]=newmat[i]
                    newmat[i]=temp
                    temp=res[i]
                    res[i]=res[j]
                    res[j]=temp
                if newmat[i][0]==newmat[j][0] and newmat[i][1]>newmat[j][1]:
                    temp=newmat[j]
                    newmat[j]=newmat[i]
                    newmat[i]=temp
                    temp=res[i]
                    res[i]=res[j]
                    res[j]=temp
                #print(res)
        return res[:k]

2.数组大小减半

class Solution(object):
    def minSetSize(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        dic={}
        for i in arr:
            if i not in dic:
                dic[i]=1
            else:
                dic[i]+=1
        newdic=sorted(dic.items(),key=lambda item:item[1],reverse=True)
        #print(newdic)
        num=0
        count=0
        for i in newdic:
            if num<len(arr)//2:
                num+=i[1]
                count+=1
            else:
                return count
        return count

3.分裂二叉树的最大乘积5

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def maxProduct(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def find(root,sumvalue):
            if root:
                sumvalue[0]+=root.val
            if root.left:
                find(root.left,sumvalue)
            if root.right:
                find(root.right,sumvalue)
            #print(sumvalue)
            return sumvalue
        sumvalue=find(root,[0])
        res=[]
        def findvalue(root,res):
            if not root:
                return 0
            left=0
            right=0
            if root.left:
                left=findvalue(root.left,res)
            if root.right:
                right=findvalue(root.right,res)
            res.append(left+right+root.val)
            return left+right+root.val
        findvalue(root,res)
        finalres=[(sumvalue[0]-i)*i for i in res]
        return max(finalres)%(10**9+7)

4.跳跃游戏 V 6
解题思路
可以看成有向图上求最长路径。

把这个数组转换成一个无环有向图。

利用 mp 数组存每个点能直接到达的节点。

dfs 用于递归求一个点的解。一个点的解就是这个点能到的所有点里解最大的一个加一。（如果他哪也到不了，就是 1）

ansx 做了记忆化搜索，防止求重复的点的解。这里可以使用 functools 中的 lru_cache(None) 代替自己定义数组，写法更简洁。

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        l = len(arr)
        mp = [[] for i in range(l)]
        for i in range(l):
            j = i - 1
            while j >= 0:
                if i - j > d: break
                if arr[j] >= arr[i]: break
                mp[i].append(j)
                j -= 1
            j = i + 1
            while j < l:
                if j - i > d: break
                if arr[j] >= arr[i]: break
                mp[i].append(j)
                j += 1
        ansx = [0] * l
        def dfs(i):
            if ansx[i] != 0: return ansx[i]
            if len(mp[i]) == 0:
                ansx[i] = 1
                return 1
            ans = dfs(mp[i][0])
            for toid in mp[i][1:]:
                ans = max(ans, dfs(toid))
            ansx[i] = ans + 1
            return ans + 1
        ans = dfs(0)
        for i in range(1, l):
            ans = max(ans, dfs(i))
        return ans