[Swift]LeetCode633.平方数之和|SumofSquareNumbers

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10475892.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given a non-negative integer c, your task is to decide whether there're two integers a and b such that a2 + b2 = c.

Example 1:

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: 3
Output: False

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c。

示例1:

输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5

示例2:

输入: 3
输出: False

Runtime: 8 ms

Memory Usage: 19 MB

 1 class Solution {
 2     func judgeSquareSum(_ c: Int) -> Bool {
 3         var a:Int = 0
 4         var b:Int = Int(sqrt(Double(c)))
 5         while (a <= b)
 6         {
 7             if a * a + b * b == c
 8             {
 9                 return true
10             }
11             else if a * a + b * b < c
12             {
13                 a += 1
14             }
15             else
16             {
17                 b -= 1
18             }
19         }
20         return false
21     }
22 }

8ms

 1 class Solution {
 2     func judgeSquareSum(_ c: Int) -> Bool {
 3         var c = c; var i = 2
 4         while (i*i <= c) {
 5             var multi = 0
 6             if (c % i == 0) {
 7                 while (c % i == 0) {
 8                     multi += 1
 9                     c /= i
10                 }
11                 if (i % 4 == 3 && multi % 2 != 0) {
12                     return false
13                 }
14             }
15             i += 1
16         }
17         return c % 4 != 3
18     }
19 }

12ms

 1 class Solution {
 2     func judgeSquareSum(_ c: Int) -> Bool {
 3         var left = 0
 4         var right: Int = Int(sqrt(Double.init(exactly: c)!))
 5         while left <= right {
 6             let cur = left*left + right*right
 7             if cur == c {
 8                 return true
 9             }
10 
11             if cur < c {
12                 left += 1
13             } else {
14                 right -= 1
15             }
16         }
17         return false
18     }
19 }

24ms

 1 class Solution {
 2   func judgeSquareSum(_ c: Int) -> Bool {
 3     let root = Int(sqrt(Double(c)))
 4     
 5     for i in 0...root {
 6       let diff = c - i * i
 7       let diffRoot = sqrt(Double(diff))
 8       
 9       if Double(Int(diffRoot)) == diffRoot {
10         return true
11       }
12     }
13     
14     return false
15   }
16 }

28ms

 1 class Solution {
 2     func judgeSquareSum(_ c: Int) -> Bool {
 3         for a in 0...Int(sqrt(Double(c))) {
 4             let b = Int(sqrt(Double(c - a * a)))
 5             if a * a + b * b == c {
 6                 return true
 7             }
 8         }
 9         return false
10     }
11 }