LeetCodeに毎日挑戦してみた 69. Sqrt(x)（Python、Go）

はじめに

無料英単語サイトE-tanを運営中の@ishishowです。

プログラマとしての能力を上げるために毎日leetcodeに取り組み、自分なりの解き方を挙げていきたいと思います。

Leetcodeとは

leetcode.com
ソフトウェア開発職のコーディング面接の練習といえばこれらしいです。
合計1500問以上のコーデイング問題が投稿されていて、実際の面接でも同じ問題が出されることは多いらしいとのことです。

golang入門＋アルゴリズム脳の強化のためにgoとPythonで解いていこうと思います。(Pythonは弱弱だが経験あり)

17問目（問題69)

69. Sqrt(x)

問題内容

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

（日本語訳）

2つのバイナリ文字列aとが与えられた場合b、それらの合計をバイナリ文字列として返します。

負でない整数が与えられた場合x、の平方根を 計算して返しxます。

戻り値の型は整数であるため、10進数は切り捨てられ、結果の整数部分のみが返されます。

Example 1:

Input: x = 4
Output: 2

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Constraints:

• 0 <= x <= 231 - 1

考え方

1. バイナリーサーチという探索方法を使用します。

2. 左端と右端（l,r）を定義し、検索する間隔を半分にしながらループで回していきます。

3. midの二乗とmid+1の二乗に値が入った時midを返します

• 解答コード

class Solution(object):
    def mySqrt(self, x):
        l, r = 0, x
        while l <= r:
            mid = l + (r-l)//2
            if mid * mid <= x < (mid+1)*(mid+1):
                return mid
            elif x < mid * mid:
                r = mid - 1
            else:
                l = mid + 1

• Goでも書いてみます！(goではバイナリーサーチしていません)

func mySqrt(x int) int {
    for i := 1; i <= x; i++ {
        if i*i == x { return i }
        if i*i > x { return i-1 }
    }
    return 0
}