本文已收錄于專欄 💜《夜深人靜寫演算法》💜

前言

??看到太多爆肝熬夜整合的內容，又是幾萬字，又是爆肝，我也來試試看能不能扛得住，試完后發現，果然還是扛不住啊，但是既然整理完了，那就把我的 演算法學習路線 發出來吧，我把整個演算法學習的階段總結成了五個步驟，分別為： 「基礎語法」、 「語法練習」、 「資料結構」、 「演算法入門」、 「演算法進階」，本文梳理了這五個大項的思維導圖，在下文會有詳細介紹，
??希望各位能夠找到自己的定位，通過自己的努力在演算法這條路上越走越遠，
??剛開始切勿心浮氣躁，說一定要把這么多東西都學會，就算你的精力旺盛，日夜操勞，時間也是有限的，所以，首先是明確我們要做什么，然后制定好一個合理的 「目標」 ，然后再將目標進行逐漸拆解，再一點一點將要學習的內容逐步付諸實踐才是最重要的，

點擊我跳轉末尾 獲取 粉絲專屬 《演算法和資料結構》原始碼，

文章目錄

前言
1、基礎語法
- 1）第一個程式
- 2）熱愛編程
- 3）制定目錄
- 4）勤于思考
- 5）事必躬親
- 6）堅持到底
- 7）正反饋
- 8）儀式感
2、語法練習
- 1、例題1：整除判定
- - 一、題目描述
  - 二、解題思路
  - 三、代碼詳解
  - - 1、if else 陳述句
    - 2、條件運算子
- 2、例題2：最大的數
- - 一、題目描述
  - 二、解題思路
  - 三、代碼詳解
3、資料結構
- 1、什么是資料結構
- 2、資料結構和演算法的關系
- 3、資料結構概覽
- - 1）順序表
  - 2）鏈表
  - 3）堆疊
  - 4）佇列
  - 5）雙端佇列
  - 6）哈希表
  - 7）樹
  - 8）二叉樹
  - 9）二叉搜索樹
  - 10）堆
  - 11）AVL樹
  - 12）線段樹
  - 13）字典樹
  - 14）霍夫曼樹
  - 15）并查集
  - 16）圖
  - 17）二分匹配
  - 18）最短路
  - 19）最小生成樹
  - 20）強連通
4、演算法入門
5、演算法進階
- 1）圖論
- - 1、搜索概覽
  - 2、深度優先搜索
  - 3、記憶化搜索
  - 4、廣度優先搜索
- 2）動態規劃
- - 1、1D/1D
  - 2、2D/0D
  - 3、2D/1D
  - 4、2D/2D
- 3）計算幾何
- - 1、double 代替 float
  - 2、浮點數判定
  - 3、負零判定
  - 4、避免三角函式、對數、開方、除法等
  - 5、系統性的學習
- 4）數論
- - 1、數論入門
  - 2、數論四大定理
  - 3、數論進階
粉絲專屬福利

1、基礎語法

??演算法是以編程語言為基礎的，所以選擇一門編程語言來學習是必須的，因為作者本身是C/C++技術堆疊的，所以就拿C語言來舉例子吧，如果是 Java、Python 技術堆疊，可以跳過 C語言相關的內容，這一小節，先給出學習路線圖，然后我再來講，每部分應該如何去學，

1）第一個程式

??無論是 Java、Python、C/C++，想要上手一門語言，第一步一定是 HelloWorld，先不要急著去配環境，如果環境配了幾個小時，可能一開始的雄心壯志就被配環境的程序消磨殆盡，更加不要談日后的豐功偉業了，來看第一個 C 語言程式：

#include <stdio.h>               // (1)
int main()                       // (2)
{
   /* 我的第一個 C 程式 */       // (3)
   printf("Hello, World! \n");   // (4)
   return 0;                     // (5)
}

這段代碼只做了一件事情，就是向螢屏上輸出一行字：Hello, World!，
( 1 ) (1) (1) stdio.h是一個頭檔案 (標準輸入輸出頭檔案) , #include是一個預處理命令，用來引入頭檔案，當編譯器遇到 printf()函式時，如果沒有找到 stdio.h頭檔案，就會發生編譯錯誤，
( 2 ) (2) (2) main()作為這個程式的入口函式，代碼都是從這個函式開始執行的，
( 3 ) (3) (3) 被/*和*/包圍起來的代表注釋，是給人看到，不進行代碼的決議和執行，
( 4 ) (4) (4) printf代表將內容輸出到控制臺上，其中\n代表換行符，
( 5 ) (5) (5) 作為函式的回傳值，

2）熱愛編程

??所以，我們需要讓這件事情從一開始就變得有趣，這樣才能堅持下去，比如找一個相對較為有趣的教程，這里我會推薦這個：《光天化日學C語言》，聽名字就比較搞笑，可能作者本身也不是什么正經人，哈哈哈！雖然不能作為一個嚴謹的教程去學，起碼可以對搞笑的內容先產生興趣，從而對于語言本身有學習下去的動力，
??剛才提到的這個系列，可以先收藏起來，回頭再去看，它講述的是 對白式 的 C語言教學，從最簡單的輸出 HelloWorld 這個字串開始講起，逐漸讓讀者產生對C語言的興趣，這個系列的作者是前 WorldFinal 退役選手，一直致力于 將困難的問題講明白 ，我看了他的大部分教程，基本都能一遍看懂，

3）制定目錄

??然后，我們大致看下你選擇的教程的前幾個章節，那些標題是否有你認知以外的名詞出現，比如以這個思維導圖為例，前幾個章節為：

1、第一個C語言程式
2、搭建本地環境
3、變數
4、標準輸出
5、標準輸入
6、進制轉換入門
7、ASCII字符
8、常量

??如果你覺得這些名詞中有五六個是沒有什么概念的，那么，可能需要補齊一些數學、計算機方面的基礎知識，反之，我們就可以繼續下一步了，

4）勤于思考

??只要對一件事情養成習慣以后，你就會發現，再難的事情，都只是一點一點積累的程序，重要的是，每天學習的程序一定要吃透，養成主動思考的好習慣，因為，越到后面肯定是越難的，如果前期不養成習慣，后面很可能心有余而力不足，
??就像刷題，一旦不會做就去找解題報告，最后就養成了看解題報告才會做題的習慣，當然這也是一種習慣，只不過不是一種好習慣罷了，

5）事必躬親

??光看教程肯定是不行的，寫代碼肯定還是要動手的，因為有些語法你看一遍，必定忘記，但是寫了幾遍，永世難忘，這或許就是寫代碼的魅力所在吧，所以，記得多寫代碼實踐，

6）堅持到底

??每天把教程上的內容，自己在鍵盤上敲一遍，堅持一天，兩天，三天，你會發現，第四天就變成了習慣，所以堅持就是今天做了這件事情，明天繼續做，

7）正反饋

??然而，就算再有趣的教程，看多了都會乏味，這是人性決定的，你我都逃不了，能夠讓你堅持下去的只有你自己，這時候，適當給予自己一些正反饋就顯得尤為重要，比如，可以用一張表格將自己的學習計劃記錄下來，然后每天都去分析一下自己的資料，
??當然，你也可以和我一樣，創建一個博客，然后每天更新博文，就算沒有內容，也堅持日更，久而久之，你會發現，下筆如有神，鍵盤任我行！更新的內容，可以是自己的學習筆記，心路歷程等等，
??看著每天的粉絲量呈指數級增長，這是全網對你的認可，應該沒有什么會是比這個更好的正反饋了，

8）儀式感

??那么，至此，不知道螢屏前的你感想如何，反正正在打字的我已經激情澎湃了，已經全然忘記這一章是要講C語言基礎的了！
??介于篇幅，我會把C語言基礎的內容，放在這個專欄《光天化日學C語言》里面去講，一天更新一篇，對啊，既然說了要堅持，要養成習慣，我當然也要做到啦~如果你學到了哪一章，可以在評論區評論 “打卡” ，也算是一種全網見證嘛！
??我也很希望大家的學習速度能夠超越我的更新速度，

2、語法練習

??學習的程序中，做題當然也是免不了的，還是應征那句話：實踐是檢驗真理的唯一標準，
??而這里的題庫，是我花了大量時間，搜羅了網上各大C語言教程里的例題，總結出來的思維導圖，可以先大致看一眼：

??從數學基礎、輸入輸出、資料型別、回圈、陣列、指標、函式、位運算、結構體、排序等幾個方面，總結出的具有概括性的例題 100 道《C語言入門100例》，

這里可以列舉幾個例子：

1、例題1：整除判定

一、題目描述

??先輸入一個 t t t，然后輸入 t t t 組資料，對于每組資料，輸入兩個整數 a a a 和 b b b，如果 a a a 能夠被 b b b 整除，則輸出 YES，否則輸出 NO，

二、解題思路

難度：🔴????
??首先，當 b b b 等于 0 時， a a a 是一定不能被 b b b 整除的；然后，就是看 a a a 除上 b b b 的余數是不是零了，這步運算在C語言中表示為a % b；

三、代碼詳解

1、if else 陳述句

#include <stdio.h>
int main() {
    int a, b, t;
    scanf("%d", &t);             // (1)
    while (t--) {                // (2)
        scanf("%d %d", &a, &b);
        if (b == 0 || a % b)     // (3)
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}

( 1 ) (1) (1) 輸入 t t t 組資料；
( 2 ) (2) (2) while(t--)等價于while(t-- != 0)，當 t = 0 t=0 t=0 的情況下，這個回圈就會結束，也就是說整個回圈會執行一開始輸入的那個t的次數；
( 3 ) (3) (3) 根據本題的題意，用邏輯運算子||（或）對兩種情況輸出 N O NO NO，一種是 b等于0，另一個中是 a % b不等于0；

2、條件運算子

#include <stdio.h>
int main() {
    int a, b, t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &a, &b);
        printf("%s\n", (b == 0 || a % b) ? "NO" : "YES"); // (1)
    }
    return 0;
}

( 1 ) (1) (1) 采用條件運算子?:來實作if else陳述句的功能；

2、例題2：最大的數

一、題目描述

??回圈輸入，每組資料先輸入 n ( n ≤ 10000 ) n(n \le 10000) n(n≤10000)，再輸入 n n n 個正整數 a i ( a i ≤ 10000 ) a_i(a_i \le 10000) ai?(ai?≤10000)，輸出其中最大的數，當沒有任何輸入時，程式結束，

二、解題思路

難度：🔴????
??這個問題的經典思路就是列舉問題，以第一個元素為初始最大值，然后不斷和第二個數、第三個數、…、第 n n n 個數進行比較，程序中將最大值存下來，最后輸出這個最大值即可，

三、代碼詳解

#include <stdio.h>
int max(int a, int b) {
    return a > b ? a : b;             // (1)
}
int main() {
    int n, a, i, maxv;
    while(scanf("%d", &n) != EOF) {
        for(i = 0; i < n; ++i) {
            scanf("%d", &a);
            if(i == 0) {              // (2)
                maxv = a;       
            }
            maxv = max(a, maxv);      // (3)
        }
        printf("%d\n", maxv);
    }
    return 0;
}

( 1 ) (1) (1) 首先，實作一個最大值函式：給定兩個數，求其中的大者，我們利用三目運算子來實作；
( 2 ) (2) (2) 對 n n n 個數迭代求大者，將最大值存盤在maxv中，當輸入第一個數的時候因為沒有比較，所以我們把第一個輸入的數直接賦值給它；
( 3 ) (3) (3) 然后對每個輸入的數a，和maxv比大小，迭代求最大值；

??由于這個專欄是付費專欄，可能對學生黨不是很友好，所以作者經過再三思考，打算放出 300 張 7 折優惠券，先到先得，只要拿這個圖片來找作者即可享受，僅限前 300 名，
??為了適當提高一定門檻，你至少需要學會如何下載圖片或者截圖并且發送到微信里 🤣，

在這里插入圖片描述

3、資料結構

??《C語言入門100例》上的例題，如果能理解前面 35 道，那基本C語言的學習就可以告一段落了，接下來就要開始我們的資料結構的學習了，

1、什么是資料結構

你可能聽說過陣列、鏈表、佇列、堆疊、堆、二叉樹、圖，沒錯，這些都是資料結構，但是你要問我什么是資料結構，我突然就一臉懵逼了，
如果一定要給出一個官方的解釋，那么它就是：

計算機存盤、組織資料的方式，相互之間存在一種或多種特定關系的資料元素的集合，通常情況下，精心選擇的資料結構可以帶來更高的運行或者存盤效率，往往同高效的檢索演算法和索引技術有關，

是不是還不如說它是堆，是堆疊，是佇列呢？
是這樣的，我們學習的程序中，跳過一些不必要的概念，能夠節省我們更多的時間，從而達到更好的效果，當你還在理解資料結構是什么的時候，可能人家已經知道了堆疊有哪些操作了，

2、資料結構和演算法的關系

很多同學搞不明白，資料結構與演算法有哪些千絲萬縷的關系？甚至有些同學以為演算法里本身就包含了資料結構，
資料結構主要講解資料的組織形式，比如鏈表，堆，堆疊，佇列，
而演算法，則注重的是思想，比如鏈表的元素怎么插入、洗掉、查找？堆的元素怎么彈出來的？堆疊為什么是先進后出？佇列又為什么是先進先出？
講得直白一點，資料結構是有物體的，演算法是虛擬的；資料結構是物質上的，演算法是精神上的，當然，物質和精神缺一不可，

3、資料結構概覽

第一章 線性表

1）順序表

《畫解資料結構》（1 - 1）- 順序表

2）鏈表

《畫解資料結構》（1 - 2）- 鏈表

3）堆疊

《畫解資料結構》（1 - 3）- 堆疊

4）佇列

《畫解資料結構》（1 - 4）- 佇列

在這里插入圖片描述

5）雙端佇列

《畫解資料結構》（1 - 5）- 雙端佇列

6）哈希表

《畫解資料結構》（1 - 6）- 哈希表

在這里插入圖片描述

7）樹

第二章 樹 （2-1）畫解樹

?? 更多內容請收看：畫解樹，

8）二叉樹

（2-2）畫解二叉樹

?? 為了增加閱讀體驗，更多內容請收看：畫解二叉樹，

9）二叉搜索樹

《畫解資料結構》（2 - 3）- 二叉搜索樹

10）堆

（2-4）畫解堆

?? 為了增加閱讀體驗，更多內容請收看：畫解堆，

11）AVL樹

（2-5）畫解AVL樹

?? 本文已超五萬字，為了增加閱讀體驗，更多內容請收看：畫解二叉平衡樹，

12）線段樹

（2-6）畫解線段樹

?? 為了增加閱讀體驗，更多內容請收看：畫解線段樹，

13）字典樹

（2-7）畫解字典樹

在這里插入圖片描述

?? 為了增加閱讀體驗，更多內容請收看：畫解字典樹，

14）霍夫曼樹

（2-8）畫解霍夫曼樹

在這里插入圖片描述

?? 為了增加閱讀體驗，更多內容請收看：畫解霍夫曼樹，

15）并查集

（2-9）畫解并查集

?? 為了增加閱讀體驗，更多內容請收看：畫解并查集，

16）圖

第三章 圖 （3-1）畫解圖

?? 本文已超五萬字，為了增加閱讀體驗，更多內容請收看：畫解圖，

17）二分匹配

（3-2）畫解二分匹配

?? 為了增加閱讀體驗，更多內容請收看：畫解二分匹配，

18）最短路

（3-3）畫解最短路

在這里插入圖片描述

?? 為了增加閱讀體驗，更多內容請收看：畫解最短路，

19）最小生成樹

（3-4）畫解最小生成樹

?? 為了增加閱讀體驗，更多內容請收看：畫解最小生成樹，

20）強連通

（3-5）畫解強連通

?? 為了增加閱讀體驗，更多內容請收看：畫解強連通，

4、演算法入門

演算法入門，其實就是要開始我們的刷題之旅了，先給出思維導圖，然后一一介紹入門十大演算法，

🌌《演算法入門指引》🌌

5、演算法進階

演算法進階這塊是我打算規劃自己未來十年去完成的一個專案，囊括了大學生ACM程式設計競賽、高中生的OI競賽、LeetCode 職場面試演算法的演算法全集，也就是之前網路上比較有名的《夜深人靜寫演算法》系列，這可以說是我自己對自己的一個要求和目標吧，
如果只是想進大廠，那么演算法入門已經足夠了，不需要再來看演算法進階了，當然如果對演算法有濃厚興趣，也歡迎和我一起打卡，由于內容較難，作業也比較忙，所以學的也比較慢，一周基本也只能更新一篇，

這個系列主要分為以下幾個大塊內容：
??1）圖論
??2）動態規劃
??3）計算幾何
??4）數論
??5）字串匹配
??6）高級資料結構（課本上學不到的）
??7）雜項演算法

先來看下思維導圖，然后我大致講一下每一類演算法各自的特點，以及學習方式：

在這里插入圖片描述

1）圖論

1、搜索概覽

圖論主要圍繞搜索演算法進行展開，搜索演算法的原理就是列舉，利用計算機的高性能，給出人類制定好的規則，列舉出所有可行的情況，找到可行解或者最優解，
比較常見的搜索演算法是深度優先搜索（又叫深度優先遍歷）和廣度優先搜索（又叫廣度優先遍歷或者寬度優先遍歷），各種圖論的演算法基本都是依靠這兩者進行展開的，

2、深度優先搜索

深度優先搜索一般用來求可行解，利用剪枝進行優化，在樹形結構的圖上用處較多；而廣度優先搜索一般用來求最優解，配合哈希表進行狀態空間的標記，從而避免重復狀態的計算；
原則上，天下萬物皆可搜，只是時間已惘然，搜索會有大量的重復狀態出現，這里的狀態和動態規劃的狀態是同一個概念，所以有時候很難分清到底是用搜索還是動態規劃，
但是，大體上還是有跡可循的，如果這個狀態不能映射到陣列被快取下來，那么大概率就是需要用搜索來求解的，
如圖所示，代表的是一個深度優先搜索的例子，紅色實箭頭表示搜索路徑，藍色虛箭頭表示回溯路徑，
紅色塊表示往下搜索，藍色塊表示往上回溯，遍歷序列為：

	0 -> 1 -> 3 -> 4 -> 5 -> 2 -> 6

同樣，搜索的例子還有：
計算的是利用遞回實作的 n n n 的階乘，

3、記憶化搜索

對于斐波那契函式的求解，如下所示：
f ( n ) = { 1 ( n = 0 ) 1 ( n = 1 ) f ( n ? 1 ) + f ( n ? 2 ) ( n > 2 ) f(n) = \begin{cases}1 & (n = 0) \\1 & (n = 1) \\f(n-1) + f(n-2) & (n > 2) \end{cases} f(n)=??????11f(n?1)+f(n?2)?(n=0)(n=1)(n>2)?
對于 f ( 5 ) f(5) f(5) 的求解，程式呼叫如下：
這個程序用到了很多重復狀態的搜索，我們需要將它優化，一般將一些狀態快取起來，
我們通過一個動圖來感受一下：
當第二次需要計算 f ( 2 ) f(2) f(2) 和 f ( 3 ) f(3) f(3) 時，由于結果已經計算出來并且存盤在 h [ 2 ] h[2] h[2] 和 h [ 3 ] h[3] h[3] 中，所以上面這段代碼的fib != inf運算式為真，直接回傳，不再需要往下遞回計算，這樣就把原本的 “遞回二叉樹” 轉換成了 “遞回鏈”，從而將原本指數級的演算法變成了多項式級別，
這就是記憶化搜索，像這種把狀態快取起來的方法，就是動態規劃的思想了，

4、廣度優先搜索

單向廣搜就是最簡化情況下的廣度優先搜索（Breadth First Search），以下簡稱為廣搜，游戲開發程序中用到的比較廣泛的 A* 尋路，就是廣搜的加強版，
我們通過一個動圖來對廣搜有一個初步的印象，

從圖中可以看出，廣搜的本質還是暴力列舉，即對于每個當前位置，列舉四個相鄰可以行走的方向進行不斷嘗試，直到找到目的地，有點像洪水爆發，從一個源頭開始逐漸蔓延開來，直到所有可達的區域都被洪水灌溉，所以我們也把這種演算法稱為 FloodFill，
那么，如何把它描述成程式的語言呢？這里需要用到一種資料結構 —— 佇列，
這時候，演算法和資料結構就完美結合了，

2）動態規劃

動態規劃演算法三要素：
??①所有不同的子問題組成的表；
??②解決問題的依賴關系可以看成是一個圖；
??③填充子問題的順序（即對②的圖進行拓撲排序，填充的程序稱為狀態轉移）；

如果子問題的數目為 O ( n t ) O(n^t) O(nt)，每個子問題需要用到 O ( n e ) O(n^e) O(ne) 個子問題的結果，那么我們稱它為 tD/eD 的問題，于是可以總結出四類常用的動態規劃方程：（下面會把opt作為取最優值的函式（一般取 m i n min min 或 m a x max max ）, w ( j , i ) w(j, i) w(j,i)為一個實函式，其它變數都可以在常數時間計算出來），

1、1D/1D

d [ i ] = o p t ( d [ j ] + w ( j , i ) ∣ 0 < = i < j ) d[i] = opt( d[j] + w(j, i) | 0 <= i < j ) d[i]=opt(d[j]+w(j,i)∣0<=i<j)
狀態轉移如圖四所示（黃色塊代表 d [ i ] d[i] d[i]，綠色塊代表 d [ j ] d[j] d[j]）：
這類狀態轉移方程一般出現在線性模型中，

2、2D/0D

d [ i ] [ j ] = o p t ( d [ i ? 1 ] [ j ] + x i , d [ i ] [ j ? 1 ] + y j , d [ i ? 1 ] [ j ? 1 ] + z i j ) d[i][j] = opt( d[i-1][j] + x_i, d[i][j-1] + y_j, d[i-1][j-1] + z_{ij} ) d[i][j]=opt(d[i?1][j]+xi?,d[i][j?1]+yj?,d[i?1][j?1]+zij?)
狀態轉移如圖四所示：
比較經典的問題是最長公共子序列、最小編輯距離，
有關最長公共子序列的問題，可以參考以下文章：夜深人靜寫演算法（二十一）- 最長公共子序列
有關最小編輯距離的問題，可以參考以下文章：夜深人靜寫演算法（二十二）- 最小編輯距離

3、2D/1D

d [ i ] [ j ] = w ( i , j ) + o p t ( d [ i ] [ k ? 1 ] + d [ k ] [ j ] ) d[i][j] = w(i, j) + opt( d[i][k-1] + d[k][j] ) d[i][j]=w(i,j)+opt(d[i][k?1]+d[k][j])
區間模型常用方程，如圖所示：
另外一種常用的 2D/1D 的方程為：
d [ i ] [ j ] = o p t ( d [ i ? 1 ] [ k ] + w ( i , j , k ) ∣ k < j ) d[i][j] = opt( d[i-1][k] + w(i, j, k) | k < j ) d[i][j]=opt(d[i?1][k]+w(i,j,k)∣k<j)
- 區間模型的詳細內容可以參考以下這篇文章：夜深人靜寫演算法（二十七）- 區間DP

4、2D/2D

d [ i ] [ j ] = o p t ( d [ i ′ ] [ j ′ ] + w ( i ′ , j ′ , i , j ) ∣ 0 < = i ′ < i , 0 < = j ′ < j ) d[i][j] = opt( d[i'][j'] + w(i', j', i, j) | 0 <= i' < i, 0 <= j' < j) d[i][j]=opt(d[i′][j′]+w(i′,j′,i,j)∣0<=i′<i,0<=j′<j)
如圖所示：
常見于二維的迷宮問題，由于復雜度比較大，所以一般配合資料結構優化，如線段樹、樹狀陣列等，
對于一個tD/eD 的動態規劃問題，在不經過任何優化的情況下，可以粗略得到一個時間復雜度是 O ( n t + e ) O(n^ {t+e}) O(nt+e)，空間復雜度是 O ( n t ) O(n^t) O(nt) 的演算法，大多數情況下空間復雜度是很容易優化的，難點在于時間復雜度，后續章節將詳細講解各種情況下的動態規劃優化演算法，

3）計算幾何

計算幾何的問題是代碼量最大的，它是計算機科學的一個分支，以往的決議幾何，是用代數的方法，建立坐標系去解決問題，但是很多時候需要付出一些代價，比如精度誤差，而計算幾何更多的是從幾何角度，用向量的方法來盡量減少精度誤差，例如：將除法轉化為乘法、避免三角函式等近似運算等等，
如果一個比賽中，有一道計算幾何的題，那么至少，它不會是一道水題，

1、double 代替 float

c++ 中 double 的精度高于 float，對精度要求較高的問題，務必采用 double；

2、浮點數判定

由于浮點數（小數）中是有無理數的，即無限不回圈小數，也就是小數點后的位數是無限的，在計算機存盤的時候不可能全部存下來，一定是近似的存盤的，所以浮點數一定是存在精度誤差的（實際上，就算是有理數，也是存在誤差的，這和計算機存盤機制有關，這里不再展開，有興趣可以參見我博客的文章：C++ 浮點數精度判定）；
兩個浮點數是否相等，可以采用兩數相減的絕對值小于某個精度來實作：

const double eps = 1e-8;
bool EQ(double a, double b) {
    return fabs(a - b) < eps;
}

并且可以用一個三值函式來確定某個數是零、大于零還是小于零：

int threeValue(double d) {
    if (fabs(d) < eps)
        return 0;
    return d > 0 ? 1 : -1;
}

3、負零判定

因為精度誤差的存在，所以在輸出的時候一定要注意，避免輸出 -0.00：

    double v = -0.0000000001;
    printf("%.2lf\n", v);

避免方法是先通過三值函式確定實際值是否為0，如果是0，則需要取完絕對值后再輸出：

    double v = -0.0000000001;
    if(threeValue(v) == 0) {
        v = fabs(v);
    }
    printf("%.2lf\n", v);

4、避免三角函式、對數、開方、除法等

c++ 三角函式運算方法采用的是 CORDIC演算法，一種利用迭代的方式進行求解的演算法，其中還用到了開方運算，所以實際的算力消耗還是很大的，在實際求解問題的程序中，能夠避免不用就盡量不用，
除法運算會帶來精度誤差，所以能夠轉換成乘法的也盡量轉換為乘法運算，

5、系統性的學習

基礎知識：點、向量、叉乘、點乘、旋轉、線段、線段判交、三角形面積；
進階知識：多邊形面積、凸多邊形判定、點在多邊形內判定；
相關演算法：二維凸包、三維凸包、旋轉卡殼、多邊形面積交、多邊形面積并、多邊形面積異或、多邊形和圓的面積交、半平面交、最小覆寫圓、最小包圍球、模擬退火，

學習計算幾何，最好是系統性的，刷題的程序中不斷提煉出自己的模板，

4）數論

刷題的時候遇到不會的數論題，真的是很揪心，從頭學起吧，內容實在是太多了，每個知識點都要證明吃透，不然下次遇到還是不會；不學吧，又不甘心，就是單純的想把這個題過了，真是進退兩難！
數論對一個人的數學思維要求較高，但是一般也是一些固定的模式，所以把模板整理出來很重要，
當然，數論也有簡單問題，一般先做一些入門題提升信心，

1、數論入門

主要是一些基本概念，諸如：
整除性、素數與合數、素數判定、素數篩選法、因數分解、算識訓本定理、因子個數、因子和、最大公約數 (GCD) 和最小公倍數 (LCM)、輾轉相除、同余、模運算、快速冪取模、回圈節；

2、數論四大定理

這四個定理學完，可以KO很多題：
歐拉定理、中國剩余定理、費馬小定理、威爾遜定理

3、數論進階

系統性的學習，基本也就這些內容了：
擴展歐幾里得、逆元、歐拉函式、同余方程組、擴展歐拉定理、RSA、盧卡斯定理、整數分塊、狄利克雷卷積、莫比烏斯反演、大數判素、大數因子分解、大步小步離散對數等等，

今天先講這么多吧，
如果還有不懂的問題，可以 「想方設法」找到作者的「聯系方式」 ，隨時線上溝通，

??相信看我文章的大多數都是「大學生」，能上大學的都是「精英」，那么我們自然要「精益求精」，如果你還是「大一」，那么太好了，你擁有大把時間，當然你可以選擇「刷劇」，然而，「學好演算法」，三年后的你自然「不能同日而語」，
??那么這里，我整理了「幾十個基礎演算法」 的分類，點擊開啟：

🌌《演算法入門指引》🌌
??如果鏈接被屏蔽，或者有權限問題，可以私聊作者解決，
??大致題集一覽：

??為了讓這件事情變得有趣，以及「照顧初學者」，目前題目只開放最簡單的演算法 「列舉系列」 （包括：線性列舉、雙指標、前綴和、二分列舉、三分列舉），當有一半成員刷完 「列舉系列」 的所有題以后，會開放下個章節，等這套題全部刷完，你還在群里，那么你就會成為「夜深人靜寫演算法」專家團 的一員，
??不要小看這個專家團，三年之后，你將會是別人 望塵莫及 的存在，如果要加入，可以聯系我，考慮到大家都是學生， 沒有「主要經濟來源」，在你成為神的路上，「不會索取任何」，

🔥讓天下沒有難學的演算法🔥
C語言免費動漫教程，和我一起打卡！ 🌞《光天化日學C語言》🌞
入門級C語言真題匯總 🧡《C語言入門100例》🧡
幾張動圖學會一種資料結構 🌳《畫解資料結構》🌳
組團學習，抱團生長 🌌《演算法入門指引》🌌
競賽選手金典圖文教程 💜《夜深人靜寫演算法》💜 ??這篇文章的主要目的是講解二叉搜索樹的一些基礎概念，以及和二叉搜索樹相關的一些經典演算法，但是實際學習程序還是需要看個人的毅力和堅持，下圖代表的是 LeetCode 經典的二叉搜索樹的題集，其中樹是很重要的一個章節，涉及了諸多演算法，希望可以供讀者參考和學習，

粉絲專屬福利

語言入門：《光天化日學C語言》(示例代碼)
語言訓練：《C語言入門100例》試用版
資料結構：《畫解資料結構》原始碼
演算法入門：《演算法入門》指引
演算法進階：《夜深人靜寫演算法》演算法模板

👇🏻 驗證碼 可通過搜索下方 公眾號 獲取👇🏻

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/304321.html

標籤：java

上一篇：面試結束后，被面試官在朋友圈吐槽了（心塞）

下一篇：阿里P7教你如何快速熟悉一個系統

《演算法和資料結構》總綱，五個階段，一個目標，堅持就是勝利，沖！ (建議自學)

前言

文章目錄

1、基礎語法

1）第一個程式

2）熱愛編程

3）制定目錄

4）勤于思考

5）事必躬親

6）堅持到底

7）正反饋

8）儀式感

2、語法練習

1、例題1：整除判定

一、題目描述

二、解題思路

三、代碼詳解

1、if else 陳述句

2、條件運算子

2、例題2：最大的數

一、題目描述

二、解題思路

三、代碼詳解

3、資料結構

1、什么是資料結構

2、資料結構和演算法的關系

3、資料結構概覽

1）順序表

2）鏈表

3）堆疊

4）佇列

5）雙端佇列

6）哈希表

7）樹

8）二叉樹

9）二叉搜索樹

10）堆

11）AVL樹

12）線段樹

13）字典樹

14）霍夫曼樹

15）并查集

16）圖

17）二分匹配

18）最短路

19）最小生成樹

20）強連通

4、演算法入門

5、演算法進階

1）圖論

1、搜索概覽

2、深度優先搜索

3、記憶化搜索

4、廣度優先搜索

2）動態規劃

1、1D/1D

2、2D/0D

3、2D/1D

4、2D/2D

3）計算幾何

1、double 代替 float

2、浮點數判定

3、負零判定

4、避免三角函式、對數、開方、除法等

5、系統性的學習

4）數論

1、數論入門

2、數論四大定理

3、數論進階

粉絲專屬福利