LeetCode 367: isValidSquare 是否是完全平方數（Java）

nanchen2251 發布于2019-08-14 15:53 / 1989人閱讀

摘要：題目給一個正整數，判斷它是不是完全平方數。給的是型的正整數，所以下界是，上界是最大正整數的平方根。但要注意一定要用乘法來判斷相等時的情況。下面是代碼數學技巧所有的完全平方數都可以被表示成奇數和。

題目：給一個正整數，判斷它是不是完全平方數。

解法：

二分法。給的是int型的正整數，所以下界是1，上界是最大正整數Integer.MAX_VALUE的平方根。但要注意一定要用乘法來判斷相等時的情況。下面是代碼：

  public static int mySqrt(int x) {
        if(x == 0) return 0;
        int left = 1, right = Integer.MAX_VALUE;
        while(true){
            int mid = left + (right-left)/2;
            if(mid > x/mid)
                right=mid-1;
            else{
                if(mid+1>x/(mid+1))
                    return (int)mid;
                left=mid+1;
            }
        }
    }
    
    public static boolean isPerfectSquare(int num) {
        if(num == 0) return true;
        int left = 1, right = mySqrt(Integer.MAX_VALUE);
        while(right >= left){
            int mid = left + (right-left)/2;
            if(mid*mid == num)
                return true;
            else if(mid*mid > num)
                right = mid - 1;
            else
                left = mid + 1;
        }
        return false;
    }

2.數學技巧：所有的完全平方數都可以被表示成奇數和1+3+5+7+9 ...。

public boolean isPerfectSquare(int num) {
     int i = 1;
     while (num > 0) {
         num -= i;
         i += 2;
     }
     return num == 0;
 }

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66089.html

LeetCode 367. 有效的完全平方數

摘要：給定一個正整數，編寫一個函數，如果是一個完全平方數，則返回，否則返回。注意不要使用任何內置的庫函數，如。示例輸入輸出示例輸入輸出該題實現起來很簡單，數學上有個公式所以直接粗暴的解法就是循環減去每個奇數另外還可以用二分的思維給定一個正整數 num，編寫一個函數，如果 num 是一個完全平方數，則返回 True，否則返回 False。注意：不要使用任何內置的庫函數，如 sqrt。示...

jubincn 2019-08-23 11:26 評論0 收藏0
70道前端LeetCode題目集合及視頻講解（持續更新中...）

前端LeetCode刷題下面是已刷的題目的目錄。GitHub：https://github.com/cunzaizhuy...每日打卡更新中，歡迎關注。數組類 26 刪除排序數組中的重復項 27 移除元素 35 搜索插入位置 66 加1 80 medium 刪除排序數組中的重復項2 88 合并兩個有序數組 167 兩數之和II - 輸入有序數組 118 楊輝三角 169 easy 求眾數 1...

mayaohua 2019-08-26 10:46 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0
LeetCode 319 燈泡開關[數學] HERODING的LeetCode之路

摘要：解題思路這題本質就是數學，需要分析，每個燈泡會被翻轉的時機正好是他的約數次遍歷的時候，那么我們其實知道，對于每個數的約數都是成對出現的，除非是完全平方數，會有奇數個約數，所以，最后完全平方數的燈泡會亮，題目也就變成了找 ...

liujs 2021-11-16 11:45 評論0 收藏0