TopCoder Algorithm Tutorials - 基礎數學

摘錄自：Mathematics for TopCoders

底數(base)
把 b 進位的數字轉成十進位，可以用下面這段 code 實現。簡單來說就是利用 mod 10 取出各個位數的數字，乘上 b 的 x 次方(multiplier)得到真正的值加到結果(result)中。

public int toDecimal(int n, int b)
{
   int result = 0;
   int multiplier = 1;
      
   while(n>0)
   {
      result += n % 10 * multiplier;
      multiplier *= b;
      n /= 10;
   }
      
   return result;
}

(... 閱讀「TopCoder Algorithm Tutorials - 基礎數學」全文)

TopCoder Algorithm Tutorials - 解題規劃

摘錄自：Planning an Approach to a TopCoder Problem

Pattern Mining and the Wrong Mindset
當解過一定數量的問題後，會發現問題大致上可以分成幾類，於是就會陷入一種「從過去類似問題中找解法」的情況，試著拿過去解過的問題套到眼前的這個問題。這樣的情況並不是很好，特別是當眼前的問題是一個全新的問題時，很容易產生挫敗感。唯有不斷的複習、把每個問題都當成全新的經驗，才能持續進步。

Coding Kata
試試看下面這個練習，它能帶你體驗面對問題的各種可能情況。
嘗試挑一個未解過的問題，開始思考、尋找解法，把解法寫出來、通過測試之後，記下總共花了多少時間解這個問題。接著把程式碼清掉、再寫一次！第二次可能還是會犯些小錯誤，最後再次通過測試後，同樣記下第二次所花的時間，接著再把程式碼清除重新寫一次。第三次就會覺得順多了，完成後也同樣記錄時間。第一個時間表示當你心中沒有任何解法時，理解問題並思考、設計一個解所需要的時間；第二個時間，很意外地，通常只是少了理解問題的時間；而第三次才是真正的當你面對一個問題且能馬上想到解法時，所需要花的時間以及帶給你的感受，記住這個感受作為日後解題時的鼓勵！

(念到Atomic Code開始)

(... 閱讀「TopCoder Algorithm Tutorials - 解題規劃」全文)

TopCoder Algorithm Tutorials - 從題目線索中找解法

摘錄自：How To Find a Solution

從題目給的線索中猜測該用什麼演算法解題。

直覺模擬
這類題目單純地會給很多步驟，條件(複雜度)不會太高，也不會太低，通常是在測試你的 coding 速度，因此不用想太多，照著做就對了。

BFS (廣度優先搜尋)
這類題目通常要求找出從起點狀態到終點狀態「最少步驟(最低成本)」的解，並且狀態間的轉移成本通常是1。常見題目都是給一個 N*M 的表格，有些格子不能通過，求要到達目的地的最短路徑。
因為 BFS 複雜度多半是線性的，因次 N (或 M) 很大(到百萬)也沒關係。

Flood Fill
BFS 找所有解，而非最小那個。

暴力搜尋、backtracking
暴力搜尋的條件(複雜度)不能太高，因為它就是(必須/可以)嘗試所有可能、然後找最好的。backtracking 也是暴力搜尋的一種，通常用遞迴做，並且題目給的條件(複雜度)會很低，那就很適合。

(... 閱讀「TopCoder Algorithm Tutorials - 從題目線索中找解法」全文)

TopCoder Algorithm Tutorials - 序

摘錄自：The Importance of Algorithms

執行時間分析
當 N = 100 時，各種複雜度的估計執行時間：


最短路徑
即使是目前最好的演算法也不一定能有效解決真實生活中的問題。通常處理這些真實問題時，會加一些 heuristic 來幫助加快找到可行的答案。

字串比對
使用 DP 可以大大節省時間。DNA 比對、文章嫖竊判定...等都是字串比對的應用，「版本比對」則是把"一行"視為一個"字"，因此也是用字串比對的方式去看哪幾行有新增、修改、刪除。

(... 閱讀「TopCoder Algorithm Tutorials - 序」全文)