算法概覽

算法基礎(chǔ)

  • 遞歸算法的空間復(fù)雜度 = 每次遞歸的空間復(fù)雜度 * 遞歸深度
  • c/c++的內(nèi)存管理
    • 固定部分:
      • 代碼區(qū):存放二進(jìn)制代碼
      • 數(shù)據(jù)區(qū):全局變量,靜態(tài)變量和常量等等
    • 可以變部分
      • 棧區(qū):運(yùn)行方法的形參,局部變量,返回值,以及遞歸棧所需的空間.系統(tǒng)自動(dòng)分配和回收
      • 堆區(qū):動(dòng)態(tài)開辟的空間,存放new出來的對象在堆區(qū)中的真實(shí)數(shù)據(jù).需要手動(dòng)回收
  • 內(nèi)存對齊:
    • 平臺(tái)原因:為了同一個(gè)程序可以在多平臺(tái)運(yùn)行,需要內(nèi)存對齊
    • 硬件原因:經(jīng)過內(nèi)存對齊后,CPU訪問內(nèi)存的速度大大提升
  • 內(nèi)存對齊:一次尋址即可. 非內(nèi)存對齊:兩次尋址+一次合并操作
  • 數(shù)組是存放在連續(xù)內(nèi)存空間上的相同類型數(shù)據(jù)的集合,刪除/添加元素要移動(dòng)其他元素
  • 有序不唯一元素是二分法的前提條件
  • 算法特征:
    • 明確性:算法應(yīng)該清晰明確.每個(gè)步驟及其輸入/輸出明確并只能產(chǎn)生一種含義
    • 輸入:應(yīng)該有0個(gè)或以上定義明確的輸入
    • 輸出:應(yīng)該有1個(gè)或以上明確定義和匹配所需的輸出
    • 有限性:必須在有限步驟后終止
    • 可行性:在可用資源下是可行的
    • 獨(dú)立性:有分步知道,獨(dú)立于任何編程代碼
  • 貪婪算法:
  • 分治算法:
  • 動(dòng)態(tài)規(guī)劃:
  • 派生數(shù)據(jù)類型:List, Array, Stack, Queue
  • 基本操作:Traversing(遍歷),Searching,Insertion, Deletion, Sorting, Merging
  • 數(shù)組:
  • 鏈表:鏈表是一系列數(shù)據(jù)結(jié)構(gòu)，它們通過鏈接連接在一起。
    • 單向鏈表:
      • 鏈接:鏈表的每個(gè)鏈接都可以存儲(chǔ)稱為元素的數(shù)據(jù)。
      • 鏈表的每個(gè)鏈接都包含一個(gè)鏈接到名為 Next 的下一個(gè)鏈接。
      • 鏈表包含到第一個(gè)名為 First 的鏈接的連接鏈接。
    • 雙向鏈表(Doubly Linked List):
      • 比單向鏈表多一個(gè)Prev
      • 操作:插入開始,刪除開始,插入最后,刪除最后,后插入,根據(jù)key刪除,正向顯示,向后顯示
    • 循環(huán)鏈表:最后一個(gè)元素指向第一個(gè)元素
      • 操作:插入,刪除,顯示
  • 堆棧:堆棧是一種抽象數(shù)據(jù)類型 (ADT)，通常用于大多數(shù)編程語言。
    • 操作:push,pop, peek, isFull, isEmpty
  • 隊(duì)列:Queue 是一種抽象的數(shù)據(jù)結(jié)構(gòu),FIFO
    • 操作:enqueue, dequeue,peek,isfull, isempty
  • 查找:
    • 線性搜索是一種非常簡單的搜索算法
    • 二分查找(Binary search):必須對目標(biāo)數(shù)組進(jìn)行排序
      • 步驟:
        • 1.找出中位數(shù) mid
        • 2.目標(biāo)target 與mid比較
        • 3.對比成功或者查無此目標(biāo)
    • 插值搜索(Interpolation search):此搜索算法適用于所需值的探測位置
      • mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (T - A[Lo])
      • 步驟:步驟跟二分查找一樣
    • 哈希表是一種以關(guān)聯(lián)方式存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu),在哈希表中，數(shù)據(jù)以數(shù)組格式存儲(chǔ)，其中每個(gè)數(shù)據(jù)值都有自己唯一的索引值
      • 插入和搜索操作都非?？斓臄?shù)據(jù)結(jié)構(gòu)
      • 散列是一種將一系列鍵值轉(zhuǎn)換為數(shù)組索引范圍的技術(shù) hash:12 % 20 = 12
      • 通過查看下一個(gè)單元格來搜索數(shù)組中的下一個(gè)空位置，直到找到一個(gè)空單元格。這種技術(shù)稱為線性探測。
  • 排序算法:
    • 冒泡排序(Bubble sort) Ο(n^2)
    • 插入排序:(Insertion sort) Ο(n^2)
      • 1.每兩個(gè)比較一次
      • 2.每比較完一次都有對所有已比較過的都比較一次
    • 選擇排序:將列表分為兩部分，左端的已排序部分和右端的未排序部分 Ο(n^2)
      • 1.選擇最小的放在最左邊
    • 歸并排序:一種基于分治技術(shù)的排序技術(shù) Ο(n log n)
      • 1.分成單個(gè)元素
      • 2.對比合并
    • 希爾排序(Shell sort): 最好情況 O(n)
      • 如果較小的值在最右側(cè)并且必須移到最左側(cè)，則該算法避免了在插入排序的情況下的大移位
      • 1.h = h * 3 + 1
      • 2.將列表劃分為等間隔 h 的較小子列表
      • 3.使用插入排序?qū)@些子列表進(jìn)行排序
    • 快速排序是一種高效的排序算法，它基于將數(shù)據(jù)數(shù)組劃分為更小的數(shù)組
      • 步驟1:
        • 1.選擇最高的索引值pv
        • 2.取最左lo和最右hi不包括pv
        • 3.lo小于pv,右移; 右值大于pv,左移
        • 4.如果第三步都為FALSE,交換lo和hi
        • 5.如果lo>=hi,則交換lo和pv;重復(fù)
      • 步驟2:(遞歸)
        • 1.最右邊的索引值pv
        • 2.以pv分組
        • 3.遞歸快速排序左分區(qū)
        • 4.遞歸快速排序右分區(qū)
  • 圖:是一組對象的圖形表示，其中一些對象對通過鏈接連接(頂點(diǎn)(Vertex),邊(Edge),相鄰(Adjacency),路徑(path))
    • 深度優(yōu)先搜索(Depth First Search (DFS)):以深度運(yùn)動(dòng)方式遍歷圖，并使用堆棧來記住在任何迭代中出現(xiàn)死胡同時(shí)獲取下一個(gè)頂點(diǎn)以開始搜索。
      • 1.初始化棧
      • 2.第一個(gè)頂點(diǎn)壓入棧,第二個(gè)..回到第一個(gè)頂點(diǎn)停止
      • 3.出棧并檢查是否有未訪問節(jié)點(diǎn),有的話執(zhí)行步驟2
      • 重復(fù)123,直到全部出棧
    • 廣度優(yōu)先搜索 (BFS) 算法以廣度運(yùn)動(dòng)遍歷圖，并使用隊(duì)列記住在任何迭代中出現(xiàn)死胡同時(shí)獲取下一個(gè)頂點(diǎn)以開始搜索。
      • 1.初始化隊(duì)列
      • 2.標(biāo)記起始點(diǎn)S,S相鄰未訪問的點(diǎn)添加到隊(duì)列(FIFO)
      • 3.第一個(gè)入隊(duì)的點(diǎn),移出并檢查未訪問點(diǎn),將其入隊(duì),重復(fù)執(zhí)行步驟2
      • 4.重復(fù)123,直到全部出隊(duì)
  • 樹:(Path,Root,Parent,Child,Leaf,Subtree,Visiting,Traversing,Levels,Keys)
    • 遍歷樹:
      • 有序遍歷(In-order Traversal)
        • 遞歸左邊子樹(左下->中上->右下)
        • 根節(jié)點(diǎn)
        • 遞歸右邊子樹(左下->中上->右下)
      • 前序遍歷(Pre-order Traversal)
        • 根節(jié)點(diǎn)
        • 遞歸左邊子樹(中上->左下->右下)
        • 遞歸右邊子樹(中上->左下->右下)
      • 后序遍歷(Post-order Traversal)
        • 遞歸左邊子樹(左下->右下->中上)
        • 遞歸右邊邊子樹(左下->右下->中上)
        • 根節(jié)點(diǎn)
    • 二叉搜索樹（BST）:
      • 特性:
        • 左子樹的鍵值小于其父（根）節(jié)點(diǎn)的鍵值。
        • 右子樹的鍵值大于或等于其父（根）節(jié)點(diǎn)的鍵值。
      • 操作:
        • 遍歷樹
        • 查找
        • 插入
    • [平衡]AVL二叉樹(AVL Trees):BalanceFactor = height(left-sutree) ? height(right-sutree)
      • 左旋轉(zhuǎn):節(jié)點(diǎn)插入到右子樹,執(zhí)行左旋轉(zhuǎn)
        • 右下B與中上A旋轉(zhuǎn)調(diào)整為左下A和B,左下B與左下C旋轉(zhuǎn)調(diào)整為中上B和右下C
      • 右旋轉(zhuǎn):節(jié)點(diǎn)插入到左子樹,執(zhí)行右旋轉(zhuǎn)
        • 左下B與中上C旋轉(zhuǎn)調(diào)整為右下B和C,右下B與右下C旋轉(zhuǎn)調(diào)整為中上B和左下C
    • 生成樹是圖 G 的一個(gè)子集，它的所有頂點(diǎn)都被盡可能少的邊數(shù)覆蓋。因此，生成樹沒有環(huán)，也不能斷開。
      • 一個(gè)無向圖最多有n^(n-2)個(gè)生成樹
      • 從生成樹中刪除一條邊將使圖斷開連接，即生成樹是最小連接的。
      • 向生成樹添加一條邊將創(chuàng)建一個(gè)回路或環(huán)路，即生成樹最大程度地是非循環(huán)的。
      • 應(yīng)用:
        • 民用網(wǎng)絡(luò)規(guī)劃
        • 計(jì)算機(jī)網(wǎng)絡(luò)路由協(xié)議
        • 聚類分析
    • 堆是平衡二叉樹數(shù)據(jù)結(jié)構(gòu)的一種特殊情況，其中根節(jié)點(diǎn)鍵與其子節(jié)點(diǎn)進(jìn)行比較并相應(yīng)地排列
      • Min-Heap - 根節(jié)點(diǎn)的值小于或等于其任一子節(jié)點(diǎn)。
      • Max-Heap - 根節(jié)點(diǎn)的值大于或等于其任一子節(jié)點(diǎn)。
      • 最大堆構(gòu)建算法:
        • 1.在堆的末尾創(chuàng)建一個(gè)新節(jié)點(diǎn)。
        • 2.為節(jié)點(diǎn)分配新值。
        • 3.將此子節(jié)點(diǎn)的值與其父節(jié)點(diǎn)的值進(jìn)行比較。
        • 4.如果父值小于子值，則交換它們。
        • 5.重復(fù)第 3 步和第 4 步，直到 Heap 屬性成立。
      • 最小生成樹算法:
        • Prim 尋找最小成本生成樹的算法（如 Kruskal 算法）使用貪婪方法。 Prim 算法與最短路徑優(yōu)先算法有相似之處。
        • Kruskal 尋找最小成本生成樹的算法使用貪婪方法。該算法將圖視為森林，并將其擁有的每個(gè)節(jié)點(diǎn)視為一棵樹。一棵樹僅連接到另一個(gè)樹，并且僅當(dāng)它在所有可用選項(xiàng)中成本最低且不違反 MST 屬性。

數(shù)據(jù)結(jié)構(gòu)與操作

鏈表

  • 單向鏈表
    • 結(jié)構(gòu):
    struct node{
  int data;
  int key;
  struct node *next;
}
    • 操作:
      • while(ptr!=NULL){ptr = ptr->next}
      • insertFirst(){*link = (struct node*) malloc(sizeof(struct node));head = link;}
      • deleFirst(){head=head->next}
      • isEmpty(){return head==NULL}
      • length(){while(!current){length++;current=current->next}}
      • find(){while(current->key != key){return current}}
      • deleteByKey(){previous->next=current->next}
      • sort(){}
      • reverse(){}

算法步驟

  1. 二分法步驟
    1. 初始化 left=0,right=size-1,middle=left+(right-left)/2
    2. 不斷縮小left到right的范圍,找到target
  2. 雙指針1(移除元素):
    1. 初始化slowIndex=0,fastIndex=0
    2. 如果[fastIndex]!=target,[slowIndex++]=[fastIndex]
  3. 雙指針2(有序數(shù)組的平方):
    1. 初始化lowestIndex=0,highestIndex=size-1
  4. 滑動(dòng)窗口(長度最小數(shù)組之和>=target)
    1. 初始化slowIndex=0,fastIndex=0
    2. 如果slowIndex到fastIndex之和大于等于target,slowIndex前移
  5. 鏈表
    1. 刪除D節(jié)點(diǎn):C->next = D->next;free(D)
    2. 添加F節(jié)點(diǎn):C->next=F;F->next=D;
    3. 刪除鏈表元素
      1. 刪除頭結(jié)點(diǎn)
        1. 新建tmp=head;
        2. head = head->next;(向前移一位)
        3. delete tmp;
      2. 刪除非頭部節(jié)點(diǎn)
        1. 新建cur=head;
        2. 新建tmp = cur->next;(刪除非頭部+1.得出)
        3. cur->next=cur->next->next;
        4. delete tmp;
    4. 翻轉(zhuǎn)鏈表
      1. 定義一個(gè)cur=head,pre=null
      2. tmp=cur->next;cur->next = pre;
      3. pre=cur; cur = tmp;
    5. 鏈表相交
      1. 兩鏈表的end()對齊
      2. 找出curA==curB
    6. 環(huán)形鏈表
  6. 哈希表(Hash table):一般用來快速判斷一個(gè)元素是否出現(xiàn)在集合里
  7. 棧和隊(duì)列
  8. 二叉樹(binary tree)
    1. 滿二叉樹:深度為k,有2^k-1個(gè)節(jié)點(diǎn)的二叉樹
    2. 完全二叉樹:允許右葉子缺失的滿二叉樹
    3. 二叉樹遍歷:
      1. 中序遍歷:cur=root;cur.left==NULL ? stack.push(cur):cur=cur.left;
      2. 前序遍歷:stack.push(root);cur=stack.pop();stack.push(cur.left);stack.push(cur.right)
      3. 后序遍歷:用兩個(gè)棧
    4. 層序遍歷(圖論中的廣度優(yōu)先遍歷):
      1. que.push(root);node = que.front();que.pop();que.push(node.left);que.push(node.right);
  9. 回溯算法
    1. 理論基礎(chǔ)
      1. 組合,分割,子集,排列,棋盤問題,其他.
      2. 回溯算法是一種搜索方式.有遞歸就有回溯
    2. 組合
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容