此题作为面试中经常考到的类型,涉及到我们熟悉的递归,动态规划,贪婪算法这三种,此文会介绍这三种解法.  递归我们先定义函数f(n)为把绳子剪成若干段之后的各段长度乘积的最大值.在剪第一刀的时候,我们会有n-1种可能的选择,也就是说剪出来的第一段绳子的长度可能为1,2,......n-1.因此就有了递归公式 f(n) = max(f(i)*f(n-i)),其中0<i<n.代码如下: #递归写法 class Solution: def cutRope(self, number): # write code here if number < 2: return 0 if numbe...

此题与<<矩阵中的路径>>那一题为同一类问题,方法是采用回溯法来解决,我同样参照剑指offer官方的解释进行了代码实现,思路可以看我<<矩阵中的路径>>的那一题,他们是很相似的哦!!!如果您看到我的代码有什么问题或者需要改进的请您指正哦!!!!! class Solution: def movingCount(self, threshold, rows, cols): # write code here if threshold < 0: return 0 visited = [0]*cols*rows result = self.movi...

此题采用回溯发来进行求解,在说之前我想告诉大家,如果大家看过之前别人提交的py版本的代码,会发现不能通过全部的测试用例,现在我根据剑指offer书中的思路写下如下py的代码,希望您批评指正!!! class Solution: def hasPath(self, matrix, rows, cols, path): # write code here if not matrix or not path : return False visited = [0] * len(matrix) result = '' length = 0 for row in range(rows): for col...

此题大家如有想到的方法就是直接进行顺序的查找,复杂度为O(n).但是我们看到题中是给出的有序的旋转数组,我们可以采用二分法来进行求解,其复杂度为O(logn).这里我们需要利用带有条件的二分法来进行求解: 第一步我们可以将这个旋转的数组看作是前后两个有序的子数组,然后设定我们的中间值 mid = (start + end) // 2. 第二步我们能够看到,当我们选取的中间值 mid 所对应的值大于 start 所对应的值时,说明此时 mid 还在第一有序的数组中,而我们所要求解的最小值是在第二个有序数组的第一个位置,此时也就是在 mid 的后面,我们就将 start 移到 mid 所在的位置....

解释：菲波那切数列本质 class Solution: def rectCover(self, number): # write code here if number == 0: return 0 if number == 1: return 1 if number == 2: return 2 fOne = 1 fTwo = 2 for i in range(3,number+1): fN = fTwo + fOne fOne = fTwo fTwo = fN return fN

解释：使用数学归纳法可以很容易的得出：  n=1时有1种跳法 n=2时有2种跳法 n=3时有4种跳法 n=4时有8种跳法  固总结出f(n) = 2**(n-1) class Solution: def jumpFloorII(self, number): # write code here return 2**(number-1)

解释：我们把n级台阶时的跳法看成n的函数，记为f(n)。当n>=2时，第一次跳的时候有两种不同的选择：  第一次跳1级，此时跳法的数目等于后面剩下的n-1级台阶的跳法数目，即为f(n-1); 第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目，即为f(n-2)。因此，n级台阶的不同跳法总数为f(n) = f(n-1) + f(n-2)  class Solution: def jumpFloor(self, number): # write code here #此题与菲波那切数列的本质一致 if number == 1: return 1 if number == 2: r...

class Solution: def Fibonacci(self, n): # write code here if n == 0: return 0 if n == 1: return 1 fOne = 1 fZero = 0 for i in range(2,n+1): fN = fOne + fZero fZero = fOne fOne = fN return fN

class Solution: def __init__(self): self.stack1 = [] self.stack2 = [] def push(self, node): # write code here self.stack1.append(node) def pop(self): # return xx if self.stack2: return self.stack2.pop() elif not self.stack1: return None else: while self.stack1: self.stack2.append(self.stack1.pop()) ...

class Solution: def GetNext(self, pNode): # write code here # 此节点有右子树 if pNode.right: temp = pNode.right while temp: result = temp temp = temp.left return result # 此节点没有右子树 while pNode: if pNode.next: if pNode.next.left == pNode: return pNode.next pNode = pNode.next else: return None

class Solution: # 返回构造的TreeNode根节点 def reConstructBinaryTree(self, pre, tin): # write code here if len(pre) == 1: head = TreeNode(pre[0]) head.left = None head.right = None return head head = TreeNode(pre[0]) temp1 = tin.index(pre[0]) length = len(tin[:temp1]) if temp1 == 0: head.left = None else: h...