推 Smallsh: 大師 08/31 10:54
推 sustainer123: 大師 08/31 10:54
推 argorok: 大師 08/31 10:55
推 DJYOMIYAHINA: 大師 08/31 11:20
每日重複了 來寫個每週
666. Path Sum IV
## 思路
1
2 3
4 5 6 7
每個點的 idx = 2^(depth-1) + (pos-1)
* 父節點 = idx // 2
* 左子節點 = 2*idx
* 右子節點 = 2*idx + 1
先把數字轉成idx跟val存到dict
再找leaves並加總path sum
## Code
```python
class Solution:
def pathSum(self, nums: List[int]) -> int:
mapping = {}
for num in nums:
depth, pos, digit = num // 100, (num % 100) // 10, num % 10
idx = 2 ** (depth-1) + pos-1
mapping[idx] = digit
res = 0
for i in mapping:
if (2*i) in mapping or (2*i+1) in mapping:
continue
while i:
res += mapping[i]
i >>= 1
return res
```
--
http://i.imgur.com/OLvBn3b.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1725072799.A.105.html
※ 編輯: dont (185.213.82.86 臺灣), 08/31/2024 10:54:10