在陣列中找出第二大的數字
題目在陣列中找出第二大的數字。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 一文中所說，會重覆計算黃 ...
JavaScript 效能測試與最佳化
說明本文針對一些 JavaScript 效能相關的文章之理論進行實際的測試與驗證，結果有些符合預期，有些則意料之外。測試環境瀏覽器如下： Chrome：18.0.1025.168 m Firefox：12.0 Safari：5.1.5(7534.55.3) Opera：11.62 IE8、IE7 為使用 IE9 切換模式 變數存取JavaScript 變數存取具有以下特性： 使用變數時會透過作用域鏈 (Scope Chain) 自動判斷其所屬範圍，會從目前區域變數查找，逐漸往外圍查找。對變數存取屬性 (點符號.) 會進行查找而消耗時間。 根據以上原則，我們可以推論出一些增加效能的可能方法並實際測試： 使用區域變數，減少變數查找次數，包含作用域鏈與存取屬性，盡可能的使用區域變數。 Chrome Firefox Safari Opera IE9 IE8 IE7 存取區域變數 14.9 15.4 62.8 58.3 30 25 30 存取全域變數 13.8 17 73.9 74.1 43.7 11165.7 11208.6 存取變數屬性 15.3 12.9 80 ...
演算法 - 迭代法 (Iterative)
簡介Iterative Method 中文翻譯作迭代法或疊代法，而在數學領域和電腦程式領域的定義有些不同，數學領域的迭代法指的是無法使用公式一次求解，而須反覆運算求出近似解；而在電腦程式雖然亦有反覆運算的含義，但一般指的是迴圈解。 迭代法透過設定一個初始值開始反覆運算，最後求出答案，是算是一種 Bottom-Up 的模式，通常會和遞迴作比較，實作方式簡易區分如下： 迭代：使用迴圈實作。 遞迴：函式推疊呼叫。 基本上相同的演算法如果能夠直接使用迴圈，因為不透過函式堆疊，效能會比較好。相對於迭代，遞迴就算是一種 Top-Down 的模式。以階乘為範例： 遞迴123456function Factorial(n) if n == 1 return 1 end if return n * Factorial(n - 1)end function 遞迴的思考模式，求 n 階的時候當作 n - 1 階已知，相乘即是答案，n - 1 的如何求在 n 階的時候無須理會，就像上級要交由下屬去處理的 Top-Down 模式。 迭代1234567function Factorial(n) sum = ...
TopCoder Inv 2001 Semi A+B - MatchMaker
資訊 路徑：Tournament \ 1-16 \ 2 - Inv 2001 Semi A+B \ MatchMaker 分數：250 題目程式介面123456Class Name: MatchMakerMethod Name: getBestMatchesParamaters: String[], String, intReturns: String[]Method signature:String[] getBestMatches(String[] members, String currentUser, int sf); 說明線上交友網站需要透過程式來自動找出條件匹配的對象，會員會先輸入一些資料做為依據，當會員要求配對時，程式會回傳一個符合的對象清單，對象的符合項目必須大於等於設定的相似度 (similarity factor)。現在程式會先輸入會員資料、目前會員和相似度，會員資料如下格式： 1{名稱} {性別} {對象性別} {資料1} {資料2} ... 例如 1BETTY ...
台北旅遊景點 - 陽明山、擎天崗、冷水坑
拍攝時間：2012 年 4 月 8 日 今天一早就坐車來到陽明山，從劍潭捷運站坐小 15 的公車，在菁山小鎮這站下車，從旁邊的登山步道開始爬。 很久以前曾經也在裡這下車過，不過才走幾步就開始下大雨，就又下山了… 從步道往擎天崗，路程記得是 2 公里多 山旁邊有流水，上游有絹絲瀑布 這邊的步道相當好走 到了絹絲瀑布，可惜距離很遠，只能遠遠的拍照 這裡河流的石頭都是黃色的，但是可以看到沒碰到水的部分是正常的顏色 不是秋天不是楓，萬綠叢中一點紅 很快的就走到擎天崗了 迎面而來的是一群牛 擎天崗上的草原有很多牛正放出來吃草，同時也有很多遊客 大牛一直舔小牛，是幫他洗澡？ 拍著拍著，意外拍到奇怪的畫面 之後就到了遊客中心附近吃自備的午餐和休息，一堆人在等公車要下山。休息完後，我們用「走」的往冷水坑前進，結果走了好久的路… 不過總算是走到了，這裡雖然叫做冷水坑，但其實是溫泉，這時候有一堆人在泡。另外溫泉的水好像是每隔一段時間會放出來，不是一直流的。 在這裡有個管理員，好像叫劉先生吧？相當的熱情，還現場高歌一曲『小草』，看他笑容多燦爛 原本要往上走七星山，結果似乎開始下雨，就改往下去菁山吊橋 路 ...
