ハミング距離に関するこのLeetcodeの課題を解決していました。私の構文とコードスタイルに関するフィードバックをお待ちしています。課題の説明は次のとおりです。
2つの整数間のハミング距離は、対応するビットが異なる位置の数です。
2つの整数xとyが与えられた場合、ハミング距離を計算します。
注:0≤x、y < 2 31 。
例:
入力:x = 1、y = 4
出力:2
説明:
1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑
上記の矢印は、対応するビットが
異なる位置を指しています。
ここに ” s私の解決策:
def hammingDistance(x: "int", y: "int") -> "int": bin_x = bin(x)[2:] bin_y = bin(y)[2:] len_x = len(bin_x) len_y = len(bin_y) if len_x != len_y: if len_x > len_y: zeros = "0" * (len_x - len_y) bin_y = zeros + bin_y else: zeros = "0" * (len_y - len_x) bin_x = zeros + bin_x dist = 0 for x,y in zip(bin_x, bin_y): if x!=y: dist += 1 return dist
回答
それは合理的なアプローチですが、早い段階で文字列に変換してから文字列に対してすべてを実行すると、多くの余分なコードが発生します。コード内のこの構成if x!=y
は、基本的に2ビットをXORし、結果がそのXORの1です。
そのXORを整数に対して直接実行すると、問題が発生します。 mplerを使用すると、ゼロを埋める必要があるという問題全体がなくなり(コードサイズはすでに半分になります)、問題は「バイナリでカウントする」になります。それでも同様のループで実行できますが、ショートカットがあります:
return bin(x ^ y).count("1")