【好書推薦】《劍指Offer》之硬技能(編程題12~16)

来源:https://www.cnblogs.com/yulinfeng/archive/2019/06/21/11062335.html
-Advertisement-
Play Games

本文例子完整源碼地址:https://github.com/yu-linfeng/BlogRepositories/tree/master/repositories/sword 《【好書推薦】《劍指Offer》之軟技能》 《【好書推薦】《劍指Offer》之硬技能(編程題1~6)》 《【好書推薦】《劍 ...


本文例子完整源碼地址:https://github.com/yu-linfeng/BlogRepositories/tree/master/repositories/sword

《【好書推薦】《劍指Offer》之軟技能》

《【好書推薦】《劍指Offer》之硬技能(編程題1~6)》

《【好書推薦】《劍指Offer》之硬技能(編程題7~11)》

持續更新,敬請關註公眾號:coderbuff,回覆關鍵字“sword”獲取相關電子書。

12.矩陣中的路徑

題目:請設計一個函數,用來判斷一個矩陣中是否存在一條包含其字元串所有字元的路徑。路徑可以從矩陣中的任意一格開始,每一步可以在矩陣中向左、右、上、下移動一格。如果一條路徑經過了矩陣的某一格,那麼該路徑不能再次進入該格子。

*回溯法:適合由多個步驟組成的問題,並且每個步驟有多個選項。

 1 /**
 2 * 矩陣中是否存在給定路徑
 3 * @author OKevin
 4 * @date 2019/6/4
 5 **/
 6 public class Solution {
 7 
 8    /**
 9     *
10     * @param matrix 一位數組表示矩陣
11     * @param rows 行數
12     * @param cols 列數
13     * @param path 路徑
14     * @return true-存在;false-不存在
15     */
16    public boolean findPath(char[] matrix, Integer rows, Integer cols, char[] path) {
17        if (matrix == null || rows <= 0 || cols <= 0 || path == null) {
18            return false;
19        }
20        boolean[] visited = new boolean[rows * cols];
21        int pathLength = 0;
22        for (int row = 0; row < rows; row++) {
23            for (int col = 0; col < cols; col++) {
24                if (findPathCore(matrix, rows, cols, row, col, path, pathLength, visited)) {
25                    return true;
26                }
27            }
28        }
29        return false;
30    }
31 
32    private boolean findPathCore(char[] matrix, Integer rows, Integer cols, int row, int col, char[] path, int pathLength, boolean[] visited) {
33        if (pathLength == path.length) {
34            return true;
35        }
36        if (row >= 0 && row < rows && col >= 0 && col < cols && matrix[row * cols + col] == path[pathLength] && !visited[row * cols + col]) {
37            visited[row * cols + col] = true;
38            pathLength++;
39            if (findPathCore(matrix, rows, cols, row, col - 1, path, pathLength, visited)
40                    || findPathCore(matrix, rows, cols, row - 1, col, path, pathLength, visited)
41                    || findPathCore(matrix, rows, cols, row, col + 1, path, pathLength, visited)
42                    || findPathCore(matrix, rows, cols, row + 1, col, path, pathLength, visited)) {
43                return true;
44            }
45            visited[row * cols + col] = false;
46 
47        }
48        return false;
49    }
50 }

13.機器人的運動範圍

題目:地上有一個m行n列的小方格,一個機器人從坐標(0,0)的格子開始移動,它每次可以向上、下、左、右移動一格,但不能進入行坐標和列坐標的數位之和大於k的格子。例如:當k=18,機器人能夠進入方格(35,37),因為3+5+3+7=18,但不能進入(35,38),因為3+5+3+8=19。請問k=18時,機器人能夠到達多少個格子。

此題有一個小的點需要靠平時的積累,數位和的計算。

 1 /**
 2 * 計算數位和
 3 * 例如:85的數位和為8+5=13
 4 * 計算過程:
 5 * 85 % 10 = 5(個位)
 6 * 85 / 10 = 8(移除個位)
 7 * 8 % 10 = 8(十位)
 8 * 5 + 8 = 13
 9 * @param number 數字
10 * @return 數位和
11 */
12 private int getDigitSum(int number) {
13    int sum = 0;
14    while (number > 0) {
15        sum += number % 10;
16        number /= 10;
17    }
18    return sum;
19 }

另外還需要註意幾個臨界條件:

  1. 訪問的行和列一定是大於等於0;

  2. 訪問的行和列一定是小於總行數和總列數(並不是小於等於,因為是從第0行開始)

  3. 行和列的數位和小於閾值

  4. 沒有被訪問過

row >= 0 && row < rows && col >= 0 && col < cols && (getDigitSum(row) + getDigitSum(col) < threshold) && !visited[row * cols + col]

題目中看似提到了m行n列,立馬想到了用二維數字來表示。實際上如果用二維數組是增加了複雜性,用一維數組同樣能表示出二維數組。例如:m行n列就一共又m*n個元素,visited[m*n]。訪問第1行第1列,在一維數組中則為visited[1*m+1],訪問第1行第2列則為visited[1*m+2],也就是在一位數組中,數據是按照一列一列存放的。如果要訪問第2行是2*cols+第幾列。

另外既然需要求出達到多少個格子,則是需要訪問格子周圍即:(i - 1, j)、(i, j - 1)、(i + 1, j)、(i, j + 1)。

 1 /**
 2 * Description:
 3 * 機器人的運動範圍
 4 * 2019-06-18
 5 * Created with OKevin.
 6 */
 7 public class Solution {
 8    public int movingCount(int threshold, int rows, int cols) {
 9        if (threshold < 0 || rows <= 0 || cols <= 0) {
10            return 0;
11        }
12        boolean[] visited = new boolean[rows * cols];
13        int count = movingCountCore(threshold, rows, cols, 0, 0, visited);
14        return count;
15    }
16 
17    private int movingCountCore(int threshold, int rows, int cols, int row, int col, boolean[] visited) {
18        int count = 0;
19        if (check(threshold, rows, cols, row, col, visited)) {
20            visited[row * cols + col] = true;
21            /**
22             * 當前訪問到了(i, j)坐標,此時則繼續訪問(i - 1, j)、(i, j - 1)、(i + 1, j)、(i, j + 1)
23             */
24            count = 1 + movingCountCore(threshold, rows, cols, row - 1, col, visited) + movingCountCore(threshold, rows, cols, row, col-1, visited) + movingCountCore(threshold, rows, cols, row + 1, col, visited) + movingCountCore(threshold, rows, cols, row + 1, col, visited);
25        }
26        return count;
27    }
28 
29    private boolean check(int threshold, int rows, int cols, int row, int col, boolean[] visited) {
30        //橫坐標與縱坐標的數位和相加小於閾值,且沒有訪問過
31        if (row >= 0 && row < rows && col >= 0 && col < cols && (getDigitSum(row) + getDigitSum(col) <= threshold) && !visited[row * cols + col]) {
32            return true;
33        }
34        return false;
35    }
36 
37    /**
38     * 計算數位和
39     * 例如:85的數位和為8+5=13
40     * 計算過程:
41     * 85 % 10 = 5(個位)
42     * 85 / 10 = 8(移除個位)
43     * 8 % 10 = 8(十位)
44     * 5 + 8 = 13
45     * @param number 數字
46     * @return 數位和
47     */
48    private int getDigitSum(int number) {
49        int sum = 0;
50        while (number > 0) {
51            sum += number % 10;
52            number /= 10;
53        }
54 
55        return sum;
56    }
57 }

14.剪繩子

題目:一段長度為n的繩子,請把繩子剪成m段(m、n都是整數,n>1且m>1),每段繩子的長度為k[0]、k[1]、……、k[m]。請問k[0]*k[1]*……*k[m]可能的最大乘積是多少?例如,當繩子的長度為8時,我們把它剪成長度分別為2,3,3的三段,此時的最大乘積是18。

這道題是求解最優化問題。理論上講,在題目中出現最大、最小、一共有多少種解法都可以用動態規劃求解。

解法一:動態規劃

拿到這道題,習慣性的可能會先從由上往下的解題思路去想,比如:長度為9,可以分為幾段:1,1,7;1,2,6等等。會去思考這個長度會分成幾個段,再將每個段的乘積求出來,取最大的那個段。

但實際上,對於求解最優化問題,可以轉換為一系列子問題。對於本題一段繩子來講,它無論如何都至少被切為2段。例如長度為8時,可能被切為:1,7;2,6;3,5;4,4。當然還有5,3,這實際上又和前面重覆了,所以一段繩子如果被切為2段,就只有n/2種可能性。

切為2段並不是最終的最大乘積長度,例如8切為了以上4種可能性的兩段,並不意味著8的切成m段的最大乘積長度為15(3*5)。它當然還能切為2*3*3=18。那為什麼說只需要切為2段呢?

這是因為我們需要把這個問題不斷地劃分為小的問題。

例如8被切為了1和7,這兩段不能再繼續切分,它就是最小的問題;同理,8被切為了2和6,但是6仍然可以繼續被切為1和5,2和4,3和3,所以2和6並不是最小的問題,以此類推,最終推出長度為6的繩子切成m段的最大乘積是9(3*3),那麼8被切為2和6時,2*9就等於18。同理繼續推3和5,4和4。

上面的分析得出了什麼樣的結論呢?結論就是,只需要想象成2段,再各自繼續切2段。也就是說假設長度為n的繩子,f(n)是它的各段最大乘積長度,它在被切第一刀時,第一段長度為(1,2,...n-1),第二段的長度為(n-1,n-2,...,1)。推出f(n)=max(f(i)*f(n-1))的關聯關係。這裡一定需要好好理解,切成2段後,並不是直接將兩段相乘,而是再繼續將各段切分直至不能再切且取最大乘積長度

在《演算法筆記》(刁瑞 謝妍著)一書中對動態規劃做了求解步驟的總結:

  1. 定義子問題

  2. 定義狀態轉換規則,即遞推關係

  3. 定義初始狀態

套用到這套題上,我認為就是需要明確以下3點:

  1. 該問題的核心在於求出每段的最大乘積長度,這是子問題,也就是上文所述,再被切為兩段時,需要明確是否能繼續切直至不能再切且取最大乘積長度。

  2. 遞推關係,也已明確(n)=max(f(i)*f(n-1))

  3. 初始狀態,長度為1不能切,長度為2最長為1,長度為3最長為2。

 1 /**
 2 * Description:
 3 * 剪繩子——動態規劃
 4 * 2019-06-19
 5 * Created with OKevin.
 6 */
 7 public class Solution1 {
 8 
 9    public int maxProductAfterCutting(int length) {
10        if (length < 2) {
11            return 0;
12        }
13        if (length == 2) {
14            return 1;
15        }
16        if (length == 3) {
17            return 2;
18        }
19        int[] products = new int[length + 1];   //數組中存儲的是每段的最優解
20        //大於長度3的繩子,當然可以劃分出1,2,3長度的繩子
21        products[0] = 0;
22        products[1] = 1;
23        products[2] = 2;
24        products[3] = 3;
25        int max = 0;
26        for (int i = 4; i <= length; i++) {
27            max = 0;
28            for (int j = 1; j <= i / 2; j++) {  //除以2的原因在上文中也以提到,將一段繩子劃分為2段時,實際上中間後的切分和前面是重覆的
29                int product = products[j] * products[i - j];    //遞推關係f(i)*f(n-1)
30                if (max < product) {
31                    max = product;
32                }
33                products[i] = max;
34            }
35        }
36        max = products[length];
37        return max;
38    }
39 }

優點:動態規劃類似於分治演算法,將大的問題逐步劃分為小的問題求解。

缺點:此題採用動態規劃的時間複雜度為O(n^2),且空間複雜度為O(n)

解法二:貪婪演算法

貪婪演算法的核心是,先挑最大的,再挑比較大的,再挑小的(貪婪嘛)。

本題對於長度為n(n>=5)的繩子應儘量多劃分為長度3的段。對於長度為4的段,應劃分為長度為2的段。

也即是,如果長度為10,那麼10/3=3個長度為3的段,劃分結果為3*3*3*1,最後一個段為1,劃分為3*3*4。

 1 /**
 2 * Description:
 3 * 剪繩子——貪婪演算法
 4 * 2019-06-20
 5 * Created with OKevin.
 6 */
 7 public class Solution2 {
 8    public int maxProductAfterCutting(int length) {
 9        if (length < 2) {
10            return 0;
11        }
12        if (length == 2) {
13            return 1;
14        }
15        if (length == 3) {
16            return 2;
17        }
18        int timesOf3 = length / 3;
19        if (length - timesOf3 * 3 == 1) {
20            timesOf3 -= 1;
21        }
22        int timesOf2 = (length - timesOf3*3) / 2;
23        return (int) (Math.pow(3, timesOf3) * Math.pow(2, timesOf2));
24    }
25 }

15.二進位中1的個數

題目:請實現一個函數,輸入一個整數,輸出該數二進位表示中1的個數。例如,把9表示成二進位是1001,有2位是1。因此,如果輸入9,則該函數輸出2。

此題可採用移位運算+與運算求解

 1 /**
 2 * Description:
 3 * 移位運算+與運算
 4 * 2019-06-20
 5 * Created with OKevin.
 6 */
 7 public class Solution {
 8    public int NumberOf1(int num) {
 9        int count = 0;
10        while (num != 0) {
11            if ((num & 1) == 1) {
12                count++;
13            }
14            num = num >>> 1;    //因為運算>>>表示無符號右移,意味著如果是負數,仍然會向右移,同時用0補齊。如果使用>>有符號右移,那麼符號位1永遠會存在,也就是會產生死迴圈
15        }
16        return count;
17    }
18 }

16.數值的整數次方

題目:實現函數Math.pow,求m的n次方。

迴圈暴力法

 1 /**
 2 * Description:
 3 * 迴圈暴力法
 4 * 2019-06-20
 5 * Created with OKevin.
 6 */
 7 public class Solution1 {
 8    public int pow(int m, int n) {
 9        int result = 1;
10        for (int i = 0; i < n; i++) {
11            result *= m;
12        }
13        return result;
14    }
15 }

很遺憾,這種解法連校招級都算不上,頂多算是剛學習編程時的水平。

其實這道題,並沒有考查過多的演算法,更多的是考查對細節的把握。一個數的整數次方,不光是整數,還有可能是負數,也有可能是0。如果數值為0,則0的冪是沒有意義的。

 1 /**
 2 * Description:
 3 * 考慮指數為0,負數,整數;數值為0的情況;0^0在數學上沒有意義
 4 * 2019-06-21
 5 * Created with OKevin.
 6 */
 7 public class Solution2 {
 8 
 9    public double pow(int m, int n) {
10        double result = 0;
11        if (m == 0 && n < 0) {
12            return -1;
13        }
14        int absN = Math.abs(n);    //取絕對值
15        result = calc(m, absN);
16        if (n < 0) {
17            result = 1 / result;
18        }
19        return result;
20    }
21 
22    private int calc(int m, int n) {
23        int result = 1;
24        for (int i = 0; i < n; i++) {
25            result *= m;
26        }
27        return result;
28    }
29 }

改進後的代碼考慮到了指數是負數的情況。但實際上這仍然有優化的空間。如果指數是32,意味著calc方法需要迴圈31次。然而實際上迴圈到一半的時候就可以求它本身。也就是說a^n/2 * a^n/2,n為偶數;a^(n-1)/2 * a^(n-1)/2 * a,n為奇數。

改進後的calc方法:

 1 private int calc(int m, int n) {
 2    if (n == 0) {
 3        return 1;
 4    }
 5    if (n == 1) {
 6        return m;
 7    }
 8    int result = calc(m, n >> 1);    //右移1位表示除以2
 9    result *= result;
10    if ((m & 1) == 1) {     //位運算判斷是會否為奇數,奇數的二進位第一位一定是1與1做與運算即可判斷是否為奇數,代替m%2是否等於0
11        result *= m;
12    }
13    return result;
14 }

本文例子完整源碼地址:https://github.com/yu-linfeng/BlogRepositories/tree/master/repositories/sword

《【好書推薦】《劍指Offer》之軟技能》

《【好書推薦】《劍指Offer》之硬技能(編程題1~6)》

《【好書推薦】《劍指Offer》之硬技能(編程題7~11)》

持續更新,敬請關註公眾號:coderbuff,回覆關鍵字“sword”獲取相關電子書。

 

 

這是一個能給程式員加buff的公眾號 (CoderBuff)


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 1.SOA SOA(Service-Oriented Architecture)面向服務架構,將應用程式不同功能單元(稱為服務)進行拆分,並通過這些服務之間定義良好的介面和契約聯繫起來。 SOA 不是特定的規範,是一種技術思想,一種理念,上圖為 SOA 架構的參考模型。 SOA 是一種粗粒度、松耦合 ...
  • 實驗三、數據挖掘之決策樹 一、實驗目的 1. 熟悉掌握決策樹的原理, 2. 熟練掌握決策樹的生成方法與過程 二、實驗工具 1. Anaconda 2. sklearn 3. pydotplus 三、實驗簡介 決策樹是一個非參數的監督式學習方法,主要用於分類和回歸。演算法的目標是通過推斷數據特征,學習決 ...
  • 實驗一、數據處理之Numpy 一、實驗目的 1. 瞭解numpy庫的基本功能 2. 掌握Numpy庫的對數組的操作與運算 二、實驗工具: 1. Anaconda 2. Numpy 三、Numpy簡介 Numpy 的英文全稱為 Numerical Python,指Python 面向數值計算的第三方庫。 ...
  • 前言 開心一刻 十年前,我:我交女票了,比我大兩歲。媽:不行!趕緊分! 八年前,我:我交女票了,個比我小兩歲,外地的。媽:你就不能讓我省點心? 五年前,我:我交女票了,市長的女兒。媽:別人還能看上你?分了吧! 今年,我挺著大肚子踏進家門。媽:閨女啊,你終於開竅了 ! 前情回顧 Spring拓展介面之 ...
  • 反向整數 給定一個 32 位有符號整數,將整數中的數字進行反轉,如果超出整數的最大或者最小範圍返回0 更多文章查看個人博客 "個人博客地址:反向整數" 方法一 利用StringBuilder的reverse方法,將數字轉換成字元反轉然後再轉換回整數 java public int reverseIn ...
  • N皇後 難度分類 困難 題目描述 n皇後問題研究的是如何將 n個皇後放置在 n×n 的棋盤上,並且使皇後彼此之間不能相互攻擊。 上圖為 8 皇後問題的一種解法。 給定一個整數 n,返回所有不同的 n 皇後問題的解決方案。 每一種解法包含一個明確的 n 皇後問題的棋子放置方案,該方案中 'Q' 和 ' ...
  • 老男孩python全棧第三期視頻老男孩python全棧第三期視頻老男孩python全棧第三期視頻老男孩python全棧第三期視頻 老男孩python全棧第三期視頻老男孩python全棧第三期視頻老男孩python全棧第三期視頻老男孩python全棧第三期視頻 所屬網站分類: 資源下載 > pytho ...
  • 劉老師說這塊很重要。。。。。 應該是很重要,大概看了一下,這裡面關於views中函數作用,大概看來可能就是相應請求,傳入數據和跳轉,基本功能上貌似這些框架都差不多吧(其實我並沒用過3個框架以上。。。。) 從功能上想,網站必然包含了許多實現具體功能和數據展示的頁面,而現在在做的就是構成這些。 那麼一個 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...