其實解決復雜的算法問題時並沒有什麼良方高招但是下面的介紹的種方法還是有一定的實用性下面的方法你練習的越多就越能鑒別出用什麼方法來解決問題
這種方法並不是彼此獨立的也可能會交叉起來使用比如同一個問題可能會用到簡化和一般化和套用常見方法兩種方法
法舉例法
說明舉出個普通的例子看看是否能夠發現其中的規則
例給出任意一個時間點計算出時針和分針之間的夾角
解法:首先從:這個例子出發通過畫示意圖觀察時針和分針的角度我們會發現下面的規律
*以位置為起始點那麼分針的角度則是 *minute/
*以位置為起始點那麼時針的角度則是 *(hour%)/ + *(minutes/)*(/)
*那兩個指針之間的夾角是 (hour angle &#; minute angle)%
化簡上述式子就得到最後的公式: * hours &#; * minutes
法套用常見方法
說明如果出現的這個問題和之前用某個算法結果過的問題比較類似就可以嘗試改進原算法解決這個新問題
例一個經過排序的數組再做一次循環移動那麼數組中的數字可能是這樣的 那你如何找到數組中最小值呢？
相似的問題:
* 在數組中查找最小值
* 在數組中查找查找一個特殊的值(例如二分查找)
算法查找最值並不是什麼特別東西（你可以遍歷數組然後找到最小值即使提供了一些額外的信息比如:數組已近排序)剛才問題上額外信息似乎沒有什麼用但是二分查找好像比較有用因為給出的條件說數組已經排序過了可是還做了一次循環移動那麼這個數組的模式應該這樣的先是升序突然重置接著繼續升序那麼這個重置點就是最小值
比較第一個這個中間的元素(和)這個是升序的那麼這說明了這個重置點在之後的那一段(或者就是最小是因為數組沒有循環移動過)那麼我可以繼續采用這樣方法進行二分查找如果左邊小於右邊說明重置點不在這個范圍內如果左邊大於右邊則重置點在這個范圍內繼續進行二分查找
法簡化&一般化
說明通過改變一些條件（比如數據類型或者問題的規模）來簡化問題然後設計一個算法來解決這個簡化過的問題然後在問題一般化還原回來
例一份敲詐信可以用從雜志上剪下來的單詞拼湊出來給出一份敲詐信(字符串)你問是否能從給定的雜志中拼出來敲詐信
簡化將問題簡化成給定一份字符問是否能夠拼成一個單詞
算法對於這個簡化的問題我可以先創建一個數組用來給統計字符出現的次數首先我們計算每個字母在敲詐信中出現的個數然後在給出的字符串集合中是否有這麼多的字母
再一般化還原這個問題我們可以采用非常類似的方法這次我們采用的創建一個哈希表來映射每個單詞映出現的次數
法簡單構造法
說明從最基本的情況來解決問題(比如只有一個元素)然後再推導出有兩個元素的情況再利用一個元素和兩個元素的結論推導出三個元素的情況
例設計算法打印出一串字符的全排列假設所有的字符都不同
測試字符串abcdefg
a 全排列為 {a}
ab 全排列為 {abba}
abc 全排列為 ?
通過上面例子我們不能發現如果我們知道P(&#;ab&#;)我們就能生成P(abc)我只需要將新加入的字母&#;c&#;插入到每個可以插入位置即可如下
merge(c ab) &#;> cab acb abc
merge(c ba) &#;> cba bca bac
算法遞歸先截去字符串中的最後一個字母生成所有s[…n]的全排列然後再將最後一個字母插入到每一個可插入的位置
注意一般采用這樣的構造法大多都會用到遞歸
法數據結構頭腦風暴
說明方法看起來有點笨但是很實用過一遍數據結構然後看看哪個最適合解這個問題
例隨機生成的數字一個一個存到可擴展的數組中如何跟蹤數組的中位數
數據結構頭腦風暴
* 鏈表不太行因為鏈表在隨機訪問和排序上性能不好
* 數組可能但是你已經有一個數組了還要一直保持數組中的數字有序開銷會比較大了我們暫時先不選它但可以作為備選項
* 二叉樹有可能因為二叉樹在排序方面有很好的表現如果二叉樹是平衡的話那麼根節點就是中位數但是注意如果數組中有偶數個元素時中位數應該是中間兩個數的平均值而根節點不可能是兩個數的結論可能可行待定
* 堆堆確在排序查找最大值/最小值有很好的性能如果你創建兩個堆一個是最大堆一個最小堆一個堆堆頂記錄數組較小一半的最大值另外一個堆頂記錄較大值的最小值這樣的結構下兩個堆如果平衡的話那堆頂的數字就可能是需要的中位數了如果兩個堆不平衡(堆的大小不一樣)可以從元素多的堆中彈出堆頂的元素到另外一個堆保持平衡
只要你平時練習的越多那麼對數據結構的選擇就越有感覺
From:http://tw.wingwit.com/Article/program/sjjg/201405/30929.html
