二、同积元组
给你一个由 不同 正整数组成的数组 nums ，请你返回满足 a * b = c * d 的元组 (a, b, c, d) 的数量。其中 a、b、c 和 d 都是 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
