Reverse the Digits
0以上の整数 n が与えられます。その10進数の各桁を逆順に並べた数を返してください。先頭にくる0は取り除かれるため、120 は 21 になります。
関数
- ninteger
- 反転する非負整数
- 戻り値integer
- n の各桁を逆順に並べた数
制約
0 ≤ n < 109- 逆順にした数値も符号付き32ビット整数に収まります。
例
- 入力
- n = 1234
- 出力
- 4321
- 説明
1234の各桁は1、2、3、4です。末尾から読むと4、3、2、1となり、これは4321です。
- 入力
- n = 120
- 出力
- 21
- 説明
- 逆から読むと、
120の各桁は0、2、1です。先頭のゼロは数として数えないので、答えは21です。
- 入力
- n = 0
- 出力
- 0
- 説明
0は1桁で、逆にしても再び0になります。
提出時に隠しテスト+13件
発展問題
n が任意の32ビット整数になり得る場合、反転した値は収まらない可能性があります。乗算でオーバーフローする前に、それをどのように検出しますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
数値の最後の桁を取得する算術演算はどれで、最後の桁を取り除く演算はどれですか？
n % 10は最後の桁であり、n / 10（整数除算）はその桁を取り除きます。ある数rの末尾に数字dを付けるには、r * 10 + dを計算します。result = 0から始めます。nが0より大きい間、最後の桁をresultの末尾に移し、その桁をnから取り除きます。0 * 10 + 0は0のままなので、先頭にゼロが現れることはありません。
解説
10進数の文字列を逆順にするのは、ほとんどの言語で1行ででき、最初の回答としては十分です。面接官は通常、文字列を使わずに同じ結果を得る方法を続けて尋ねます。算術を使う方法は、2つの演算に基づいています。n % 10で最後の桁を読み取り、n / 10（整数除算）でその桁を取り除きます。
10進数のテキストを反転する
考え方
数値の各桁は、その10進数表記の文字そのものです。nをテキストに変換し、文字を逆順にしてから、そのテキストを数値として読み戻します。1234は"1234"になり、次に"4321"になり、最後に4321になります。
先頭のゼロは自動的に処理されます。120を逆順にするとテキスト"021"になり、数値として解析すると先頭のゼロは無視され、21が返されます。
10^9未満の数値は最大9桁で、処理量と追加のテキスト量はどちらも桁数に応じて増加するため、計算量はO(log n)です。
アルゴリズム
nを10進数の文字列に変換します。- 文字を逆順にします。
- 逆順にした文字列を整数として解析し、返します。
def reverseDigits(n):
# int() ignores the leading zeros that trailing zeros turn into.
return int(str(n)[::-1])算術演算で数字を取り出したり追加したりする
考え方
nの末尾から数字を1つずつ取り出し、それぞれを新しい数の末尾に追加します。n % 10はnの最後の桁で、整数除算によるn / 10はその桁を取り除きます。dをresultの末尾に追加するには、そこにある数を左に1桁ずらし、1の位にdを置きます。つまり、result * 10 + dです。
1234の場合、resultは4、43、432、4321と変化し、nは123、12、1、0と変化します。nが0になるとループは停止するため、桁数分だけ実行されます。
先頭のゼロは現れません。120の場合、最初に取り出される数字は0で、0 * 10 + 0も0のままなので、跡は残りません。n = 0の場合、ループは実行されず、答えは0です。保持する整数は2つだけなので、追加の領域はO(1)です。
アルゴリズム
result = 0に設定します。nが0より大きい間、最後の桁であるn % 10を計算します。result = result * 10 + digitに設定します。- 整数除算を使って
n = n / 10で桁を取り除きます。 resultを返します。
def reverseDigits(n):
result = 0
while n > 0:
result = result * 10 + n % 10 # push the last digit of n
n //= 10 # drop it from n
return result
落とし穴と境界ケース
ほとんどのバグは、除算とループの終了条件が原因です。
- 整数除算が必要なところで通常の除算を使う。JavaScript、Python 3、Luaでは、
n / 10は123.4になるため、nは再び整数にならず、resultに小数が入ってしまいます。Math.floor、//、または使用する言語の整数除算を使いましょう。 - ループを
while n >= 10と書く。最後の桁を処理する前に停止するため、1234は432として返されます。 - 逆順にしたテキストを数値に変換せずに返す。
"021"は数値の21ではないため、期待される答えとの比較に失敗します。 - Rで
as.characterを使ってdoubleを文字列に変換する。nがdoubleとして格納されている場合、100000000は1e+08と表示され、逆順にしたテキストは80+e1になります。format(n, scientific = FALSE)を使いましょう。
よくある質問4
数値を文字列に変換せずに、その桁を逆順にするにはどうすればよいですか？
数が 0 になるまで、2つの手順を繰り返します。n % 10 で最後の桁を取り出し、result = result * 10 + digit で結果に追加してから、整数除算を使って n = n / 10 でその桁を取り除きます。1234 の場合、結果は 4、43、432、4321 と増えていきます。
数値を反転すると、末尾のゼロはどうなりますか？
それらは先頭のゼロになりますが、数値には先頭のゼロがないため、消えてしまいます。120を逆順にすると21になり、100000000を逆順にすると1になります。算術ループでは、空の結果に0を加えても0のままなので、ゼロは自動的に取り除かれます。
整数を反転する時間計算量はどれくらいですか？
ループは10進数の各桁につき1回実行され、数値 n は約 log10(n) + 1 桁あるため、時間計算量は O(log n) です。算術演算を使う方法では追加の空間計算量は O(1) です。文字列を使う方法では各桁をテキストとして格納するため、空間計算量は O(log n) です。
整数を反転するとオーバーフローすることがありますか？
はい、入力が任意の32ビット整数になり得る場合はそうです。1000000009は収まりますが、その逆の9000000001は収まりません。ここではnが10^9未満なので、逆の数は最大9桁で、必ず収まります。より大きな入力の場合は、乗算のたびにresult > (INT_MAX - digit) / 10を確認してください。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
Python
def reverseDigits(n):
# ここにコードを書いてくださいケース1
ケース2
ケース3
入力
n = 1234
期待値
4321