C#刷遍Leetcode面試題系列連載（4）：No.633 – 平方數之和
- 2019 年 10 月 21 日
- 筆記
上篇文章中一道數學問題 – 自除數，今天我們接著分析 LeetCode 中的另一道數學題吧~
今天要給大家分析的面試題是 LeetCode 上第 633 號問題，
Leetcode 633 – 平方數之和
https://leetcode.com/problems/sum-of-square-numbers/
題目描述
給定一個非負整數 c ，你要判斷是否存在兩個整數 a和 b，使得 (a^2 + b^2 = c)。
示例1:
輸入: 5 輸出: True 解釋: 1 * 1 + 2 * 2 = 5示例2:
輸入: 3 輸出: FalseInput:
5 2 100Expected answer:
true true true-
題目難度: 簡單
-
貢獻者： Stomach_ache
相關話題
相似題目
解題思路:
做一次循環，用目標和減去循環變數的平方，如果剩下的部分依然是完全平方的情形存在，就返回true；否則返回false。
假定 $i leq a leq b $，根據數據的對稱性，循環變數 i 只需取到 $i^2 cdot 2 leq c $ 即可覆蓋所有情形.
已AC程式碼:
最初版本:
public class Solution { public bool JudgeSquareSum(int c) { for (int i = 0; c - 2 * i * i >= 0; i++) { double diff = c - i*i; if ((int)(Math.Ceiling(Math.Sqrt(diff))) == (int)(Math.Floor(Math.Sqrt(diff)))) // 若向上取整=向下取整，則該數開方後是整數 return true; } return false; } }Rank:
執行用時: 56 ms, 在所有 csharp 提交中擊敗了68.18%的用戶.
優化1:
public class Solution { public bool JudgeSquareSum(int c) { for (int i = 0; c - 2 * i * i >= 0; i++) { int diff = c - i*i; if (IsPerfectSquare(diff)) return true; } return false; } private bool IsPerfectSquare(int num) { double sq1 = Math.Sqrt(num); int sq2 = (int)Math.Sqrt(num); if (Math.Abs(sq1 - (double)sq2) < 10e-10) return true; return false; } }Rank:
執行用時: 52 ms, 在所有 csharp 提交中擊敗了90.91%的用戶.
優化2(根據文末參考資料[1]中MPUCoder 的回答改寫):
public class Solution { public bool JudgeSquareSum(int c) { for (int i = 0; i <= c && c - i * i >= 0; i++) { int diff = c - i*i; if (IsPerfectSquare(diff)) return true; } return false; } public bool IsPerfectSquare(int num) { if ((0x0213 & (1 << (num & 15))) != 0) //TRUE only if n mod 16 is 0, 1, 4, or 9 { int t = (int)Math.Floor(Math.Sqrt((double)num) + 0.5); return t * t == num; } return false; } }Rank:
執行用時: 44 ms, 在所有 csharp 提交中擊敗了100.00%的用戶.
優化3(根據文末參考資料[1]中 Simon 的回答改寫):
public class Solution { public bool JudgeSquareSum(int c) { for (int i = 0; c - i * i >= 0; i++) { long diff = c - i*i; if (IsSquareFast(diff)) return true; } return false; } bool IsSquareFast(long n) { if ((0x2030213 & (1 << (int)(n & 31))) > 0) { long t = (long)Math.Round(Math.Sqrt((double)n)); bool result = t * t == n; return result; } return false; } }Rank:
執行用時: 48 ms, 在所有 csharp 提交中擊敗了100.00%的用戶.
另外，stackoverflow上還推薦了一種寫法：
public class Solution { public bool JudgeSquareSum(int c) { for (int i = 0; c - 2 * i * i >= 0; i++) { double diff = c - i*i; if (Math.Abs(Math.Sqrt(diff) % 1) < 0.000001) return true; } return false; } }事實上，速度並不快~
Rank:
執行用時: 68 ms, 在所有 csharp 提交中擊敗了27.27%的用戶.
相應程式碼已經上傳到github:
https://github.com/yanglr/Leetcode-CSharp/tree/master/leetcode633
參考資料:
[1] Fast way to test whether a number is a square
https://www.johndcook.com/blog/2008/11/17/fast-way-to-test-whether-a-number-is-a-square/
[2] Shortest way to check perfect Square? – C#
https://stackoverflow.com/questions/4885925/shortest-way-to-check-perfect-square/4886006#4886006
