程式技術

簡介連結串列 (Linked List 或稱鏈結串列) 是串列 (List) 的一種，是一種常見的資料結構，利用這個資料結構也能進一步實作出其他的資料結構，例如堆疊 (Stack) 和佇列 (Queue) 等。 它的特性是能夠不使用連續的記憶體空間的情況下，能夠保有並使用一份連續的資料；相對來看，陣列則需要使用連續的記憶體空間。 他的的實作方式是每個節點除了記錄資料之外，還使用額外的指標指向下一個節點，將節點以此方式串連起來形成一個連結串列。 由以上的說明可以知道，使用連結串列的優點如下： 不需使用連續記憶體空間，不需事先指定串列大小。 能夠容易的修改指標，插入或移除節點。 但也有缺點如下： 使用額外的記憶體空間紀錄節點指標。 無法快速索引到某個節點，必須迭代搜索。 此資料結構可以實作的操作變化相當多，這裡實作以下幾種操作： getFirst：取得第一個節點。 getLast：取得最後一個節點。 addFirst：加入節點在最前面。 addLast：加入節點到最後。 addBefore：加入節點在某節點之前。 addAfter：加入節點在某節點之後。 removeFirst： ...

簡介佇列 (Queue) 中文也翻作隊列，顧名思義是一種像排隊一樣的概念，以生活中的情況為例如下圖 人們一個接一個的從隊伍後面加入排隊，而窗口的服務人員則從最前面的民眾一個接一個處理事務；當然現實生活是會有中途離開的人，而在程式世界裡面一般情況是不會有。 在這個模式下我們可以知道他是一種先進先出 (First-In-First-Out, FIFO) 的排程，而在此資料結構中至少會實作兩個操作： enqueue：將資料放入佇列尾端。(註：C++ 中用 push、Java 用 offer、也有 add 等不同的用字) dequeue：取出佇列前端之資料。(註：C++ 中用 pop、Java 用 poll、也有 remove 等不同的用字) 有時候也會多實作一些額外的操作以方便使用，例如： peek：看佇列前端的資料而不取出。(註：也有 front 等不同的用字) size：取得佇列的數目。 在實作上一般使用連結串列 (LinkedList) 來實作，使用陣列同樣可以達成，但較為複雜： 連結串列用指標將資料串起來，將新的東西不斷接在最後面，而取出時則移除最前面的東西即可。由於加入和移 ...

簡介堆疊 (Stack) 是資料結構的一種，是一種很基本常見的資料結構，首先利用現實生活中的例子來說明，如下圖 假設你有一些書把他們疊起來，一層一層的往上疊，所以每次新的書本會放在最上面，而當想要拿取書本的時候，也是從最上面的開始拿。當然現實生活會有可能從中間抽出書本，不過在程式中是不可以的，在程式世界下圖會更貼切。 所以他是一種後進先出 (Last-In-First-Out, LIFO) 的排程，而在此資料結構中至少會實作兩個操作： push：將資料放入堆疊頂端 pop：取出堆疊頂端之資料 有時候也會多實作一些額外的操作以方便使用，例如： peek：看堆疊頂端的資料而不取出。。(註：也有 top 等不同的用字) size：取得堆疊的數目。 在實作上一般可以使用陣列或連結串列 (LinkedList) 兩種方式來實作： 陣列堆疊建立時即建立一個陣列，並使用一個索引來記錄目前所指到的位址，新增或移除資料時，同步修改索引位址；如果有實作堆疊數目的功能時，這數字正好可做為此索引之用。優點是不用處理指標鏈結建立與移除，缺點是容量超過陣列大小時需要額外處理。 連結串列用指標將資料串起來， ...

簡介先來描述一下問題，這裡以下樓梯為例： 有一個人下樓梯，一次可以走一階或兩階，假設總共有N階樓梯，共有幾總走法？例如 N = 3，他可以走 1 + 1 + 1 、1 + 2 或 2 + 1 三種走法。 實做一個程式能夠輸入 N，能回傳共有幾總走法。 演算法這個問題直接使用 Bottom-Up 可能不容易思考，所以我們先利用遞迴的 Top-Down 思考邏輯來想這個問題，結果我們很容易就可以這樣想： 第N階的走法相當於在 N - 1 階的時候走一階過來，或者在 N - 2 階的時候走兩階過來；換句話說，就是第N階的走法等於N - 1階的走法加上N - 2階的走法。 所以我們就可以寫出遞迴式： 123F(N) = F(N - 1) + F(N - 2)F(1) = 1F(2) = 2 列出來的式子和費波那西數列 (Fibonacci) 還蠻像的，我們可以用不同的方式去實做解這問題，這問題較適合用動態規劃 (Dynamic Programming) 去解，直接用 Divide and Conquer 會重覆計算子問題。由於此問題和費波那西數列相當相似，這邊只簡單實做迭代法和動態規 ...

常見考題包含了基礎的演算法和資料結構，以及一些其他類型的程式實作考題。 演算法 分治法 (Divide and conquer) 二元搜索法 (Binary Search) 動態規劃 (Dynamic Programming) 費波那西數列 (Fibonacci) 上下樓梯問題 & (籃球) 得分問題 最大子序列 (Maximum Subarray) 排序演算法 (Sorting) 資料結構 連結串列 (LinkedList) 堆疊 (Stack) 佇列 (Queue) 其他考古題 不使用暫存變數交換兩個變數 (Swap two variables without using a temporary variable) 計算 1 + 2 + 3 + … + N 的總和 (Sum the Integers from 1 to N)可以思考不同的解法，例如： 使用遞迴 比 O(n) 時間複雜度更快的方法 計算1 * 2 + 2 * 3 + … + (N - 1) * N的總和 (Write a function to calculate 1 * 2 + 2 * 3 ...

題目未排序的 n 個連續整數中少了一個，試著找到最快的方法算出少了哪一個。例如：3, 6, 9, 7, 8, 4，連續整數範圍為 3-9，少了 5。How to find the missing integer in an array. 說明這個題目我們直覺得可以使用 Hashtable 的方式來判斷哪些數字出現過，但是這樣題目就太簡單了，所以一般會再有一個額外的限制：空間複雜度為 O(1)。 所以在不使用 Hashtable 的情況下，我們只能用數學的方式去求解，此等差數列正好為梯形公式：(上底 + 下底) * 高 / 2。 接著利用公式的理論總和減去實際總和就是缺少的數字，以上面的例子為例： 123(3 + 9) * 7 / 2 = 423 + 6 + 9 + 7 + 8 + 4 = 3742 - 37 = 5 解法1234567891011121314static int Find(int[] array){ int max = array[0]; int min = array[0]; int sum = 0; for (int i ...

題目在陣列中找出第二大的數字。Find second largest number in an array. 說明找最大的方法我們都會，很簡單地用一個變數去保存目前最大，那找第二大不就可以很簡單的用兩個變數去保存？反之找最小的想法也是一樣，就不在此贅述；這個方法時間複雜度為 O(N)。 解法使用 C# 1234567891011121314151617static int Find(int[] array){ int max = int.MinValue; int second = int.MinValue; for (int i = 0; i < array.Length; ++i) { int n = array[i]; if (n > max) { second = max; max = n; } else if (n > second) second = n; ...

題目計算 1 到 N 總和 (1 + 2 + 3 +…+ N)Sum the Integers from 1 to N. 說明這題看似很簡單，其實真的很簡單，只是可能會有不同要求。一般直覺會使用迴圈解，不過有時候也會要求遞迴解，考你簡單遞迴觀念。 迴圈解1234567int sum(int n){ int sum = 0; for (int i = 1; i <= n; ++i) sum += i; return sum;} 遞迴解123456int sum(int n){ if (n < 1) return 0; return n + sum(n - 1);} 數學解然後不論是迴圈還是遞迴解，都是 O(n) 的時間複雜度，有時候還會要求寫出O(1)的版本，這時候就要拿出數學的思考邏輯了，這沒記錯的話應該是高中數學的範圍。公式如下： 寫成程式 1234int sum(int n){ return n * (n + 1) / 2;} 推導參考維基百 ...

題目從兩個數字中找出最大的一個而不使用判斷描述。There are two int variables: a and b, don’t use “if”, “? :”, “switch” or other judgement statements, find out the biggest one of the two numbers. 說明max(a, b)… 正解，這題題目限制不能用 if、switch 或 ? : 的語法，但沒說不能用 math 的 max。不過這樣就太簡單了，所以我們假定不能用內建函式，而是自己實作這個 max()。 由於不能用判斷式，所以我們依照以下步驟來解： 用利用減法，大減小為正，小減大為負的特性來判斷大小。 至於如何判斷正負，我們看最左邊的 bit 是否為 1，利用上面的 shift 方式得到 sign_bit 為 0 則為正，1 為負。 接著我們利用陣列的索引來代替判斷式，0 為正，表示 a 大，所以 0 的位置放 a；反之 1 為負，b 大，1 的位置放 b。 解法1234567int max(int a, int b){ int ...

題目不使用暫存變數交換兩個變數。Swap two variables without using a temporary variable. 解法常見的方法有以下方式： 加減法123a = a + bb = a - ba = a - b 乘除法123a = a * bb = a / ba = a / b XOR 法123a = a ^ bb = a ^ ba = a ^ b 由於使用加減乘除有可能會有溢位 (overflow) 的問題，所以最好的方式是使用位元運算的 XOR。 說明加減乘除我們用數學角度來看很好理解，以加減為例： 1234假設 X、Y 和 Z 為未知數，a 和 b 為已知數，已知：X = a + bY = X - bZ = X - Y X 代入第二式 1Y = (a + b) - b = a 接著將 X 和 Y 代入 Z，可得 1Z = (a + b) - a = b 回頭和程式對比，可以發現 Y 相當於 b 變數，Z 相當於 a 變數。 使用位元運算並不好去理解為什麼這樣子做就可以達到交換的目的，首先要瞭解以下三點： XOR 定義：有且僅有一個為真，換句 ...