新竹旅遊景點 - 靜心湖和新竹公園
拍攝時間：2012 年 7 月 1 日 這天用了下午的時間帶朋友去新竹的一些小景點逛逛，首先來到靜心湖，之前住在這附近住了一年都不知道這裡有個湖，藏身於園區附近的一個景點。 從金山街出發的話，可以從星巴克對面的小路過去，一直到新竹家扶中心旁邊就可以進入了。 靜心湖 進入靜心湖之後，我們先從仿古代庭院造景的地方穿過，來到蓮花池。 正值夏天，可以看到一些蓮花綻放。 也有很多蓮藕。 仿古代的庭院造景，不能看太仔細，不然就會穿幫(都不是木造)。 旁邊有一棟外觀看起來別致的建築，其實這是廁所。 穿過庭院之後，有個太極的雕像造景，有很多民眾會來這邊運動，不知道有沒有打太極拳就是了。 在湖的正中央有一個小島，有座橋可以通過去。 這座大廈相當的搶鏡，上次來還沒蓋好，現在好像完成了。 我們從這座橋走到了小島。 七月了，在這座小島上竟然還有櫻花？ 走近一看，原來是假的，用燈泡做成的櫻花，不知道晚上會不會亮。 新竹公園新竹公園這一帶集合了玻璃工藝博物館、假日花市、動物園和孔廟等等景點。 這裡也有一小片湖，可以從照片中的橋穿過。 這裡有不少的鳥類和水中生物棲息，一隻白鷺鷥停在灑水器上。 這裡也來過很多次 ...
上下樓梯問題 & (籃球) 得分問題
簡介先來描述一下問題，這裡以下樓梯為例： 有一個人下樓梯，一次可以走一階或兩階，假設總共有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)
題目計算 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 定義：有且僅有一個為真，換句 ...
演算法 - 費波那西數列 (Fibonacci)
簡介費波那西數列 (Fibonacci)，又稱費氏數列、黃金分割數列等很多譯名，由西方的數學家費波那西使用兔子問題來描述這個數列，以下引用 Wiki： 第一個月初有一對剛誕生的兔子 第二個月之後(第三個月初)牠們可以生育 每月每對可生育的兔子會誕生下一對新兔子 兔子永不死去 使用數學式來表達的話如下： 123F(0) = 0F(1) = 1F(n) = F(n-1) + F(n-2) 列出前20個數值 F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15 F16 F17 F18 F19 F20 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 演算法數學法解法有很多種，可以直接套數學公式，推導過程可參考 Wiki，公式如下： 以程式設計的角度來看，一般使用迭代法、Divide and Conquery 和動態規劃 (Dynamic Programming) 的方式來解。 迭代法由於每次新的問題的答案來自於前兩個問題，所以每次運 ...
演算法 - 動態規劃 (Dynamic Programming)
簡介Dynamic Programming 中文譯作動態規劃，動態規劃類似 Divide and Conquer，一個問題的答案來相依於子問題，常用來解決最佳解的問題。與 Divide and Conquer 不同的地方在於，動態規劃多使用了 memoization 的機制，將處理過的子問題答案記錄下來，避免重複計算，因此在子問題重疊的時候應該使用動態規劃；Divide and Conquer 通常使用遞迴 (Top-Down) 來處理，有時轉成迴圈 (Bottom-up) 來解並不容易，故使用動態規劃則可以解決重覆計算並保留遞迴思考的優點。 同樣拿費波那西數列 (Fibonacci) 為例子 使用 Divide and Conquer 的寫法如下： 12345678function Fibonacci(n) if n == 0 return 0 if n == 1 return 1 end if return Fibonacci(n - 1) + Fibonacci(n - 2)end function 如同之前在 Divide and conquer 一文中所說，會重覆計算黃 ...
