LeetCode #29. Divide Two Integers プログラミング練習
問題:
難易度: medium
入力: (int) devidend, (int) devidsor
目的: devidendをdevidsorで割った結果を返せ。
出力: int
入力は二つの整数、除数と被除数、つまりは割る数字と割られる数字です。
/を使ってしまえば一発と言いたいところですが当然そんな簡単な問題ではなく、
割り算を*と/なしで表せと言う問題です。
足し算と引き算で割り算をすればいいのです。
但しその場合正数や非正数、除数が0、intをオーバーフローしてしまった等とボーダーケースをきちんと考えましょう。
注意すべき事:
- 除数は0ではない
- 答えは32-bit int型に入る
- 入力がマイナスの時注意
以下回答です。
class Solution { public int divide(int dividend, int divisor) { long a = dividend; long b = divisor; long res = 0; int sign = 0; if (a<0 && b>0) sign = 1; if (a>0 && b<0) sign = 1; b = Math.abs(b); a = Math.abs(a); long c = b; long i = 1; while (b<a-b) { b += b; i += i; } while (a>=c) { if (a >= b) { a -= b; res += i; } else { b -= c; i--; } } res = sign == 0 ? res:-res; if (res > Integer.MAX_VALUE || res < Integer.MIN_VALUE) return Integer.MAX_VALUE; else return (int)res; } }
中学校くらいでやったかもしれない問題をプログラミングしましょう。
まずはマイナス入力がややこしいのですべて絶対値を取り、最後にマイナスプラスを判断する。
しかしこの時int型は-2,147,483,648 ~ 2 147,483,647なので、-2,147,483,648が入力された場合はオーバーフローします。
なのでlongで保管。
後は普通に割り算を引き算で真似て最後にプラスマイナスを判断するだけです。
Integer.MAX_VALUEより大きい場合はMAX_VALUEを返す。
今日は以上。
よいプログラミング生活を!