題目連結: 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)