[leetcode]問題解答と解説。338. Counting Bits [JavaScript]
皆さんleetCode好きですよね。私も好きです。
なかなかやる機会がないのですよね。
leetCodeの使い方や解説ではなく実際に問題を解決するために何をしたか
をメモ書きして行きます
私はある決意をして今挑んでいます。
モチベーションを保つためだけにこれをやっています。
では今日のleetCode。
【338. Counting Bits】の解決策と方法。自分がまず挑戦して
やったことをさらけ出します。
※下にある自分のコードは自分で設けた制限時間内に書けたところまです。
これは
「私は年末までこれを続けたらどんなleetCoderになるか」のシリーズ。
実験的ブログ更新です。
[leetcode] 338. Counting Bits ルール
Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.
nが渡されたときに二進数にしたときの1が何個あるか配列のインデックスに表現して返せというもの
Example 1:
Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10 // 1が1つある
Example 2:
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10 // 1が1つあるから1
3 --> 11 // 1が2つあるから2
4 --> 100 // 1が1つあるから1
5 --> 101 // 1が2つあるから2
exampleは実際の問題ページを見てください
[leetcode] 338. Counting Bits 問題ページ
[leetcode] 338. Counting Bits
my code is not completed
問題文が何を入っているかわからなかった。
お手上げです
そして解決させる為に調べたら色々知らない概念に出会えた
We can use Brian Kernighan’s algorithm to improve the above naive algorithm’s performance. The idea is to only consider the set bits of an integer by turning off its rightmost set bit (after counting it), so the next iteration of the loop considers the next rightmost bit.
The expression n & (n-1) can be used to turn off the rightmost set bit of a number n. This works as the expression n-1 flips all the bits after the rightmost set bit of n, including the rightmost set bit itself. Therefore, n & (n-1) results in the last bit flipped of n.
For example, consider number 52, which is 00110100 in binary, and has a total 3 bits set.
問題文が何を入っているのかわかった記事
https://www.geeksforgeeks.org/count-set-bits-in-an-integer/
https://www.youtube.com/watch?v=dwjjhbwNJxM
ここで紹介している 「Kernighan’s algorithm」は二進数でbitsが何かを返すものだという
https://www.youtube.com/watch?v=uAcxY2w-oGI
この動画がむちゃくちゃわかりやすかった
そのnのbits数は
偶数の時は同じ
奇数の時はその一個前の数プラス1
で表現できるという
これがまさに答えで示すことになった
[leetcode] 338. Counting Bits。discussの中の一つの解答例
数ある中からJavaScriptのもので、理解しやすい解説をピックアップしました。
discussから見ればさらにもっと違う方法で真似したくなるものがあるかもしれない
JavaScriptでfilterされている、discussはこちらから
var countBits = function(n) {
let map = []
map[0] = 0
for(let i = 1; i <= n; i++){
if((i % 2) == 0){
map[i] = map[i/2]
} else {
// i is odd
map[i] = (map[i-1] + 1)
}
}
return map
};/**
* @param {number} n
* @return {number[]}
*/
var countBits = function (n) {
let result = [0]
for (let i = 1; i <= n; i++) {
result[i] = result[i & (i - 1)] + 1
}
return result
};Explain:
The most important formula:
OnesCount(n) = OnesCount( n & ( n - 1 ) ) + 1How to get this formula ?
Assume we have a binary: n = 1101, then n - 1 = 1100, the result of n & ( n - 1 ) = 1100.
So we can conclude that: count in n & ( n - 1 ) is one less then n, that's why we should plus 1 in the formula.説明：
最も重要な公式：
OnesCount(n) = OnesCount( n & ( n - 1 ) ) + 1この式を取得するには？
バイナリがあると仮定します: n = 1101、n - 1 = 1100、n & ( n - 1 ) = 1100 の結果。
したがって、次のように結論付けることができます: count in n & ( n - 1 ) は n よりも 1 少ないため、式に 1 を足す必要があります。
[leetcode] 338. Counting Bits をやってみて感想
- 悔しい