iT邦幫忙

2021 iThome 鐵人賽

DAY 19
0
自我挑戰組

試煉之地 Leetcode 的挑戰系列 第 19

Leetcode 挑戰 Day 19 [ 633. Sum of Square Numbers ]

633. Sum of Square Numbers


今天我們一起挑戰leetcode第633題 Sum of Square Numbers! 這題雖然難度是medium,但其實題目相對比較單純一些,讓我們一起來看看!

題目


Given a non-negative integer c, decide whether there're two integers a and b such that a^2 + b^2 = c.

Example 1:
Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:
Input: c = 3
Output: false

Example 3:
Input: c = 4
Output: true

Example 4:
Input: c = 2
Output: true

Example 5:
Input: c = 1
Output: true

這題會給我們一個整數,並希望我們確認,是否能找到兩個任意整數,使此二整數a和b的平方和剛好等於題目給我們的整數。譬如5 = 1^2 + 2^2,5符合此條件,因此要回傳True,否則回傳False。

Sqrt and Forloop


我們可以利用sqrt來找到,此題a和b的可能最大值。通過移項,利用for迴圈來遍歷所有有可能的整數,並根據規則算出相對應的數,而再去利用找到的數,來做題目要求的檢查,只要找到一個符合的,就直接回傳True。遍歷完所有的可能整數後,還沒找到就回傳False

以下是python的程式碼

import math
class Solution:
    def judgeSquareSum(self, c: int) -> bool:
        m = int(math.sqrt(c))  # a或b可能的最大值
        for a in range(m+1):
            b = round(math.sqrt(c-a*a))
            if a*a + b*b == c:
                return True
        return False

上一篇
Leetcode 挑戰 Day 18 [ 367. Valid Perfect Square ]
系列文
試煉之地 Leetcode 的挑戰19

尚未有邦友留言

立即登入留言