問題與以前莫個算法解決過的問題相似,此時就可以觸類旁通,嘗試改進原有算法來解決
此方法首先將問題簡單化,如改變數據類型、空間大小等,然後嘗試著將簡化後的問題解決。
為了降低問題的復雜度,很多時候都會將問題逐層分解,最後歸結為壹些簡單的問題,這就是遞歸法
將壹個難以直接解決的大問題,分割成壹些規模較小的相同問題,以便各個擊破,分而治之。分治法壹般包括以下三個步驟:
1)將問題的實例劃分為幾個較小的實例,最好最有相等的規模。
2)對這些較小的實例求解,而最常見的方法壹般是遞歸。
3)如歌有必要,合並這些較小問題的解,以得到原始問題的解。
壹般而言,時間復雜度越低的算法越高效。而更想達到時間復雜度的高效,很多時候就必須在空間上有所犧牲,用空間來換時間。而用空間換時間最有效的方法就是Hash法、大數組和位圖法。
在設計題目時,往往會有壹個載體,這個載體便是數據結構。如數組、鏈表、二叉樹和圖等,當窄體確定後,可用的算法自然而然就會顯現出來。可問題是很多時候並不確定這個載體是什麽,當無法確定這個載體時,壹般也就很難想到合適的方法了。
當遇到上面的問題時,可以采用最原始的思考問題的方式——輪詢法。常考的數據結構與算法壹***就幾種,如下圖
此種方法看似笨拙,卻很實用,只要對常見的數據結構與算法爛熟於心,壹點都沒有問題。