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

• 線性表
  • 物理結(jié)構(gòu)
    • 數(shù)組
      • 需要連續(xù)的空間，查詢快，修改慢
      • 數(shù)組的長度定義了就不能改變了臣淤，所以如果插入長度大于了定義長度就需要擴容嗦锐，一般擴容為原來的兩倍嫌松，比較耗性能
    • 鏈表
      • 不需要連續(xù)的空間，修改快奕污，查詢較慢
      • 單鏈表萎羔，雙鏈表，循環(huán)鏈表
  • 邏輯結(jié)構(gòu)
    • 棧
      • 先進后出
    • 隊列
      • 先進先出
    • 棧和隊列都可以通過數(shù)組或者鏈表來實現(xiàn)
• 散列表
  • hash：基于數(shù)組實現(xiàn)的
    • K-V鍵值對結(jié)構(gòu)菊值，通過hash函數(shù)把K轉(zhuǎn)換為固定的散列值從而定位到需要存儲的數(shù)組下標的位置外驱，如果有多個值定位到同一下標，可以用鏈表的方式去存儲
    • hash沖突腻窒，不同的k經(jīng)過hash計算后得到同樣的散列值
      • 可能導致死循環(huán)
      • 解決辦法：
        • 開放尋址法：沖突了就向下尋找可以存儲的位置昵宇，效率不高，threadlocal就是使用這種算法
        • 鏈表法：新來的Entry映射到與之沖突的數(shù)組位置時儿子，只需要插入到對應的鏈表中即可
    • hash擴容：經(jīng)過多次插入操作瓦哎，散列表達到一定的飽和度，發(fā)生hash沖突的概率就會提高，沖突的多了會后續(xù)的操作效率會降低蒋譬，所以需要擴容割岛。
      • capacity和loadFactor
        • 當map.size >= capacity * loadFactor時就可以擴容了
        • 步驟
          • 創(chuàng)建新的數(shù)據(jù)，長度是原來的兩倍
          • 重新hash犯助，把原來所有元素重新放入新的位置
      • JDK8中增加了紅黑樹癣漆，鏈表長度超過
  • 位圖
• 樹
  • 二叉樹
    • 紅黑樹：自平衡的查找二叉樹，通過左旋剂买、右旋惠爽、顏色反轉(zhuǎn)實現(xiàn)
  • 多路樹
  • 堆
• 圖
  • 無向圖
  • 有向圖
  • 帶權(quán)圖

數(shù)組的下標為什么要從0開始呢？

• 因為數(shù)組的定位是a[i]_address=a[0]_address+i*4瞬哼，為了方便計算所以從0開始

算法：解決特定問題的思路

• 查找

  • 二分查找：適用于有序數(shù)組集合
    • 時間復雜度：O(logn)
    • 先找中間的數(shù)去判斷婚肆，如果小于目標數(shù)就從前半段中繼續(xù)找中間數(shù)，大于目標數(shù)就從后半段中繼續(xù)找中間數(shù)坐慰。直到找到為止

• 排序

  • 冒泡：前一個數(shù)和后一個數(shù)比較较性，前數(shù)大就前后交換
    • 時間復雜度：O(n^2)
  • 快速：每一輪挑選一個基準元素，并讓其他比它大的元素移動到數(shù)列一邊结胀，比它小的元素移動到數(shù)列的另一邊赞咙，并把基準元素和最后的mark元素交換
    • 時間復雜度：O(nlogn)
  • 堆排序：（還沒有理解）將待排序序列構(gòu)造成一個大頂堆，此時把跨，整個序列的最大值就是堆頂?shù)母?jié)點人弓。將其與末尾元素進行交換，此時末尾就為最大值着逐。然后將剩余n-1個元素重新構(gòu)造成一個堆崔赌，這樣會得到n個元素的次小值。如此反復執(zhí)行耸别，便能得到一個有序序列了
  • 時間復雜度：O(nlogn)
    • 時間復雜度：O(nlogn)
  • 計數(shù)排序：適合排序數(shù)據(jù)比較集中的數(shù)據(jù)健芭，比如是1-10的數(shù)排序。有這個數(shù)就放到對應下標的位置秀姐，元素+1慈迈。遍歷完后再遍歷數(shù)組，元素大于零的就輸出省有，下標就是數(shù)據(jù)
    • 時間復雜度：O(n+m)
  • 桶排序：按照數(shù)據(jù)范圍定義桶的數(shù)據(jù)痒留，根據(jù)定義的范圍把數(shù)據(jù)分別放入合適的桶內(nèi)，桶內(nèi)的數(shù)據(jù)再去排序
    • 時間復雜度：O(n)
  • <img src="C:\Users\Administrator\Desktop\md\階段十一_數(shù)據(jù)結(jié)構(gòu)和算法.assets\24465169-8e9751efadebf51c.png" style="zoom: 67%;" />

• 字符串匹配

  • BF算法：brute force 暴力算法
    • 時間復雜度：O(n*m)
  • RK算法：通過哈希算法對主串中的 n-m+1 個子串分別求哈希值蠢沿，然后逐個與模式串的哈希值比較大小伸头。如果某個子串的哈希值與模式串相等，那就說明對應的子串和模式串匹配了
    • 時間復雜度：O(n)
  • BM算法：（未掌握）通過壞字符規(guī)則去滑動子串
    • 時間復雜度：O(n/m)
  • trie數(shù)：用于從一組字符串中找某個字符串

• 算法思維

  • 貪心算法：每一步選中都采取在當前狀態(tài)下最好或最優(yōu)的選擇舷蟀，從而希望導致結(jié)果是全局最好或最優(yōu)的算法

    • 經(jīng)典問題：部分背包問題
    • 先把背包價值排序恤磷，先取最有價值的去填充面哼，沒滿再用次有價值的填充，以此類推直到填滿

• 分治算法：把原本的問題劃分為n個規(guī)模比較小的問題扫步，遞歸的解決子問題魔策，最后再合并，得到原問題的解

  • 回溯算法：實際上一個類似枚舉的深度優(yōu)先搜索嘗試過程河胎，主要是在搜索嘗試過程中尋找問題的解闯袒，當發(fā)現(xiàn)已不滿足求解條件時，就“回溯”返回（也就是遞歸返回）游岳，嘗試別的路徑搁吓。

    • 經(jīng)典問題：N皇后問題

• 動態(tài)規(guī)劃Dynamic Programming

  • 上個結(jié)果對后續(xù)結(jié)果有影響
  • 找到DP方程的規(guī)律

• 實戰(zhàn)
  • 環(huán)形鏈表問題
    • 如何判斷一個鏈表是環(huán)形的？
      • 一個指針正常速度遍歷吭历，另一個指針兩倍速度去遍歷，只要兩個指針相遇了那就是環(huán)形的擂橘。追擊問題晌区。
  • 1 - 0 背包問題，實際是動態(tài)規(guī)劃
    • 背包物品只有一個通贞，要么不取要么全取
    • 核心思想：
      • 不選這件物品
        • dp(i,j) = dp(i-1,j) 取上件物品的最優(yōu)解
      • 選這件物品
        • dp(i,j) = v[i] + dp(i-1, j-w[i])
      • 比較兩個dp(i,j)哪個是最大的