Re: [閒聊] 每日LeetCode

看板Marginalman作者pandix (麵包屌)時間1年前 (2022/11/02 15:12)推噓7(7推 0噓 1→)

留言8則, 7人參與討論串80/719 (看更多)

433. Minimum Genetic Mutation 龍大體內的基因突變了。給你開始和目標基因以及合法基因，問突變至目標基因要花幾步基因是長度為8 由"ACGT"組成的字串基因突變:改變基因中的一個字元 ex: "AACCGGTT" -> "AACCGGTA" 過程中只能突變至合法基因中有的基因 Example 1: Input: start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"] Output: 1 Example 2: Input: start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"] Output: 2 Example 3: Input: start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"] Output: 3 思路: 1.總之先建 set 存那些合法基因，因為問最短步數所以就用BFS 每輪檢查目前走到的基因中有哪些突變後的結果在合法基因中有就加進下一輪要檢查的基因 2.走到之後可以直接把他移出合法基因代表他已經走過了不用再走了可以省下一般 BFS 中要用的 visited 3. Python code: class Solution: def minMutation(self, start: str, end: str, bank: List[str]) -> int: bankset = set(bank) currstep, nextstep = [start], [] step = 0 while currstep: for gene in currstep: if gene == end: return step for i in range(8): for c in 'ACGT': newgene = gene[:i] + c + gene[i+1:] if newgene in bankset: nextstep.append(newgene) bankset.remove(newgene) currstep, nextstep = nextstep, [] step += 1 return -1 -- 蛤? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.193.176 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1667373177.A.FDC.html

推

ririoshi

11/02 15:14, 1年前 , 1^F

11/02 15:14, 1^F

推

Jaka

11/02 15:15, 1年前 , 2^F

11/02 15:15, 2^F

推

Rushia

11/02 15:15, 1年前 , 3^F

11/02 15:15, 3^F