摘要: 稱球問題經常是面試中的常客，這里我用做了一個稱球的程序，主要的方法就是遞歸和掃描，貼出來請大家指正。
閱讀全文
摘要: 這是一個美國IT企業的面試題，原題大意是從一個文件中讀取出可連通的城市對，給出兩個城市，判斷是否可連通，如果可連通就輸出yes，不可連通就輸出no，否則給出命令行幫助。
其實判斷連接狀態不用遍歷圖，用蔓延法即可，具體做法就是從起始城市開始，依次改變其周邊連通城市的連通狀態，再從周邊開始向周邊連通城市蔓延，如果能蔓延到結束城市的周邊可連通城市，則說明兩個城市是完全可連通的。這種做法和多米諾骨牌效應很像。我姑且稱之為蔓延法。
閱讀全文
摘要: 回溯法有“通用的解題法“之稱。用它可以系統的搜索一個問題的所有解或任一解。會所法是一個既帶有系統性又帶有跳躍性的搜索算法，他在包含問題的所有解的解空間樹中，按照深度有限的策略，從根節點出發搜索解空間樹，算法搜索至解空間樹的任一節點時，總是先判斷該節點是否肯定不包含問題的解。如果肯定不包含，則跳過對該節點為根的子樹的系統搜索，逐層向其祖先節點回溯，否則進入該子樹，繼續按照深度優先的策略進行搜索。回溯法在用來求問題的任一接時，只要搜索到問題的一個解就可以結束。
這種深度優先的解的算法稱為回溯法，它適合于解一些組合數較大的問題。
用回溯法解n皇后問題時，可以用一棵完全n叉樹來表示其解空間。剪去不滿足行列和斜線攻擊的子樹后，剩下的就是問題的解答。
閱讀全文
摘要: 求兩字符串的公共子串，如abc123與123456的公共字串為123，基本想法是在長的字符串前面加上長度等于短字符串的空格前綴，然后拿短字符串與新字符串挨個匹配，匹配上的置上匹配字符，否則置上空格，這樣的新串就包含了匹配字串和空格，再劈分放入set即可，重復的元素會被set略過去。
閱讀全文