《算法和資料結構》學習路線指引

大家好，又見面了，我是你們的朋友全棧君。

前言

  所謂活到老，學到老，雖然我感覺自己已經學了很多算法了，但是昨天熬夜整理完以後發現，自己還是個弟弟，實在忍不住了，打算把 算法學習路線 發出來，我把整個算法學習的階段總結成了五個步驟，分别為： 基礎文法學習（重要）、文法配套練習、資料結構、算法入門、算法進階。本文梳理了這五個大項的思維導圖，在下文會有詳細介紹。

  希望各位能夠找到自己的定位，通過自己的努力在算法這條路上越走越遠。

  剛開始切勿心浮氣躁，千萬不要給自己立 flag，說一定要把這麼多東西都學會。就算你的精力旺盛，日夜操勞，時間也是有限的。是以，首先是明确我們要做什麼，然後制定好一個合理的 目标 ，再一點一點将要學習的内容逐漸付諸實踐才是最重要的。

圖檔較大，文章中有拆解，需要原圖可以留言找我要哈

1、基礎文法學習

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

1）HelloWorld

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

2）讓自己産生興趣

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

3）目錄是精髓

• 然後，我們大緻看下你選擇的教程的前幾個章節，那些标題是否有你認知以外的名詞出現，比如以這個思維導圖為例。
• 如果你覺得這些名詞中有 3 / 4 以上是沒有什麼概念的。那麼，可能需要補齊一些數學、計算機方面的基礎知識。反之，我們就可以繼續下一步了。

4）習慣思考并愛上它

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

5）實踐是檢驗真理的唯一标準

• 光看教程肯定是不行的，寫代碼肯定還是要動手的，因為有些文法你看一遍，必定忘記。但是寫了幾遍，永世難忘。這或許就是寫代碼的魅力所在吧。
• 是以，記得多寫代碼實踐喲 (＾Ｕ＾)ノ~ＹＯ

6）堅持其實并沒有那麼難

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

7）适當給予正回報

• 然而，就算再有趣的教程，看多了都會乏味，這是人性決定的，你我都逃不了。能夠讓你堅持下去的隻有你自己，這時候，适當給予自己一些正回報就顯得尤為重要。比如，可以用一張表格将自己的學習計劃記錄下來，然後每天都去分析一下自己的資料。
• 當然，你也可以和我一樣，建立一個部落格，然後每天更新博文，就算沒有内容，也堅持日更，久而久之，你會發現，下筆如有神，鍵盤任我行！更新的内容，可以是自己的學習筆記，心路曆程 等等。
• 看着每天的粉絲量呈指數級增長，這是全網對你的認可，應該沒有什麼會是比這個更好的正回報了。
• 那麼，至此，不知道螢幕前的你感想如何，反正正在打字的我已經激情澎湃了。已經全然忘記這一章是要講C語言基礎的了！
• 介于篇幅，我會把C語言基礎的内容，放在這個專欄 《光天化日學C語言》 裡面去講，一天更新一篇，對啊，既然說了要堅持，要養成習慣，我當然也要做到啦~如果你學到了哪一章，可以在評論區評論 “打卡” ，也算是一種全網見證嘛！
• 我也很希望大家的學習速度能夠超越我的更新速度。

2、文法配套練習

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

• 從數學基礎、輸入輸出、資料類型、循環、數組、指針、函數、位運算、結構體、排序 等幾個方面，總結出的具有概括性的例題 100 道 《C語言入門100例》，目前還在更新中。
• 這裡可以列舉幾個例子：

1、例題1：交換變量的值

一、題目描述

  循環輸入，每輸入兩個數 a a a 和 b b b，交換兩者的值後輸出 a a a 和 b b b。當沒有任何輸入時，結束程式。

二、解題思路

難度：🔴⚪⚪⚪⚪

• 這個題的核心是考察如何交換兩個變量的值，不像 python，我們可以直接寫出下面這樣的代碼就實作了變量的交換。

a, b = b, a           

複制

• 在C語言裡，這個文法是錯誤的。
• 我們可以這麼了解，你有兩個杯子 a a a 和 b b b，兩個杯子裡都盛滿了水，現在想把兩個杯子裡的水交換一下，那麼第一個想到的方法是什麼？

當然是再找來一個臨時杯子：

  1）先把 a a a 杯子的水倒進這個臨時的杯子裡；

  2）再把 b b b 杯子的水倒進 a a a 杯子裡；

  3）最後把臨時杯子裡的水倒進 b b b 杯子；

• 這種就是臨時變量法，那麼當然，還有很多很多的方法，接下來就讓我們來見識一下吧。

三、代碼詳解

1、正确解法1：引入臨時變量

#include <stdio.h>
int main() { 
   
    int a, b, tmp;
	while (scanf("%d %d", &a, &b) != EOF) { 
   
	    tmp = a;   // (1)
	    a = b;     // (2)
	    b = tmp;   // (3)
	    printf("%d %d\n", a, b);
	}
	return 0;
}           

複制

• ( 1 ) (1) (1)

  tmp = a;

  表示把 a a a 杯子的水倒進這個臨時的杯子裡；
• ( 2 ) (2) (2)

  a = b;

  表示把 b b b 杯子的水倒進 a a a 杯子裡；
• ( 3 ) (3) (3)

  b = tmp;

  表示把臨時杯子裡的水倒進 b b b 杯子裡；
• 這三步，就實作了變量 a a a 和 b b b 的交換。

2、正确解法2：引入算術運算

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

複制

• ( 1 ) (1) (1)

  a = a + b;

  執行完畢後，現在最新的

  a

  的值變成原先的

  a + b

  的值；
• ( 2 ) (2) (2)

  b = a - b;

  執行完畢後，相當于

  b

  的值變成了

  a + b - b

  ，即原先

  a

  的值；
• ( 3 ) (3) (3)

  a = a - b;

  執行完畢後，相當于

  a

  的值變成了

  a + b - a

  ，即原先

  b

  的值；
• 進而實作了變量

  a

  和

  b

  的交換。

3、正确解法3：引入異或運算

• 首先，介紹一下C語言中的

  ^

  符号，代表的是異或。
• 二進制的異或，就是兩個數轉換成二進制表示後，按照位進行以下運算：

左操作數	右操作數	異或結果
1	1
1	1
1	1

• 也就是對于 0 和 1，相同的數異或為 0，不同的數異或為 1。
• 這樣就有了三個比較清晰的性質：
• 1）兩個相同的十進制數異或的結果一定位零。
• 2）任何一個數和 0 的異或結果一定是它本身。
• 3）異或運算滿足結合律和交換律。

#include <stdio.h>
int main() { 
   
    int a, b;
	while (scanf("%d %d", &a, &b) != EOF) { 
   
	    a = a ^ b;   // (1)
	    b = a ^ b;   // (2)
	    a = a ^ b;   // (3)
	    printf("%d %d\n", a, b);
	}
	return 0;
}           

複制

• 我們直接來看 ( 1 ) (1) (1) 和 ( 2 ) (2) (2) 這兩句話，相當于

  b

  等于

  a ^ b ^ b

  ，根據異或的幾個性質，我們知道，這時候的

  b

  的值已經變成原先

  a

  的值了。
• 而再來看最後一句話，相當于

  a

  等于

  a ^ b ^ a

  ，還是根據異或的幾個性質，這時候，

  a

  的值已經變成了原先

  b

  的值。
• 進而實作了變量

  a

  和

  b

  的交換。

4、正确解法4：奇淫技巧

• 當然，由于這個題目問的是交換變量後的輸出，是以它是沒辦法知道我程式中是否真的進行了交換，是以可以幹一些神奇的事情。比如這麼寫：

#include <stdio.h>
int main() { 
   
    int a, b;
	while (scanf("%d %d", &a, &b) != EOF) { 
   
	    printf("%d %d\n", b, a);
	}
	return 0;
}           

複制

• 你學廢了嗎 🤣？

2、例題2：整數溢出

一、題目描述

  先輸入一個 t ( t ≤ 100 ) t (t \le 100) t(t≤100)，然後輸入 t t t 組資料。每組輸入為 4 個正整數 a , b , c , d ( 0 ≤ a , b , c , d ≤ 2 62 ) a,b,c,d(0 \le a,b,c,d \le 2^{62}) a,b,c,d(0≤a,b,c,d≤262)，輸出 a + b + c + d a+b+c+d a+b+c+d 的值。

二、解題思路

難度：🔴🔴⚪⚪⚪

• 這個問題考察的是對補碼的了解。
• 仔細觀察題目給出的四個數的範圍： [ 0 , 2 62 ] [0, 2^{62}] [0,262]，這四個數加起來的和最大值為 2 64 2^{64} 264。而C語言中，

  long long

  的最大值為： 2 63 − 1 2^{63}-1 263−1，就算是

  unsigned long long

  ，最大值也隻有 2 64 − 1 2^{64}-1 264−1。
• 但是我們發現，隻有當四個數都取得最大值 2 62 2^{62} 262 時，結果才為 2 64 2^{64} 264，是以可以對這一種情況進行特殊判斷，具體參考代碼詳解。

三、代碼詳解

#include <stdio.h>
typedef unsigned long long ull;                           // (1)
const ull MAX = (((ull)1)<<62);                           // (2)

int main() { 
   
	int t;
	ull a, b, c, d;
	scanf("%d", &t);
	while (t--) { 
   
		scanf("%llu %llu %llu %llu", &a, &b, &c, &d);     // (3)
		if (a == MAX && b == MAX && c == MAX && d == MAX) // (4)
			printf("18446744073709551616\n");             // (5)
		else
			printf("%llu\n", a + b + c + d);              // (6)
	}
	return 0;
}           

複制

• ( 1 ) (1) (1) 由于這題資料量較大，所有資料都需要用64位無符号整型。

  ull

  作為

  unsigned long long

  的别名；
• ( 2 ) (2) (2) 用常量

  MAX

  表示 2 62 2^{62} 262，這裡采用左移運算符直接實作 2 2 2 是幂運算；

數學	C語言
2 n 2^n 2n	1<<n

• 需要注意的是，由于 1 是

  int

  類型，是以需要對 1 進行強制轉換。

  (ull)1

  等價于

  (unsigned long long)1

  ；
• ( 3 ) (3) (3)

  %llu

  是無符号64位整型的輸入方式；
• ( 4 ) (4) (4) 這裡是對所有數都等于最大值的特殊判斷，

  &&

  運算符的優先級低于

  ==

  ，是以這裡不加括号也沒事；
• ( 5 ) (5) (5) 由于 2 64 2^{64} 264 是無法用數字的形式輸出的，是以我們提前計算機算好以後，用字元串的形式進行輸出；
• ( 6 ) (6) (6) 其它情況都在 [ 0 , 2 64 − 1 ] [0, 2^{64}-1] [0,264−1] 範圍内，直接相加輸出即可。

3、資料結構

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

1、什麼是資料結構

• 你可能聽說過 數組、連結清單、隊列、棧、堆、二叉樹、圖，沒錯，這些都是資料結構，但是你要問我什麼是資料結構，我突然就一臉懵逼了。
• 如果一定要給出一個官方的解釋，那麼它就是：

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

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

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

• 很多同學搞不明白，資料結構與算法有哪些千絲萬縷的關系？甚至有些同學以為算法裡本身就包含了資料結構。
• 資料結構主要講解資料的組織形式，比如連結清單，堆，棧，隊列。
• 而算法，則注重的是思想，比如連結清單的元素怎麼插入、删除、查找？堆的元素怎麼彈出來的？棧為什麼是先進後出？隊列又為什麼是先進先出？
• 講得直白一點，資料結構是有實體的，算法是虛拟的；資料結構是物質上的，算法是精神上的。當然，物質和精神 缺一不可。

3、資料結構概覽

• 周末花了一個下午整理的思維導圖，資料結構：

• 資料結構相關入門可以參考以下文章：資料結構入門

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、盧卡斯定理、整數分塊、狄利克雷卷積、莫比烏斯反演、大數判素、大數因子分解、大步小步離散對數等等。

5）字元串比對

• 字元串比對學習路線比較明确。
• 先學習字首比對：字典樹。
• 然後可以簡單看一下回文串判定算法：Manacher。
• 以及經典的單字元串比對算法：KMP。
• 實際上平時最常用的還是 BM 算法，而ACM中基本不考察。
• 然後就是較為高階的 字首自動機、字尾數組、字尾樹、字尾自動機了。

• 關于 《畫解資料結構》學習路線 的内容到這裡就結束了。
• 如果還有不懂的問題，可以 「 想方設法 」找到作者的「 聯系方式 」 ，随時線上溝通。

釋出者：全棧程式員棧長，轉載請注明出處：https://javaforall.cn/127206.html原文連結：https://javaforall.cn