C++筆記 - HackMD

###### tags: `programing note` # C++筆記 ## 先備知識 ### 時間複雜度 * 根據定義，不計算常數倍數，所以我們只說 O(n)而不會說 O(3n)或 O(5n)。因為常數倍數不計，所以 log(n)不必指明底是 2 或 10。 * 兩個函數相加的 Big-O 等於比較大的函數。也就是說，若當 n 足夠大的時候，f(n)>g(n)，則 O(f(n)+g(n)) = O(f(n))。 * 如果某一段程式的複雜度是 O(f(n))而這段程式執行了 g(n)次，則複雜度為 O(f(n)*g(n))。 * 當要估算複雜度時，建議可以一秒 106~107的指令數量來估計，所以，假設執行一筆測資的時限為1 秒，我們可以得到下面常見的複雜度推估： | n | 超過 1 萬 | 數千 | 數百 | 20~25 | 10 | | ---- | --------- | ---- | ---- | ----- | --- | |複雜度 |O(n) or O(nlog(n))|O(n^2)| O(n^3) |O(2n) |O(n!)| ## 初始定義 ### 函式庫 <bit/stdc++.h> <math.h> <string.h> ### 使用命名空間 using namespace std; //namespace為命名空間，預設的 //所以可以建立自己的命名空間 ### 優化程式速度 ``` #pragma GCC optimize("O0")//不優化(預設) #pragma GCC optimize("O1")//優化一點 #pragma GCC optimize("O2")//優化更多 #pragma GCC optimize("O3")//O2優化再加上inline函式優化 #pragma GCC optimize("Os")//針對程式大小進行優化(程式最小) #pragma GCC optimize("Ofast")//O3加上一些快速但不安全的數學運算 ``` 引用資料：[HOW TO OPTIMIZE YOUR CODE IN C++](https://horikitacoding.blogspot.com/2019/07/how-to-optimize-your-code-in-c.html) ## 輸入輸出 //想輸入輸出 ``` cout << "hello, world" << endl; //cout輸出 //endl換行 cin>> name1>> name2; //cin輸入 //第二個>>為,的意思 ``` ### 限定位數 #### printf() output 幾位(int): ex兩位, printf("%02d") 幾位(float): ex兩位, printf("%0.2f", 0.222) #### cout<< cout << fixed << setprecision(10) << 1.0*a/b << '\n'; fixed表示的，是小數點以下的意思，因此，若沒有fixed，setprecision(10)代表的，其實是總共輸出十位數字設定一次輸出位數後，下一次便不需要重新設定如果想要重新設定，可以使用「cout.unsetf( ios::fixed );」關閉fixed，範例如下 ``` cout << fixed << setprecision(3) << 3.1234 << endl; cout.unsetf( ios::fixed ); cout << x << endl; ``` ### 優化 cin.tie(0); cout.tie(0); ios::sync_with_stdio(false); ## bitset bitset 表示一個固定大小的 N 位序列 #include <bitset> bitset<32> bs1(toBinary(number)); //<位數> //bs1第一個 //toBinary()為一個Function(可以省略) ## 動態陣列 ### set ``` set<變數類型> 變數名稱(myset) = {} //也可以=myset(array, array+n) 會將數值由小排到大, 並去掉重複的 myset.insert(value)插入數值(不可以重複,只會紀錄不一樣的) for (std::set<int>::iterator it = myset.begin(); it != myset.end(); it++) { std::cout << *it << " "; } //輸出set內的值//由小到大 for (std::set<int>::iterator it = myset.rbegin(); it != myset.rend(); it++) { std::cout << *it << " "; } set<int>::iterator it = myset.find(value); //find special value myset.erase(2);//delect某個元素 myset.count(value)//判斷是否有該元素 myset.empty()//判斷set內是否有東西 myset.size() ``` set 容器裡面元素的值是不可修改的 #### 補述: multiset(寫法像set)只是可以重複元素 map(寫法像set+pair)有兩個欄位//first&second ### vector vector<type> name //////name.? ?: ``` push_back：把元素加到尾巴，必要時會進行記憶體配置 pop_back：移除尾巴的元素 insert：插入元素 erase：移除某個位置元素, 也可以移除某一段範圍的元素 clear：清空容器裡所有元素 size：回傳目前長度 empty：回傳是否為空 [i]：隨機存取索引值為i的元素，跟陣列一樣索引值從 0 開始 at(i)：隨機存取索引值為i的元素，跟上面 operator[] 差異是 at(i) 會作邊界檢查，存取越界會拋出一個例外 reserve()：預先配置大小 //假設我想要預先配置好 5 個大小的話可以這樣寫 vector.reserve(5)//不指定元素 resize() : 預先配置大小 //可以指定元素(不指定的話都是0),ex. resize(5, 10);//長度5元素指定為10 capacity() : 容量(記憶體長度)//非實際長度 shrink_to_fit() : 釋放（free）那些尚未使用的空間 ``` *** 如果是指定複製傳統陣列的範圍的話，可以這樣寫， int n[5] = {1, 2, 3, 4, 5}; vector<int> v(n+2, n+4); // {3, 4} ## 搜尋法 ### 二分搜 ``` binary_search() : return boolean是否有收尋到 lower_bound() : return value // value>=目標 upper_bound() : return value // value>目標 ``` ### 山峰::三分搜其一:山峰::三分搜三分搜是將區間三等分，如果 1/3 的位置大於 2/3 的位置，可以丟掉左邊的 1/3；反之，如果 2/3 的位置較大，則可以丟棄右邊 1/3 的區間。如此每次可以將區間長度減少 1/3，在 O(log(n))次比較可以找到最低點 ### 山谷::差分二分搜只要以二分搜找到差分序列第一個大於等於 0 的位置就是 f 的最小值 ## 佇列queue 佇列//出入口不同，一進一出 ``` queue<int> Q; Q.push(t)放入數值 Q.empty()檢查數值 Q.pop()刪除數值 Q.front()前端值 Q.back()後端值 ``` ## 堆疊stack 堆疊//出入口相同 ``` stack<int> S; S.push(t)放入數值 S.empty()檢查數值 S.top()top值 S.pop()刪除top數值 ``` ## 雙向佇列deque 雙向佇列//兩個出入口 ``` deque<int> D; D.push_front/back放入前/後端 D.empty()檢查數值 D.pop_front/back()刪除前/後端 D.front()前端值 D.back()後端值 ``` ## 字元或字串 ### 字串宣告 1. string str("txt"); string str = "txt"; 2. string str1 = "test"; string str2(str1); 3. string str(7,'*'); 運用第三個宣告方式，可以一次打印指定數量字元 ### 字串長度呼叫 `int length = k.size();` ### 轉換字元或字串字串一定要用 string 變數名稱不可以用char a[n]來替換 `int x = stoi(放入字串) //將字串轉換成數字` ### 判斷字元或字串判斷字元或字串 //括號中放要判斷的東西 ``` isalnum() 如果是字母或數字，返回true isalpha() 如果是字母，返回true isdigit() 如果是數字，返回true islower() 如果是小寫字母，返回true ispunct() 如果是標點符號，返回true isspace() 如果是空白字符，包括空格、進紙、換行符、回車、製表符等，返回true isupper() 如果是大寫字符，返回true tolower() 如果是大寫字符，返回其小寫 toupper() 如果是小寫字符，返回其大寫 isxdigit() 如果是16進制數，返回true，如0-9、a-f、A-F iscntrl() 如果是控制字符，返回true isgraph() 如果是除空格以外的打印字符，返回true isprint() 如果是打印字符，返回true ``` ## struct 結構體適合建構多維陣列 ex. 三維陣列 ``` struct point{ int x, y, z; }; ``` 此結構體的point代表的是你自己建構的一種資料型態建立point這種變數的方法 ``` point p; ``` p為變數名稱 ## 串列鏈結(Linked list) * 串列是一個很重要的資料結構，顧名思義，他是將資料以鏈結的方式串成一列。他最重要的運用場合是當資料無法依序儲存在連續空間的時候 * 雙向的串列我們會儲存每一個資料的前一筆與下一筆鏈結，單向的只存下一筆 * 在陣列中構造所需的鏈結串列，用陣列的索引(index) * 左邊的 next 改成 i 的 next，把右邊的 pre 改成 i 的 pre，這樣在串列中沿著鏈結追蹤時就再也找不到 i 了，也就相當於從串列中移除了 ## 貪心演算法 ## 其他變換變數類型==> (類型)value 絕對值=> abs(value) //#include <math.h> 陣列宣告數值 int number[10] = {0}; ## 參考資料 [從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/) [大數運算](https://hackmd.io/@CLKO/r1KtmuMdf?type=view)