LeetCode第633題_Sum of Square Numbers

- 7月 22, 2018

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

題目就是給定一個數輸入
判定是不是某兩個數的平方和

就是如此

1 -> 0^2 + 1^2 =1 -> true
2-> 1^2 + 1^2 = 2 -> true
...
3 -> x
4-> 0^2+2^2 = 4 ->true

第一版.直觀法(暴力法) 使用兩層迴圈去跑範圍皆從0跑到該數
利用演算法【奇數之平方和必為一可開平方數】

圖像理解(正方形的邊)

所以改寫至程式進行算法優化後

原本輸入9
我的作法是給其跑兩層迴圈
i從0到9
j從0到9

-------------------------------
i=0時 j=0,j=1,j=2.......j=9給個都去跑
.
.
.

i=9時 j=0,j=1,j=2.......j=9

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package leetcode633_sumofsquarenumbers;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 *
 * @author chous
 */
public class LeetCode633_SumOfSquareNumbers {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
        // TODO code application logic here
        BufferedReader input;
        input = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Input");
        String strInput = input.readLine();
        int numInput = Integer.parseInt(strInput);
        System.out.println(judgeSquareSum(numInput));
        
        
        
    }
    public static boolean judgeSquareSum(int c) {
        if(c==0 || c==1)
            return true;
        for(long i=0;i<=c;i++){
            for(long j=0;j<=c;j++){
                if(i*i + j*j == c)
                    return true;
            }
        }
        return false;
    }
}

邏輯正確但是丟上去會逾時
時間複雜度為 O(n^2) 跑了雙層loop
較不優
當輸入為 1000000000

補上一個用來打印驗證用途的函數區塊

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package leetcode633_sumofsquarenumbers;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 *
 * @author chous
 */
public class LeetCode633_SumOfSquareNumbers {
    private static long num1;
    private static long num2;
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
        // TODO code application logic here
        BufferedReader input;
        input = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Input");
        String strInput = input.readLine();
        int numInput = Integer.parseInt(strInput);
        System.out.println(judgeSquareSum(numInput));
        
    }
    public static boolean judgeSquareSum(int c) {
        if(c==0 || c==1)
            return true;
        for(long i=0;i<=c;i++){
            for(long j=0;j<=c;j++){
                if(i*i + j*j == c){
                    testPrint(i,j);
                    return true;
                }
            }
        }
        return false;
    }
    
    public static void testPrint(long n1,long n2){
        System.out.println("num1:"+ n1 );
        System.out.println("num2:" + n2);
    }
}

第二種優化作法.範圍跑至該數的平方根即可

改善為
只跑一層loop
而且取9開跟後的3為上限(a<=3)
a=0 -> b = c(原本輸入的數值9) - 0^2 = 9 -> 0*0 + 9*9 不等於9
a=1 -> b = 9 - 1 =8 -> 1*1 + 8*8 不等於9
a=2 -> b = 9-2^2 = 5 -> 2*2 + 5*5 不等於9
a=3 -> b = 9-3^2 = 0 -> 3*3 + 0*0 = 9 結束

所以這題我們透過必氏定理( a平方+b平方的開根號 = 第三邊 )
公式的變數替換先省略掉查找第二個值得迴圈層

a跑的範圍鎖定從0至該數的開方根

CODE

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package leetcode633_sumofsquarenumbers;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 *
 * @author chous
 */
public class LeetCode633_SumOfSquareNumbers {
    private static long num1;
    private static long num2;
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
        // TODO code application logic here
        BufferedReader input;
        input = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Input");
        String strInput = input.readLine();
        int numInput = Integer.parseInt(strInput);
        //System.out.println(judgeSquareSum(numInput));
        System.out.println(judgeSquareSum2(numInput));
    }
    public static boolean judgeSquareSum(int c) {
        if(c==0 || c==1)
            return true;
        for(long i=0;i<=c;i++){
            for(long j=0;j<=c;j++){
                if(i*i + j*j == c){
                    return true;
                }
            }
        }
        return false;
    }
    //a^2 + b^2 = c --> c - a^2 = b^2
    public static boolean judgeSquareSum2(int c) {
        if(c==0 || c==1)
            return true;
        int m = (int) Math.sqrt(c);
        for(long a=0;a<=m;a++){
            int b = (int) Math.sqrt(c - a*a);
            if(a*a + b*b == c)
                return true;
        }
        return false;
    }
}

測試跑過了

搜尋此網誌

第25個冬天

LeetCode第633題_Sum of Square Numbers

留言

張貼留言

這個網誌中的熱門文章

何謂淨重(Net Weight)、皮重(Tare Weight)與毛重(Gross Weight)

Architecture(架構) 和 Framework(框架) 有何不同?_軟體設計前的事前規劃的藍圖概念

(2021年度)駕訓學科筆試準備題庫歸納分析_法規是非題