數(shù)據(jù)結(jié)構(gòu)靈魂拷問(wèn)

復(fù)雜度分析

什么是大O復(fù)雜度表示法？

T(n) = O(f(n))

T(n)表示代碼執(zhí)行的時(shí)間；n 表示數(shù)據(jù)規(guī)模的大??；f(n) 表示每行代碼執(zhí)行的次數(shù)總和。因?yàn)檫@是一個(gè)公式，所以用 f(n) 來(lái)表示。公式中的 O，表示代碼的執(zhí)行時(shí)間 T(n) 與 f(n) 表達(dá)式成正比。

  • 順序執(zhí)行：O(1)

  • 循環(huán)：O(n)

  • 雙重循環(huán)：O(n^2)

  • 循環(huán)中對(duì)循環(huán)次數(shù)條件進(jìn)行乘法計(jì)算的：O(logn)

       i=1;
   while (i <= n)  {
   i = i * 2;
   }

  • 雙重循環(huán)中，子循環(huán)對(duì)循環(huán)次數(shù)條件進(jìn)行乘法計(jì)算的：O(nlogn)

    歸并排序、快速排序

什么是最好、最壞、平均、均攤時(shí)間復(fù)雜度？

在循環(huán)體內(nèi)有判斷條件，某些情況下執(zhí)行，某些情況下不執(zhí)行。

最好時(shí)間復(fù)雜度：執(zhí)行次數(shù)最少的條件下的時(shí)間復(fù)雜度

最壞時(shí)間復(fù)雜度：執(zhí)行次數(shù)最多的條件下的時(shí)間復(fù)雜度。

平均時(shí)間復(fù)雜度：將執(zhí)行條件的每一種情況需要遍歷的次數(shù)乘上這種情況下發(fā)生的概率，也叫加權(quán)平均時(shí)間復(fù)雜度。

均攤時(shí)間復(fù)雜度：使用攤還分析方法，將某一次的執(zhí)行情況平攤到每一次的執(zhí)行中，總體下來(lái)，得到算法的執(zhí)行次數(shù)。比如某一特定情況下，執(zhí)行情況是O(n),其他情況都是O(1),那么平攤下來(lái)，算法時(shí)間復(fù)雜度就是O(1)

數(shù)組

如何優(yōu)化數(shù)組的插入和刪除操作？

一般情況下，插入和刪除會(huì)導(dǎo)致后續(xù)節(jié)點(diǎn)的移動(dòng)，導(dǎo)致復(fù)雜度為O(n),如何將其優(yōu)化為O(1)

  • 插入操作

    如果數(shù)組中存儲(chǔ)的數(shù)據(jù)并沒(méi)有任何規(guī)律，數(shù)組只是被當(dāng)作一個(gè)存儲(chǔ)數(shù)據(jù)的集合。

    如果要將某個(gè)數(shù)據(jù)插入到第 k 個(gè)位置，為了避免大規(guī)模的數(shù)據(jù)搬移，我們還有一個(gè)簡(jiǎn)單的辦法就是，直接將第 k 位的數(shù)據(jù)搬移到數(shù)組元素的最后，把新的元素直接放入第 k 個(gè)位置。

3f70b4ad9069ec568a2caaddc231b7dc.jpg

  • 刪除操作

    數(shù)組 a[10]中存儲(chǔ)了 8 個(gè)元素：a，b，c，d，e，f，g，h。現(xiàn)在，我們要依次刪除 a，b，c 三個(gè)元素。

    為了避免 d，e，f，g，h 這幾個(gè)數(shù)據(jù)會(huì)被搬移三次，我們可以先記錄下已經(jīng)刪除的數(shù)據(jù)。每次的刪除操作并不是真正地搬移數(shù)據(jù)，只是記錄數(shù)據(jù)已經(jīng)被刪除。當(dāng)數(shù)組沒(méi)有更多空間存儲(chǔ)數(shù)據(jù)時(shí)，我們?cè)儆|發(fā)執(zhí)行一次真正的刪除操作，這樣就大大減少了刪除操作導(dǎo)致的數(shù)據(jù)搬移。

b69b8c5dbf6248649ddab7d3e7cfd7e5.jpg

什么時(shí)候使用數(shù)組，什么時(shí)候使用容器(ArrayList)?

  1. Java ArrayList 無(wú)法存儲(chǔ)基本類(lèi)型，比如 int、long，需要封裝為 Integer、Long 類(lèi)，而 Autoboxing、Unboxing 則有一定的性能消耗，所以如果特別關(guān)注性能，或者希望使用基本類(lèi)型，就可以選用數(shù)組。
  2. 如果數(shù)據(jù)大小事先已知，并且對(duì)數(shù)據(jù)的操作非常簡(jiǎn)單，用不到 ArrayList 提供的大部分方法，也可以直接使用數(shù)組.
  3. 當(dāng)要表示多維數(shù)組時(shí)，用數(shù)組往往會(huì)更加直觀(guān)。比如 Object[][] array；而用容器的話(huà)則需要這樣定義：ArrayList <ArrayList<object>> array 。

對(duì)于業(yè)務(wù)開(kāi)發(fā)，直接使用容器就足夠了，省時(shí)省力。畢竟損耗一丟丟性能，完全不會(huì)影響到系統(tǒng)整體的性能。但如果你是做一些非常底層的開(kāi)發(fā)，比如開(kāi)發(fā)網(wǎng)絡(luò)框架，性能的優(yōu)化需要做到極致，這個(gè)時(shí)候數(shù)組就會(huì)優(yōu)于容器，成為首選。

為什么大多數(shù)編程語(yǔ)言數(shù)組從0開(kāi)始編號(hào)，而不是1？

程序訪(fǎng)問(wèn)數(shù)組中的元素，使用尋址訪(fǎng)問(wèn)，指針或引用指向的是數(shù)組中的首地址，通過(guò)計(jì)算尋址公式來(lái)得到第k個(gè)元素的地址。

如果從0編號(hào)：

a[k]_address = base_address + k * type_size

如果從1編號(hào)：

a[k]_address = base_address + (k-1) * type_size
  1. 從1編號(hào)，每次訪(fǎng)問(wèn)需要計(jì)算k-1，效率不如從0編號(hào)好
  2. C 語(yǔ)言設(shè)計(jì)者用 0 開(kāi)始計(jì)數(shù)數(shù)組下標(biāo)，之后的 Java、JavaScript 等高級(jí)語(yǔ)言都效仿了 C 語(yǔ)言，習(xí)慣如此

鏈表、隊(duì)列和棧

如何實(shí)現(xiàn)LRU緩存淘汰算法？

緩存的大小有限，當(dāng)緩存被用滿(mǎn)時(shí)，哪些數(shù)據(jù)應(yīng)該被清理出去，哪些數(shù)據(jù)應(yīng)該被保留？這就需要緩存淘汰策略來(lái)決定。常見(jiàn)的策略有三種：先進(jìn)先出策略 FIFO（First In，F(xiàn)irst Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used）

維護(hù)一個(gè)有序單鏈表，越靠近鏈表尾部的結(jié)點(diǎn)是越早之前訪(fǎng)問(wèn)的。當(dāng)有一個(gè)新的數(shù)據(jù)被訪(fǎng)問(wèn)時(shí)，我們從鏈表頭開(kāi)始順序遍歷鏈表。

  1. 如果此數(shù)據(jù)之前已經(jīng)被緩存在鏈表中了，我們遍歷得到這個(gè)數(shù)據(jù)對(duì)應(yīng)的結(jié)點(diǎn)，并將其從原來(lái)的位置刪除，然后再插入到鏈表的頭部。

  2. 如果此數(shù)據(jù)沒(méi)有在緩存鏈表中，又可以分為兩種情況：

    1. 如果此時(shí)緩存未滿(mǎn)，則將此結(jié)點(diǎn)直接插入到鏈表的頭部；
    2. 如果此時(shí)緩存已滿(mǎn)，則鏈表尾結(jié)點(diǎn)刪除，將新的數(shù)據(jù)結(jié)點(diǎn)插入鏈表的頭部。

如何實(shí)現(xiàn)瀏覽器的前進(jìn)和后退功能？

我們使用兩個(gè)棧，X和Y，我們把首次瀏覽的頁(yè)面依次壓入棧X，當(dāng)點(diǎn)擊后退時(shí)，再依次從棧X中出棧，并將出棧的數(shù)據(jù)依次放入棧Y中。當(dāng)我們點(diǎn)擊前進(jìn)按鈕時(shí)，我們依次從棧Y中取出數(shù)據(jù)，放入棧X中。如果點(diǎn)擊其它頁(yè)面時(shí)，將棧Y清空。

如何實(shí)現(xiàn)表達(dá)式求值？

比如3+5*8-6

使用兩個(gè)棧來(lái)實(shí)現(xiàn)，一個(gè)放數(shù)字，一個(gè)放運(yùn)算符

我們從左向右遍歷表達(dá)式，當(dāng)遇到數(shù)字，我們就直接壓入操作數(shù)棧；當(dāng)遇到運(yùn)算符，就與運(yùn)算符棧的棧頂元素進(jìn)行比較，如果比運(yùn)算符棧頂元素的優(yōu)先級(jí)低或者相同，從運(yùn)算符棧中取棧頂運(yùn)算符，從操作數(shù)棧的棧頂依次取兩個(gè)操作數(shù)，第一個(gè)在運(yùn)算符后，第二個(gè)在運(yùn)算符前，然后進(jìn)行計(jì)算，再把計(jì)算結(jié)果壓入操作數(shù)棧，繼續(xù)比較。

bc77c8d33375750f1700eb7778551600.jpg

如何實(shí)現(xiàn)括號(hào)匹配？

假設(shè)表達(dá)式中只包含三種括號(hào)，圓括號(hào) ()、方括號(hào)[]和花括號(hào){}，并且它們可以任意嵌套。比如，{[] ()[{}]}或[{()}([])]等都為合法格式，而{[}()]或[({)]為不合法的格式。那我現(xiàn)在給你一個(gè)包含三種括號(hào)的表達(dá)式字符串，如何檢查它是否合法呢

用棧來(lái)保存未匹配的左括號(hào)，從左到右依次掃描字符串，如果遇到左括號(hào)，入棧，如果遇到有括號(hào)，從棧頂取出一個(gè)元素進(jìn)行比較，如果能夠匹配，繼續(xù)掃描，直到結(jié)束。最后檢查棧是否為空，如果為空，則全部匹配，否則異常。

為什么函數(shù)調(diào)用要使用“?！眮?lái)保存臨時(shí)變量呢，用其它數(shù)據(jù)結(jié)構(gòu)不可以嗎？

函數(shù)調(diào)用中，變量的作用域很重要，先聲明的作用域更大，后聲明的更小，函數(shù)的調(diào)用結(jié)束，伴隨著出棧操作，變量的使用就結(jié)束了。

函數(shù)中，調(diào)用函數(shù)的關(guān)系滿(mǎn)足先進(jìn)后出，后進(jìn)先出原則，所以使用棧很合適。

循環(huán)隊(duì)列的判斷為滿(mǎn)的條件是什么？

(tail + 1) % n == head

3d81a44f8c42b3ceee55605f9aeedcec.jpg

public class CircularQueue {
  // 數(shù)組：items，數(shù)組大?。簄
  private String[] items;
  private int n = 0;
  // head表示隊(duì)頭下標(biāo)，tail表示隊(duì)尾下標(biāo)
  private int head = 0;
  private int tail = 0;

  // 申請(qǐng)一個(gè)大小為capacity的數(shù)組
  public CircularQueue(int capacity) {
    items = new String[capacity];
    n = capacity;
  }

  // 入隊(duì)
  public boolean enqueue(String item) {
    // 隊(duì)列滿(mǎn)了
    if ((tail + 1) % n == head) return false;
    items[tail] = item;
    tail = (tail + 1) % n;
    return true;
  }

  // 出隊(duì)
  public String dequeue() {
    // 如果head == tail 表示隊(duì)列為空
    if (head == tail) return null;
    String ret = items[head];
    head = (head + 1) % n;
    return ret;
  }
}

什么是阻塞隊(duì)列，什么是并發(fā)隊(duì)列？

  • 阻塞隊(duì)列：在隊(duì)列基礎(chǔ)上增加了阻塞操作。簡(jiǎn)單來(lái)說(shuō)，就是在隊(duì)列為空的時(shí)候，從隊(duì)頭取數(shù)據(jù)會(huì)被阻塞。因?yàn)榇藭r(shí)還沒(méi)有數(shù)據(jù)可取，直到隊(duì)列中有了數(shù)據(jù)才能返回；如果隊(duì)列已經(jīng)滿(mǎn)了，那么插入數(shù)據(jù)的操作就會(huì)被阻塞，直到隊(duì)列中有空閑位置后再插入數(shù)據(jù)，然后再返回。

    我們可以使用阻塞隊(duì)列，輕松實(shí)現(xiàn)一個(gè)“生產(chǎn)者 - 消費(fèi)者模型”?。?！

  • 并發(fā)隊(duì)列：線(xiàn)程安全的隊(duì)列叫做并發(fā)隊(duì)列。最簡(jiǎn)單直接的實(shí)現(xiàn)方式是直接在 enqueue()、dequeue() 方法上加鎖，但是鎖粒度大并發(fā)度會(huì)比較低，同一時(shí)刻僅允許一個(gè)存或者取操作。

    實(shí)際上，基于數(shù)組的循環(huán)隊(duì)列，利用 CAS 原子操作，可以實(shí)現(xiàn)非常高效的并發(fā)隊(duì)列。這也是循環(huán)隊(duì)列比鏈?zhǔn)疥?duì)列應(yīng)用更加廣泛的原因。

什么場(chǎng)景下會(huì)使用隊(duì)列？

  • 線(xiàn)程池的池結(jié)構(gòu)使用隊(duì)列來(lái)排隊(duì)請(qǐng)求。

  • 數(shù)據(jù)庫(kù)連接池，使用隊(duì)列連接數(shù)據(jù)庫(kù)操作。

  • 消息隊(duì)列使用隊(duì)列來(lái)處理消息的發(fā)送和消費(fèi)。

如何實(shí)現(xiàn)無(wú)鎖的并發(fā)隊(duì)列？

使用CAS實(shí)現(xiàn)無(wú)鎖隊(duì)列，在入隊(duì)前，獲取tail位置，入隊(duì)時(shí)比較tail是否發(fā)生變化，如果否，則允許入隊(duì)，反之，本次入隊(duì)失敗。出隊(duì)則是獲取head位置，進(jìn)行cas。

遞歸

使用遞歸算法的條件是什么？

  1. 一個(gè)A問(wèn)題可以被分解為不確定的子問(wèn)題B、C、D等
  2. 這個(gè)問(wèn)題與分解之后的子問(wèn)題，除了數(shù)據(jù)規(guī)模不同，求解思路完全一樣
  3. 存在遞歸終止條件

使用遞歸算法可能會(huì)產(chǎn)生什么問(wèn)題？

  • 堆棧溢出

函數(shù)調(diào)用會(huì)使用棧來(lái)保存臨時(shí)變量。每調(diào)用一個(gè)函數(shù)，都會(huì)將臨時(shí)變量封裝為棧幀壓入內(nèi)存棧，等函數(shù)執(zhí)行完成返回時(shí)，才出棧。系統(tǒng)棧或者虛擬機(jī)?？臻g一般都不大。如果遞歸求解的數(shù)據(jù)規(guī)模很大，調(diào)用層次很深，一直壓入棧，就會(huì)有堆棧溢出的風(fēng)險(xiǎn)。

  • 重復(fù)值計(jì)算

    在處理f(n) = f(n-1)+f(n-2) 的遞歸情況時(shí)，會(huì)出現(xiàn)以下情況

e7e778994e90265344f6ac9da39e01bf.jpg

從圖中，我們可以直觀(guān)地看到，想要計(jì)算 f(5)，需要先計(jì)算 f(4) 和 f(3)，而計(jì)算 f(4) 還需要計(jì)算 f(3)，因此，f(3) 就被計(jì)算了很多次，這就是重復(fù)計(jì)算問(wèn)題。為了避免重復(fù)計(jì)算，我們可以通過(guò)一個(gè)數(shù)據(jù)結(jié)構(gòu)（比如散列表）來(lái)保存已經(jīng)求解過(guò)的 f(k)。當(dāng)遞歸調(diào)用到 f(k) 時(shí)，先看下是否已經(jīng)求解過(guò)了。如果是，則直接從散列表中取值返回，不需要重復(fù)計(jì)算，這樣就能避免剛講的問(wèn)題了。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀(guān)點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

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