題目連結: https://leetcode.com/problems/counting-bits/
參考解法: https://leetcode.com/problems/counting-bits/discuss/171380/Swift-solution-(24ms)
法ㄧ: (Brute force)
func countBits(_ n: Int) -> [Int] {
var resultArr: [Int] = []
for i in 0 ..< (n + 1) {
let s = getBinary(i)
let count = getCountOfOne(s)
resultArr.append(count)
}
return resultArr
}
func getCountOfOne(_ s: String) -> Int {
var count = 0
for c in s {
if c == "1" {
count += 1
}
}
return count
}
func getBinary(_ n: Int) -> String {
var tmp = n
var result = ""
while tmp > 0 {
let remainder = tmp % 2
tmp = tmp / 2
result = "\(remainder)" + result
}
return result
}
法二(Dynamic programming)
(p.s. 參考自Ref)
func countBits(_ n: Int) -> [Int] {
if n == 0 { return [0] }
var arr = Array(repeating: 0, count: n+1)
for i in 1 ... n {
if i % 2 != 0 {
arr[i] = arr[i-1] + 1
} else {
arr[i] = arr[i/2]
}
}
return arr
}
Ref: https://leetcode.com/problems/counting-bits/discuss/171380/Swift-solution-(24ms)