Tag-算法

 2017-08-31 14:12:13 |  0 Comments  |  算法

dungeon-game

https://leetcode.com/problems/dungeon-game ``` class Solution(object): def calculateMinimumHP(self, dungeon): """ :type dungeon: List[List[int]] :rtype: int """
 2017-07-16 20:15:10 |  0 Comments  |  算法

快速幂

# 概念 快速幂的目的就是做到快速求幂,对于$a^b$一般的做法是O(b)即O(n) 其实可以对幂拆分为二进制,比如 $a^{11}=a^{(2^0+2^1+2^3)}$ 设二进制数某位为$s_i$(i从0算起),二进制数的值为$2^i*s_i$。 所以11的二进制是1011,也是$2^0+2^1+2^3$的计算结果。 利用位运算可以自己实现一个快速幂函数`poww`,比如计算$a^{11}
 2016-11-19 14:31:42 |  0 Comments  |  算法

贪婪算法

# 基本思想 在每个阶段选择当前阶段认为最好的选择,不考虑将来的结果. 当算法终止时期待最后的结果是最优的,但有时候不会得到最优解而是次最优解. 贪心策略适用的前提是:局部最优策略能导致产生全局最优解。 实际上,**贪心算法适用的情况很少**。 # 解题步骤 1.建立数学模型来描述问题; 2.把求解的问题分成若干个子问题; 3.对每一子问题求解,得到子问题的局部最优解; 4.把子问题的局部最
 2016-11-19 14:30:41 |  0 Comments  |  算法

回溯算法

# 概念 回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。 回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。 许多复杂的,规模较大的问题都可
 2016-11-08 17:04:04 |  0 Comments  |  算法

动态规划

# 概述 动态规划中有两个词比较重要:"状态","状态转移方程". 个人理解"状态"就是一个变量,"状态转移方程"就是求这个变量的方程 # 动规问题特点 问题具有最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就称该问题具有**最优子结构**性质。 用已知的较小的子问题的最优解去求解较大问题的最优解. 这种说法的前提是问题与子问题有相同的形式 # 解题步骤 1.