其实解决复杂的算法问题时并没有什么良方高招但是下面的介绍的种方法还是有一定的实用性下面的方法你练习的越多就越能鑒别出用什么方法来解决问题
这种方法并不是彼此独立的也可能会交叉起来使用比如同一个问题可能会用到简化和一般化和套用常见方法两种方法
法举例法
说明举出个普通的例子看看是否能够发现其中的规则
例给出任意一个时间点计算出时针和分针之间的夹角
解法:首先从:这个例子出发通过画示意图观察时针和分针的角度我们会发现下面的规律
*以位置为起始点那么分针的角度则是 *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]的全排列然后再将最后一个字母插入到每一个可插入的位置
注意一般采用这样的构造法大多都会用到递归
法数据结构头脑风暴
说明方法看起来有点笨但是很实用过一遍数据结构然后看看哪个最适合解这个问题
例随机生成的数字一个一个存到可扩展的数组中如何跟蹤数组的中位数
数据结构头脑风暴
* 链表不太行因为链表在随机访问和排序上性能不好
* 数组可能但是你已经有一个数组了还要一直保持数组中的数字有序开销会比较大了我们暂时先不选它但可以作为备选项
* 二叉树有可能因为二叉树在排序方面有很好的表现如果二叉树是平衡的话那么根节点就是中位数但是注意如果数组中有偶数个元素时中位数应该是中间两个数的平均值而根节点不可能是两个数的结论可能可行待定
* 堆堆确在排序查找最大值/最小值有很好的性能如果你创建两个堆一个是最大堆一个最小堆一个堆堆顶记录数组较小一半的最大值另外一个堆顶记录较大值的最小值这样的结构下两个堆如果平衡的话那堆顶的数字就可能是需要的中位数了如果两个堆不平衡(堆的大小不一样)可以从元素多的堆中弹出堆顶的元素到另外一个堆保持平衡
只要你平时练习的越多那么对数据结构的选择就越有感觉
