[leetcode]問題解答と解説。67. Add Binary [JavaScript]

[leetcode]問題解答と解説。67. Add Binary [JavaScript]

皆さんleetCode好きですよね。私も好きです。
なかなかやる機会がないのですよね。
leetCodeの使い方や解説ではなく実際に問題を解決するために何をしたか
をメモ書きして行きます

私はある決意をして今挑んでいます。
モチベーションを保つためだけにこれをやっています。

では今日のleetCode。
【67. Add Binary】の解決策と方法。自分がまず挑戦して
やったことをさらけ出します。

※下にある自分のコードは自分で設けた制限時間内に書けたところまです。

これは
「私は年末までこれを続けたらどんなleetCoderになるか」のシリーズ。
実験的ブログ更新です。

森田賢二のleetCode

森田賢二のleetCode

[leetcode] 67. Add Binary ルール

exampleは実際の問題ページを見てください

[leetcode] 67. Add Binary 問題ページ

338. Counting Bits

[leetcode] 67. Add Binary

my code is not completed

var addBinary = function(a, b) {
    return (BigInt("0b" + a) + BigInt("0b" + b)).toString(2)
};

当初

var addBinary = function(a, b) {
    return (parseInt(a, 2) + parseInt(b, 2)).toString(2)
};

このように書いていたが、これだと大きい数字の二進数のテストでこけるので
BigIntを使う必要があった

ref:
https://stackoverflow.com/a/60522888

[leetcode] 67. Add Binary。discussの中の一つの解答例

数ある中からJavaScriptのもので、理解しやすい解説をピックアップしました。
discussから見ればさらにもっと違う方法で真似したくなるものがあるかもしれない

JavaScriptでfilterされている、discussはこちらから

気に入った解答1

var addBinary = function(a, b) {
    return (BigInt("0b"+a) + BigInt("0b"+b)).toString(2);
}

"0b"をつけるのは文字列は2 進数を表現しているから。'a' と 'b' が 2 進数であることを BigInt() に伝える必要があるためつける
下記解説

BigInt is used to represent Integers greater than 2^53 -1.
(2^53) - 1 is the Maximum Number Primitive which can be safely represented using JavaScript.
This is represented by MAX_SAFE_INTEGER.
We coule use parseInt("number", base) to convert the arguments 'a' and 'b' from binary base to decimal base and then add them together.
But the problem here is, if we have integers, i.e a or b's binary value to be huge (that is if the numbers passed to a or b is really big which is more than 2^52 -1), then javascript can not process it as the max Number primitive it can work with safely is 2^53 -1 or lesser.

Therefore, we make use of BigInt to represent all kind of numbers, small to large Integers.
The BigInt object takes a String Integer literal as argument and then returns us a number which is of theBigInt datatype.

So, here we need to pass the string (which should be an Integer Literal), as whichever base it is currently represented as.
In our case we have 'a' and 'b' as binary numbers(strings).
We need to tell BigInt() that 'a' and 'b' are Binary numbers, so we append '0b' to the beginning of 'a' and 'b' and then pass them to BigInt().
Similarly, if we have Hexadecimal number we prefix '0x' and for Octal numbers we prefix '0o'.

Once we have converted our binary numbers 'a' and 'b' to BigInt datatype, we add them using normal addition (+) operator.

Now, we use the toString method to convert our BigInt number (sum calculated) to String which is a Binary, by passing the base we want to convert our argument to.
str.toString(2) converts the str string to Binary (base 2).

BigInt は、2^53 -1 より大きい整数を表すために使用されます。
(2^53) - 1 は、JavaScript を使用して安全に表現できる最大数プリミティブです。
これは MAX_SAFE_INTEGER で表されます。
parseInt("number", base)を使用して、引数 'a' と 'b' を 2 進数から 10 進数に変換し、それらを加算します。
しかし、ここでの問題は、整数がある場合、つまり a または b のバイナリ値が巨大である場合 (つまり、a または b に渡される数値が 2^52 -1 を超える非常に大きい場合)、javascript は処理できないことです。安全に動作できる最大の Number プリミティブは 2^53 -1 以下です。

したがって、BigInt を使用して、小さい整数から大きい整数まで、あらゆる種類の数値を表します。
BigIntオブジェクトは String Integer リテラルを引数として受け取り、 BigInt データ型の数値を返します。

そのため、ここでは文字列 (整数リテラルである必要があります) を、現在表現されている基数として渡す必要があります。
この場合、'a' と 'b' は 2 進数 (文字列) です。'a' と 'b' が 2 進数であることを BigInt()
に伝える必要があるため、'a' と 'b' の先頭に '0b' を追加してから BigInt() に渡します。 同様に、16 進数の場合はプレフィックス「0x」を付け、8 進数の場合はプレフィックス「0o」を付けます。

2 進数の 'a' と 'b' を BigInt データ型に変換したら、通常の加算 (+) 演算子を使用して加算します。

ここで、toString メソッドを使用して、引数を変換したい基数を渡すことにより、BigInt 数値 (計算された合計) を Binary である String に変換します。
str.toString(2) は、str 文字列を Binary (基数 2) に変換します。

[leetcode] 67. Add Binary をやってみて感想

  • BigInt初めて使った
  • 大きい2進数の数字を扱うには0bつけること

カテゴリー leetCode