程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> leetcode筆記:Sqrt(x)

leetcode筆記:Sqrt(x)

編輯:C++入門知識

leetcode筆記:Sqrt(x)


一. 題目描述

Implement int sqrt(int x).
Compute and return the square root of x.

二. 題目分析

該題要求實現求根公式,該題還算是比較簡單的,因為只需返回最接近的整數,直接二分法即可。在實現的過程中還是有一些細節的,比如判斷條件:x / mid > mid而不能是x > mid * mid,因為mid * mid會導致溢出。

三. 示例代碼

#include 

using namespace std;

class Solution
{
public:
    int sqrt(int x)
    {
        if (x == 0 || x == 1) return x;
        int min = 1, max = x / 2; // 根必在此區間中
        // 二分查找
        int mid, result;
        while (min <= max)
        {
            mid = min + (max - min) / 2;
            if (x / mid > mid)
            {               
                // 根的平方需小於等於x,因此每次須在此處更新根的值
                result = mid; 
                min = mid + 1;
            }
            else if (x / mid < mid) max = mid - 1;
            else return mid;
        }
        return result;
    }
};

一些運行結果:

這裡寫圖片描述

四. 小結

此題為分治思路的經典題型之一。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved