周赛笔记224


二、同积元组

给你一个由 不同 正整数组成的数组 nums ,请你返回满足 a * b = c * d 的元组 (a, b, c, d) 的数量。其中 abcd 都是 nums 中的元素,且 a != b != c != d

class Solution:
    def tupleSameProduct(self, nums: List[int]) -> int:
        dic=collections.defaultdict(list)
        n=len(nums)
        for i in range(n):
            for j in range(i+1,n):
                dic[nums[i]*nums[j]].append(1)
        #print(dic)
        ans=0
        for i in dic.values():
            n=len(i)
            if n:
                ans+=comb(n,2)*8
        return ans

三、重新排列后的最大子矩阵

给你一个二进制矩阵 matrix ,它的大小为 m x n ,你可以将 matrix 中的 列 按任意顺序重新排列。

请你返回最优方案下将 matrix 重新排列后,全是 1 的子矩阵面积。

class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        m,n=len(matrix),len(matrix[0])
        pre=[[0]*n for _ in range(m+1)]   #记住每个位置往下可以连多少个
        for i in range(m-1,-1,-1):
            for j in range(n):
                if matrix[i][j]:
                    pre[i][j]=1+pre[i+1][j]
                else: pre[i][j]=0
        #print(pre)

        ans=0
        for i in range(m):
            pre[i].sort(reverse=True)
            for j in range(n):
                ans=max(ans,(j+1)*pre[i][j])  #枚举更新
        return ans

#二维暂存数组

再提一下另一道题:
84.柱状图中最大的矩形

#仿本题做法:
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        tmp=[]
        max_height=max(heights)
        for height in heights:
            cur=[i+1 for i in range(height)]+[0]*(max_height-height)
            tmp.append(cur)

        ans=0
        for ceil in zip(*tmp):
            num,cnt=0,0
            for i in range(len(ceil)):
                if ceil[i]: 
                    num=ceil[i]
                    cnt+=1
                else: cnt=0
                ans=max(ans,num*cnt)

        return ans

#超时,太惨了,
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights.append(0)
        stack = [-1]
        ans = 0 
        for i in range(len(heights)):
            while heights[i] < heights[stack[-1]]:
                h = heights[stack.pop()]
                w = i - stack[-1] - 1
                ans = max(h*w, ans)

            stack.append(i)
        return ans 

四、猫和老鼠 II

https://leetcode-cn.com/problems/cat-and-mouse-ii/

class Solution:
    def canMouseWin(self, grid: List[str], catJump: int, mouseJump: int) -> bool:
        m, n  = len(grid), len(grid[0])
        grid  = [list(t) for t in grid]
        isin  = lambda i, j : 0<=i<m and 0<=j<n
        get_h = lambda i, j : i * n + j
        for i in range(m) :
            for j in range(n) :
                if grid[i][j] == 'C' :
                    cat_pos = (i, j)
                    grid[i][j] = '.'
                elif grid[i][j] == 'M' :
                    mouse_pos = (i, j)
                    grid[i][j] = '.'
                elif grid[i][j] == 'F' :
                    food_pos = (i, j)
                    grid[i][j] = '.'

        def visit(start, end, dist) :
            to_visit = [[0, start]]
            visited = {get_h(*start):0}
            while len(to_visit) > 0 :
                ct, (ni, nj) = to_visit.pop(0)
                dirctions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
                for dt in dirctions :
                    for step in range(1, dist+1) :
                        xi, xj = ni+dt[0]*step, nj+dt[1]*step
                        if not isin(xi, xj) :
                            break
                        if grid[xi][xj] == '#' :
                            break
                        if get_h(xi, xj) in visited :
                            continue
                        visited[get_h(xi, xj)] = ct+1
                        to_visit.append([ct+1, [xi, xj]])
            end_hash = get_h(*end)
            return -1 if not end_hash in visited else visited[end_hash]
        dis_cat   = visit(cat_pos, food_pos, catJump)
        dis_mouse = visit(mouse_pos, food_pos, mouseJump)
        if dis_mouse == -1 :
            return False
        if dis_mouse > 1000 :
            return False
        print(dis_cat)

        @functools.lru_cache(None)
        def solve(cpos=cat_pos, mpos=mouse_pos, action='m', nt=1) :
            assert action in ['m', 'c']
            if mpos == food_pos :
                return True
            if cpos == food_pos :
                return False
            if mpos == cpos :
                return False
            if nt > max(dis_cat*2, 30) :
                return False

            if action == 'm' :
                ni, nj = mpos
                dirctions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
                to_use = []
                for dt in dirctions :
                    for step in range(0, mouseJump+1) :
                        xi, xj = ni+dt[0]*step, nj+dt[1]*step
                        if not isin(xi, xj) :
                            break
                        if grid[xi][xj] == '#' :
                            break
                        to_use.append(solve(cpos=cpos, mpos=(xi, xj), action='c', nt=nt+1))
                if any(to_use) :
                    return True
                return False
            if action == 'c' :
                ni, nj = cpos
                dirctions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
                to_use = []
                for dt in dirctions :
                    for step in range(0, catJump+1) :
                        xi, xj = ni+dt[0]*step, nj+dt[1]*step
                        if not isin(xi, xj) :
                            break
                        if grid[xi][xj] == '#' :
                            break
                        to_use.append(solve(cpos=(xi, xj), mpos=mpos, action='m', nt=nt+1))
                if not all(to_use) :
                    return False
                return True
        solve.cache_clear()
        return solve()

#copy

文章作者: ╯晓~
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ╯晓~ !
评论
  目录