【剑指offer】连续子数组的最大和（python） python初始化整数的最大值和最小值 这是聪明法，这个sum的设置，想不到 # -*- coding:utf-8 -*- import sys class Solution: def FindGreatestSumOfSubArray(self, array): # write code here if not array: return 0 sum = 0 maxSum = -sys.maxint -1 for i in array: ...

【剑指offer】变态跳台阶（python） 动态规划，跳上n阶台阶可以从n-1跳1，也可以从n-2跳2，。。。f(n)=f(n-1)+f(n-2)+...+f(0)其实就是算了一个等比数列。 # -*- coding:utf-8 -*- class Solution: def jumpFloorII(self, number): # write code here dp = [1 for i in range(number)] for i in range(1,number): for j in range(0,...

【剑指offer】矩形覆盖（python） 覆盖n为1时，只有一种覆盖方法。覆盖n为2时，有两种覆盖方法。要覆盖2xn的大矩形，可以先覆盖2x1的矩形，再覆盖2x(n-1)的矩形；或者先覆盖2x(n-2)的矩形。而覆盖2x(n-1)的矩形和2x(n-2)的矩形可以看成子问题。递推公式就有了。 # -*- coding:utf-8 -*- class Solution: def rectCover(self, number): # write code here # base 是n=1和n=2 if number <= 2: retu...

【剑指offer】裴波那契数列（Python） 动态规划是“自下而上”求解，从最基础的base解到最终解。这里基础解就是第0项和第1项，第2项=第0项+第1项，从第2项开始往上。时间复杂度：O（n）空间复杂度：O（1） # -*- coding:utf-8 -*- class Solution: def Fibonacci(self, n): # write code here # 动规是从下往上的 if n <= 1: return n pre1 = 1 pre2 = 0 fib =...

【剑指offer】数组中的逆序对（python） 思路：先把数组分割成子数组，先统计出子数组内部的逆序对数目，然后统计出两个相邻子数组之间的逆序对数目。统计过程中，还需要对数组进行排序，以免重复统计。两个指针分别指向两个子数组的末尾，如果第一个子数组的数字大于第二个数组的数字，构成逆序对，并且逆序对数目等于第二个子数组中剩余数字个数，每一次比较都把较大数字从后往前复制到辅助数组中。 # -*- coding:utf-8 -*- class Solution: tmp = [] cnt = 0 def InversePairs(self, data): #...

【剑指offer】把数组排成最小的数（python） 1. 重写排序 使用匿名函数lambda和cmp函数： （cmp（x,y）如果x<y,则返回-1，如果x=y，则返回0，如果x>y,则返回1） sorted(a,lambda x,y:cmp(x,y) # 正序排列 sorted(a,lambda x,y:-cmp(x,y) # 倒序排列 这里比较字符串s1和s2的大小，定义为比较s1+s2和s2+s1的大小，如果s1+s2<s2+s2，应该s1在前。 compare = ...

python3才有语法 arr.copy()，python2里使用 arr[:] 复制 # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # #  # @param array int整型一维数组  # @return int整型一维数组 # class Solution:     def reOrderArray(self , array ):    &nbs...

【剑指offer】字符串的排列（python） 1. 数组转字符串字符串转数组，list(str)，直接通过list转换时是以每一个字符为分割的。2. 注意保证不重复3. 回溯注意局部状态 mark[i] = True s.append(chars[i]) self.backTravesal(chars, mark, s) s.pop(-1) mark[i] = False这里表示将当前字符的标志置为True，遍历其余字符，最后还需要将字符弹出，清除标志，进行下一次遍历。 # -*- coding:utf-8 -*- class Solution: ret = [] def P...

【剑指offer】机器人的运动范围（python） 回溯是DFS的特例，每次搜索需要设置本次搜索的局部状态，并在本次搜索结束后清除状态，这里就是 mark[r][c]=True，标记这里已经遍历了。和“矩阵中的路径”思路差不多，这个简单些。 # -*- coding:utf-8 -*- class Solution: next = [[0,1],[0,-1],[1,0],[-1,0]] rows = 0 cols = 0 count = 0 def movingCount(self, threshold, rows, cols): # w...

【剑指offer】矩阵中的路径（python） 1. str转换为list 在将str转化为list时，主要就是通过str的split()函数，split()参数为空时，默认以空格来做分割。 直接通过list转换时是以每一个字符为分割的。 2. python申明多维数组 list_three = [[0 for i in range(3)] for j in range(3)] 注意方括号 3. 回溯法 一种暴力搜索方法，在一次搜索结束时需要进行回退，将这一次搜索过程中设置的状态清楚，再开始一次新的搜索过程。 ...

【剑指offer】数值的整数次方（python） 分治思想将原问题拆分成多个规模较小的子问题，最后将子问题的解合并起来。本题子问题是 x^{n/2}，如果 n 不为偶数，拆成两半还剩下一个 x，将子问题合并时还需多乘一个 x。 # -*- coding:utf-8 -*- class Solution: def Power(self, base, exponent): # write code here isNegative = False if exponent < 0: exponent = -expon...

【剑指offer】剪绳子（Python） 1. 聪明解法 绳子拆成 1 和 n-1， 1*(n-1) - n = -1 < 0，乘积变小，所以不能出现长度为 1 的绳子 绳子拆成 2 和 n-2， 2*(n-2) - n = n-4 >= 0(n>=4)，当n>=4时乘积变大 绳子拆成 3 和 n-3， 3*(n-3) - n = 2n-9 >= 0(n>=5)，当n>=5时乘积变大 绳子拆成 4 和 n-4， 因为 4 = 2*2 所以效果和2一样 绳子拆成 5 和 n-5， 因为 5=2+3，而5<2*3，...

【剑指offer】平衡二叉树（python） 递归返回当前结点是否平衡，和当前深度。 class Solution:     def IsBalanced_Solution(self, pRoot):         # write code here         def dfs(root):  &n...

【剑指offer】二叉树的深度（python） python 的三元运算符。“为真时的结果 if 判定条件 else 为假时的结果” # -*- coding:utf-8 -*- # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def TreeDepth(self, pRoot): # write code here ret...