#LeetCode:338. Counting Bits

灆洢 2020-05-29 00:31:46

此題要求出 0 到給予的數字全部換算成二進位後,每一個數字中 1 的個數有幾個。

可以利用 DP 動態規劃來求值,也剛好 DP 動態規劃求出來的表即是答案,遞歸方式如下:

  1. 0: 答案為 0。
  2. n: 先將個位數那位是 0 還是 1 先得出來,接著砍掉個位數後(向右移或除 2),剩下的部分一定比目前這個值小。由於本題惠從小到大的求解,故可直接查表後將原本個位數那位的答案加總即是答案。

Kotlin(164ms)

/*******************************************************
 * LeetCode 338. Counting Bits                         *
 * Author: Maplewing [at] knightzone.studio            *
 * Version: 2020/05/29                                 *
 *******************************************************/
class Solution {
    fun countBits(num: Int): IntArray {
        val numberOfBits = IntArray(num + 1, { 0 })
        for (i in 0..num) {
            val currentDigit = i and 1
            val currentBits = currentDigit + numberOfBits[i shr 1]
            numberOfBits[i] = currentBits
        }

        return numberOfBits
    }
}

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料