LeetCode第50題_Pow(x, n)_Divide & Conquer

-
題目
Implement pow(x, n), which calculates x raised to the power n (xn).



Example 1:
Input: 2.00000, 10
Output: 1024.00000
Example 2:
Input: 2.10000, 3
Output: 9.26100
Example 3:
Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
Note:
  • -100.0 < x < 100.0
  • n is a 32-bit signed integer, within the range [−231, 231 − 1]




需要考量的問題:
1.輸入的指數正負性
2.指數為奇為偶的情況


較直觀且簡易的一般作法
是直接跑Loop

當次方為1時代表保持不變回傳原本輸入的數值
其餘狀況
則判定指數n是否>1
是 ,則依序做n次累乘
否 ,則做累除



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/*
 * 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 leetcode50_pow;

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

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

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
        // TODO code application logic here
        BufferedReader inputBase, inputExponent;
        inputBase = new BufferedReader(new InputStreamReader(System.in));
        inputExponent = new BufferedReader(new InputStreamReader(System.in));

        System.out.println("Input:");
        String strBase = inputBase.readLine();
        String strExponent = inputExponent.readLine();

        double numBase = Double.parseDouble(strBase);
        int numExponent = Integer.parseInt(strExponent);

        System.out.println(myPow(numBase, numExponent));

    }
    //x^n次方
    //解法1.
    public static double myPow(double x, int n) {
        double res = 1;
        if (n == 1) {
            res = x;
        } else {
            if (n > 1) {
                for (int i = 1; i <= n; i++) {
                    res = (double) (res * x);
                }
            } else {
                for (int i = 1; i <= n * (-1); i++) {
                    res = (double) (res / x);
                }
            }
        }
        return res;
    }
}

當然這題如果直接用這種作法會  Exceed Time
所以要換另一種演算法來實踐改進
當輸入情況為如下case的時候

底數: 0.00001 指數: 2147483647

如果你拿去自己本機試跑會發現
跑了3分鐘多都還沒算完
沒耐心就中斷了


在此要介紹一個演算法思維技巧

就是「分治演算法」(Divide & Conquer)

在許多情況下分治法很常會搭配遞迴方式去對問題進行拆解
一般較為具體的流程

Step1. 分解:把遇到的問題可能規模一開始較大拆分為若干個小的模式且相互獨立維持原問題形式的子問題

Step2. 解決:如果透過上一步驟獲得之子問題可以解則進行解決反之則回至上一步以相同方式再次分解，直到可解決為止。

Step3. 合併:將第二步所解出來各個子問題解以某種規則合併出最終原始規模大的問題解



較困難的點在於如何去拆解問題然後做合併

這類解法主要目的
常為了解決像是降低時間複雜度(讓計算量不要負擔太大!!!!)
比方1000個數字要進行排序
把它一分為二變成兩個各自處裡500個數字的排序最和再合併
有點像做任務多一點分工的概念
直到最後將排序工作簡化為單獨去實踐兩個數字排序(比對)的概念
而此模式可以重複去調用而更能變得容易解決。

剛剛上述舉的例子就是快速排序的實作原理
================================================

還是不太懂!!!
我們舉一個更加淺顯易懂的例子
比方說有A、B兩個人在進行1到1000之間
猜數遊戲(A在問B來猜，A只會回答yes/no)

B就開始問
是1嗎?
是2嗎?
是3嗎?
....
是999嗎?

這就是O(n) --> 依序窮舉出來(又稱為順序查找)
最好的情況下是只需要一次就猜中(也就是查找目標就是第一個)
也就是O(1) -->只要比較1次
最差情況就是
要命中的該數是最後一個999
而我們的B則從1開始依序非常有耐心地猜問到第999次才命中
也就是O(n) --> 要比較n次

平均下來只少就要問500次


聰明的作法就是
大於500嗎?  --> 是
大於750嗎?  --> 是
大於625嗎?
...
每次透過縮小猜測範圍至上一次的一半

所以只需要10次以內即可把目標數字猜測出來
這種思維又稱為  二分查找
================================================

原作法和分治算法比較







當我們給的輸入
底數:2 指數:4的時候

原本我們要做4次累乘
2的1次方-> 2*1=2
2的2次方-> 2*2 = 4
2的3次方-> 4*2=8
2的4次方-> 8*2=16

經由二分法直接簡化成
可以將
2^4 -->4^2 -> 16
這部就是先將2的四次方 演變為
2的平方的平方
先計算2的平方部分獲得4
4在做一次  4*4即可獲得最終解
因此累計做乘法運算的次數為2




2^9 --> 2 *2^8 = 2* (2^2)^4=2*4^4
2*4^4 --> 2*(4^2)2 = 2*16^2







 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/*
 * 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 leetcode50_pow;

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

/**
 *
 * @author chous
 */
public class LeetCode50_Pow {
    private static int loopTimes = 0;
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
        // TODO code application logic here
        BufferedReader inputBase, inputExponent;
        inputBase = new BufferedReader(new InputStreamReader(System.in));
        inputExponent = new BufferedReader(new InputStreamReader(System.in));

        System.out.println("Input:");
        String strBase = inputBase.readLine();
        String strExponent = inputExponent.readLine();

        double numBase = Double.parseDouble(strBase);
        int numExponent = Integer.parseInt(strExponent);
        System.out.println(myPow(numBase, numExponent));
        System.out.println("迴圈執行次數:" + loopTimes);

        System.out.println(myPow2(numBase, numExponent));
        System.out.println("執行次數:" + loopTimes);
    }
    //x^n次方
    //解法1.
    public static double myPow(double x, int n) {
        double res = 1;
        if (n == 1) {
            res = x;
        } else {
            if (n > 1) {
                for (int i = 1; i <= n; i++) {
                    loopTimes ++;
                    res = (double) (res * x);
                }
            } else {
                for (int i = 1; i <= n * (-1); i++) {
                    res = (double) (res / x);
                }
            }
        }
        return res;
    }
    //解法2.分治法(二分法)
    //2^4 -> 4^2 -> 16
    public static double myPow2(double x,int n){
        double res = 1;
        if(n==0 || x==1) // 任何數值的0次方結果皆為1 , 1的任何次方結果皆為1
            return 1;
        if(n==1) //任何數值的1次方結果皆為自己本身
            return x;
        if(n<0)
            return 1/(x*myPow2(x,-(n+1)));
        
        while(n>1){
            if(n%2==1)//為奇數 2^9 = 2*2^8
                res*=x; //--> 2
            x = x*x;//
            n/=2; //  9/2=8
        }
        res*=x;
        return res;
    }
}



留言

張貼留言

這個網誌中的熱門文章

經得起原始碼資安弱點掃描的程式設計習慣培養(五)_Missing HSTS Header

-
圖片
  接續前幾篇系列 經得起原始碼資安弱點掃描的程式設計習慣培養(一)_OWASP Top 10(十大網站安全風險)_學習寫更安全程式碼的網站推薦 經得起原始碼資安弱點掃描的程式設計習慣培養(二)_8.Insecure Deserialization ：不安全的反序列化漏洞ASP.NET處理方式 經得起原始碼資安弱點掃描的程式設計習慣培養(三)_7.Cross Site Scripting(XSS)_Stored XSS_Reflected XSS All Clients 經得起原始碼資安弱點掃描的程式設計習慣培養(四)_1.Injection注入攻擊_SQL Injection)_order by 語句正確參數化套入 最近又遇到被若安掃描到高風險要修正的程式碼啦.... 一看這還真是搞不懂該怎麼修呢 HSTS(HTTP Strict Transport Security)  主要是一份國際標準規格 (RFC 6797) 的網際網路瀏覽安全機制， 用於宣告瀏覽器與伺服器之間通訊方式必須強制採用 TLS/SSL 加密通道。 只要從伺服器端送出一個 Strict-Transport-Security 標頭 (Header) 給瀏覽器，即可告知瀏覽器於未來的某段時間內一律使用 SSL 來和該網站連接 (設定可涵蓋所有子域名網站)， 一旦發生憑證失效情況，使用者將無法再瀏覽該網站，如此一來便可大幅減少中間人攻擊的問題發生。 再更白話一點 HSTS Header 就是負責將 http 強制轉為 https CheckMarx掃碼報告給的說明 ============================================================ 風險: 如果web config沒有設置HSTS表頭、"max-age"(有效期)不足一年， 或沒有設定"includeSubDomains"(包含所有子網域)，可能會使用戶容易遭受中間人攻擊。 發生原因: 許多使用者只要在瀏覽器的網址列輸入網域名稱(Domain Name)即可瀏覽網站， 並沒有輸入協定(Protocol)的名稱。 瀏覽器會自動假設使用者使用的是HTTP協定而不是有加密機制的HTTPS協定。 在第一次發出前往特定網站的請求時，攻擊者可以執行中間人攻擊並將用戶轉址到
閱讀完整內容

經得起原始碼資安弱點掃描的程式設計習慣培養(三)_7.Cross Site Scripting(XSS)_Stored XSS_Reflected XSS All Clients

-
圖片
  近期新加入的功能code剛好也被CheckMarx掃出高風險部分的程式碼漏洞 我也踏到這個Issue啦 Cross Site Scripting(XSS)  第一種.Stored XSS 高風險 CheckMarx掃碼報告給的說明[Stored XSS] ============================================================ 風險: 攻擊者可以利用合法存取應用程式提交資料到資料庫。 當另一個使用者隨後存取該資料，網頁可能會被改寫且惡意腳本可能會被啟動。 發生原因: 從資料庫中的資料建立網頁。資料直接嵌入至HTML的頁面，利用瀏覽器顯示。 資料可能源自於其他使用者的輸入。 如果資料包含HTML片段或Javascript，使用者無法分辨是否為預期的頁面。 該漏洞主因為未先對嵌入資料庫中的資料進行編碼(Encode) 來預防瀏覽器將其當為HTML的格式而非純文字。 如何避免: 1.驗證所有資料，無論其來源為何。驗證應基於白名單：僅接受預定結構的資訊，而不是拒絕不良的樣式(Patterns)。  應確認：  ● 資料型態  ● 大小  ● 範圍  ● 格式  ● 期望值  2. 驗證無法取代編碼. 輸出嵌入之前，不論其來源， 將所有動態資料進行編碼. 編碼方式應該是上下文相關的. 例如: ● HTML內容使用HTML的編碼方式  ● HTML編碼特性是將資料輸出到特性的值 ● JavaScript的編碼方式為伺服器產生的Javascript  3.考慮使用ESAPI的編碼庫，或它的內置功能。對於舊版的ASP.NET，請考慮使用AntiXSS.  4.在HTTP類型對應的表頭， 明確定義整個頁面的字元編碼.  5. 設置 httpOnly 標誌於會期資訊，以防止利用XSS來竊取資訊. ============================================================ 這裡報告描述是指我對傳進來字串參數直接拋給DAL處裡的類別執行查詢 這裡缺乏對輸入進來的字串參數做一些查檢判斷 也建議在帶入時對參數也做一些html encode處理 這裡用AntiXSS來Encode 第二種.Reflected XSS All Clients 高風險 CheckMarx掃碼報告給的說明[Reflecte
閱讀完整內容

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

-
圖片
  若是出現 「必須」、「必需」、「...必...」、「應由」、「應先」、「應...」 則很高機率是圈 是非通常只要是如下字眼 「不必」+動詞 、「不需」「不須」、「可不」、「可以不」、「可立即」 有出現或符合的都選叉 (X)1.違規記點又不登記在駕照上，所以可以 不必理會 而任意違反交通規則。 (X)2.發生重大交通事故，為迅速恢復交通，清除現場，可 不必等待 肇事處理機關之指示，即可進行。 (X)3.道路駕駛練習，行車前 不必實施 車輛安全檢查，因為那是駕駛教練的工作。 (X)4.開車前， 不必檢查 機件安全，但在行駛中要隨時注意儀錶功能顯示，確保行車安全。 (X)5.煞車油若經常低於"MIN"線，只要添加即可， 不必到修理廠檢修 。 (X)6.冷卻系統只要副水箱在滿水位，主水箱 不必檢查 也不會有問題。 (X)7.引擎冷卻水內含有防凍液或防銹劑，可 不必更換 。 (X)8.儀錶板上的「燃油油量錶」之指針高度，已經降低至「E」點，橘色的「低油料警示燈」點亮時， 不必急著加油 ，到達目的地後再行補充燃油即可。 (X)9.有安全氣囊裝備的汽車， 不必繫 安全帶。 (X)10.煞車時有異音，是正常的情況， 不必檢修 。 (X)11.汽車定期檢驗 不必檢驗 車輛故障標誌，所以隨車不一定要帶車輛故障標誌。 (X)12.開車時 不必理會 義交之指揮，一切以號誌為主。 (X)13.汽車經過隧道，因隧道內燈光明亮視線良好，為省電可 不必開亮 頭燈。 (X)14.駕駛人只求技術優良，對遵守交通規則 不必太重視 。 (X)15.在開車前， 不必檢查 機件，以免耽誤行車時間。 (X)16.遇幼童專用車、校車、身心障礙者用特製車或教練車， 不必禮讓 。 (X)17.行車 不必攜帶 隨車工具。 (X)18.行車起駛前進， 不必顯示 方向燈。 (X)19.汽車通過鐵路平交道，前後兩車間， 不必保持 距離。 (X)20.夜間將車輛停放在無燈光設備及照明不清之道路時，亦 不必顯示 停車燈光或反光標識。 (X)21.在夜間或有霧靄、雨雪、風沙及晝晦時，把車輛停在路旁， 不必顯示 停車燈光或反光標識。 (X)22.汽車駕駛人，僅需具有優良駕駛技術， 不需 具備急救的常識和技能。 (X)23.汽車車身、引擎、底盤、電系等重要設備變更或調換時， 不需 向公路主管機關申請臨時檢驗。
閱讀完整內容