LeetCodeってなんですか？
シリコンバレーの名だたる企業や日本でも大きなサービスを展開するようなソフトウェア企業では、エンジニア採用でコーディング面接がある場合が多く、このサイトはその対策としてよく利用されるものです。
今回の問題
早いコードができたわけではないですが、他の解答よりシンプルなコードになっていると思ったので紹介しようと思いました。
・https://leetcode.com/problems/sqrtx/
問題文
Given a non-negative integer x,
return the square root of x rounded down to the nearest integer.
The returned integer should be non-negative as well.
You must not use any built-in exponent function or operator.
For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.
簡単な日本語訳
負の数でない整数値Xが与えられた時、Xの平方根の整数値部分のみを返せ。
※注意
ただし、C++ではpow(x, 0.5), pythonではx ** 0.5を使ってはならない。
上の関数は平方根がパっと出てくる便利な関数なんですが、使うなと言われてます。
解答
PythonとJavaScriptによる解答例を載せます。
(i)Python
class Solution:
def mySqrt(self, x: int) -> int:
ans = 0
while ans * ans <= x:
ans += 1
return ans - 1
(ii)JavaScript
/**
* @param {number} x
* @return {number}
*/
var mySqrt = function(x) {
let ans = 1
while (ans*ans <= x) {
ans ++
}
return ans - 1
};
解説
平方根なので、何らかの数を２乗したときにxになればいいということです。
ansというint型の変数を作って、これの２乗がxを超えるまでans+1を繰り返して、超えたタイミングのansから１だけ引いた数字を返せればいいのです。
例
x=3だとすれば、
ans=1のときは、 ans * ans = 1
ans=2のときは、 ans * ans = 4
です。
3の平方根は1.732.......ですが、
整数部分は1
です。
他の回答例
他には、二分探索のアルゴリズムを利用したものやニュートン法と呼ばれる方法があります。
参考までに、二分探索を用いたpythonコードを下記のURLから引用してみました。 こちらは、0~xまでの中央値から、２乗した結果が大きいのか小さいのかで処理をわけるので速いのはこちらです。
class Solution:
def mySqrt(self, x):
left, right = 0, x
while left <= right:
mid = left + (right - left) // 2
if mid * mid > x:
right = mid - 1
elif mid * mid < x:
left = mid + 1
else:
return mid
# left > right
return right
二分探索やニュートン法について、知りたい方は以下の記事を参考にしていただけると良いと思います。
まとめ
数字を扱う問題のときは、具体的な数字を入れてみればめちゃくちゃイメージがつきやすくなります。(数学の授業で同じようなことを言われた記憶があるな...)
今回はこの問題に対して、最も多い回答でなおかつ速いコードの二分探索に対して、他の提案をさせていただくものになりました。
コーディング面接では、どういう点を見ているのかその人事の方々に聞かないとわかりませんが、意外と少し速度として劣っていても、パッと見で簡単そう！って思うコードは需要あるんじゃないかな？って思いました。
おまけ
最後に、今回紹介したコードってどんなパフォーマンスなの？っていうのが、LeetCodeで見れるようになってるのでそれを載せて終わりにしようと思います。 ※Pythonでのパフォーマンスです。
Discussion