Re: [閒聊] LeetCode Weekly Contest 413
補一下3
先將出現過的數字大到小排(去除重複)
以這個sorted_values為基礎，從大的開始選，這樣就可以很輕鬆地排除重複問題
(這邊沒想到好虧)
然後就根據選的value，來看哪些row有出現這個value，就遍歷這些row (取or不取)
下一層就傳第二大的value繼續做一樣的事情，就一般的dfs
要記下跑過哪些row，那些row就不跑了
以row為節點的traversal，就頂多2^10組，比直接brute force好很多
等等再來看4，比賽的時候連4的題目都沒看==
def maxScore(self, grid: List[List[int]]) -> int:
m,n = len(grid), len(grid[0])
mp = defaultdict(set)
value_set = set()
for row_idx, r in enumerate(grid):
for n in r:
value_set.add(n)
mp[n].add(row_idx)
value_sorted = sorted(list(value_set))[::-1]
ans = 0
def dfs(cur_idx, cur_sum, select_rows):
nonlocal ans
if len(select_rows) == m or cur_idx>=len(value_sorted):
ans = max(ans, cur_sum)
return
if_searched = False
# print(cur_idx, len(select_rows), select_rows)
for r_idx in mp[value_sorted[cur_idx]]:
if r_idx not in select_rows:
select_rows.add(r_idx)
dfs(cur_idx+1, cur_sum+value_sorted[cur_idx], select_rows)
select_rows.remove(r_idx)
if_searched = True
if if_searched == False:
dfs(cur_idx+1, cur_sum, select_rows)
dfs(0,0,set())
return ans
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.228.146.144 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1725171089.A.A93.html
※ 編輯: DJYOMIYAHINA (125.228.146.144 臺灣), 09/01/2024 14:13:11
→
09/01 14:13,
1年前
, 1F
09/01 14:13, 1F
→
09/01 14:13,
1年前
, 2F
09/01 14:13, 2F
推
09/01 14:13,
1年前
, 3F
09/01 14:13, 3F
討論串 (同標題文章)
完整討論串 (本文為第 6 之 7 篇)：
