→ JIWP: 大師 08/22 13:57
推 oin1104: 大師 08/22 13:58
推 DJYOMIYAHINA: 我有什麼用 08/22 13:58
推 Wardyal: 今天的難得我會寫 08/22 13:59
476. Number Complement
## 思路
如果第i位數是0 就加2^i進res, 如果是1就減掉該位數, 直到num為0
## Code
```python
class Solution:
def findComplement(self, num: int) -> int:
res = 0
i = 1
while num:
if num & i == 0:
res += i
else:
num -= i
i <<= 1
return res
```
---
320. Generalized Abbreviation
列出所有縮寫組合, 但數字不能相連(ex. 11c)
ex. abc = ["3","a2","1b1","ab1","2c","a1c","1bc","abc"]
## 思路
Backtracking - O(2^N)
懶得寫
Bit manipulation
Time:O(N * 2^N), Space: O(1)
word有N個字元, 所以組合會是2^N
每個組合i檢查j-bit: 0-縮成數字, 1-字元
假如字串是abcde, i是00011 -> 3de
## Code
```python
class Solution:
def generateAbbreviations(self, word: str) -> List[str]:
ans = []
n = len(word)
for i in range(1 << n):
arr = []
count = 0
for j in range(n):
if i & (1 << j):
if count:
arr.append(str(count))
count = 0
arr.append(word[j])
else:
count += 1
if count:
arr.append(str(count))
ans.append(''.join(arr))
return ans
```
--
http://i.imgur.com/OLvBn3b.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.196 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1724306244.A.787.html