楼主:
dont 2024-09-01 14:42:49这次是参加vitual
Q1
检查两值的奇偶
Q2
k-size MaxHeap
Q3
因为测资只有1~100, row/col长度最多也才10
所以我是建val dict, 里面存row的index
然后递回加1~100 用bitmask判断row有没重复过
加上cache虽然有过 但还是跑了8000+ ms lol
```python
class Solution:
def maxScore(self, grid: List[List[int]]) -> int:
len_r, len_c = len(grid), len(grid[0])
table = defaultdict(list) # val: list[row idx]
for r in range(len_r):
for c in range(len_c):
table[grid[r][c]].append(r)
@cache
def recur(i, mask):
if i == 101:
return 0
if mask == (1 << len_r) - 1:
return 0
res = recur(i+1, mask) # skip
for j in range(i, 101):
for r in table[j]:
if mask & (1 << r):
continue
res = max(res, j + recur(j+1, mask | 1 << r))
return res
return recur(0, 0)
```
Q4
我不会