どーも！
たかぽんです！
今回はReverse Bitsに挑戦します！
執筆中に次の日になってしまいましたが...
まぁいいでしょう！
Reverse Bits
今回の問題はReverse Bitsです。
簡単に問題の解説をすると、入力として01のデータが入力されます。
それをそのまま反転し、さらに数値に変換したものを出力する...といった形です。
入力は32桁の二進数になっています。
Input: n = 00000010100101000001111010011100
Output: 964176192 (00111001011110000010100101000000)
Explanation:
The input binary string 00000010100101000001111010011100
represents the unsigned integer 43261596,
so return 964176192 which its binary representation is
00111001011110000010100101000000.考え方はほとんどExplanationに書かれている通りですね...!
inputのバイナリ文字列を反転させ、それをintegerに変えた964176192が正解...といった具合です。
アルゴリズム
さて、それでは次にアルゴリズムを検討します。
これに関しては方法は先程書いた通りですが、お見せした方が早そうなので、過程を載せておきます。
class Solution:
def reverseBits(self, n):
print(n)
print(bin(n));
print(bin(n)[2:]);
print(bin(n)[2:].zfill(32));
print(bin(n)[2:][::-1]);
print(bin(n)[2:].zfill(32)[::-1]);
print(int(bin(n)[2:].zfill(32)[::-1], 2));
# 以下出力
43261596
## 本来のinput
00000010100101000001111010011100
0b10100101000001111010011100
10100101000001111010011100
00000010100101000001111010011100
00111001011110000010100101
00111001011110000010100101000000
964176192まず、筆者が考えたのは以下でした。
単純に、nを出力すると、"43261596"というように、integerに変換されてしまったので、bin()でバイナリへ。
そして、binメソッドでは"0b10100101000001111010011100"といったように前方二文字は"0b"になります。
これは、二進数であることを示す記号的な役割をはたしているプレフィックスと呼ばれるものですね。
それに関しては反転してしまうと後ろに"b0"となってしまうため、スライスで前二桁を除外します。([2:])
そして、これによって"10100101000001111010011100"が得られます。
それを反転し、int化すればいいのでは・・・？と言うわけですね。
コードは以下です。
int(bin(n)[2:][::-1])ところが、これだと正しい正解は出ませんでした...orz...
そして先程の最初のように分解して出力するようにしたら...
## 本来のinput nのバイナリ
00000010100101000001111010011100
## bin(n)
0b10100101000001111010011100本来のinputのバイナリをbin(n)で表現する際に、左側の0が全て省略されていました...
(0bは除外すると、0が6個消えているのがわかるかと思います)
それによって、それを反転しても正しい値が得られなかったわけですね。
そのため、スライスで前二桁を削った後に、32桁になるように左側を0で埋めてあげる必要があります。
それに便利なメソッドがzfill(32)です。
Zeroで32桁までFillする。といった感じですね！
それによって、以下のように、左側をしっかりと0で埋め、反転、integerにキャスト...で完成です。
print(bin(n)[2:]);
print(bin(n)[2:].zfill(32));
10100101000001111010011100
00000010100101000001111010011100提出したコード
あまり効率はよくなさそうですね...
Runtime: 40 ms, faster than 16.25% of Python3 online submissions for Reverse Bits.
Memory Usage: 14.4 MB, less than 7.89% of Python3 online submissions for Reverse Bits.class Solution:
def reverseBits(self, n):
return int(bin(n)[2:].zfill(32)[::-1], 2);