Part0 Basis
part1 sorting
1.插入排序
def insert_sort(lists):
count = len(lists)
for I in range(1,count):
key=lists[I]
j=i-1
while j>=0:
if lists[j]>key:
lists[j+1] = lists[j]
lists[j]=key
j -=1
else:
break
return lists
2.希尔排序
def shell_sort(lists):
count = len(lists)
step = 2
group = count/step
while group>0:
for I in range(0,group):
j = I + group
while j < count:
key= lists[j]
k = j - group
while k>=0:
if lists[k]>key:
lists[k+group] = lists[k]
lists[k] = key
k -= group
else:
break
j += group
group /=step
return lists
3 冒泡排序
描述
它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
def bubble_sort(lists):
count = len(lists)
for I in range(0,count):
for j in range(I+1,count):
if lists[I]>lists[j]:
lists[I],lists[j]=lists[j],lists[I]
return lists
4 快速排序
描述
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
def quick_sort(array, left, right):
if left >= right:
return
low = left
high = right
key = array[low]
while left < right:
while left < right and array[right] > key:
right -= 1
array[left] = array[right]
while left < right and array[left] <= key:
left += 1
array[right] = array[left]
array[right] = key
quick_sort(array, low, left - 1)
quick_sort(array, left + 1, high)
Version 2
def Partition(data,start,end):
if data == None or start>end or start<0 or end>=len(data):
return None
key = data[start]
while(start<end):
while start<end and data[end] >= key:
end -= 1
if start<end:
data[start] = data[end]
while start<end and data[start]<= key:
start +=1
if start<end:
data[end] = data[start]
data[start]=key
return start # return the index of mid-number
def QuickSort(data,start,end):
if start==end:
return None
index = Partition(data,start,len(data)-1)
if index>start:
QuickSort(data,start,index-1)
if(index<end):
QuickSort(data,index+1,end)
if __name__=="__main__":
data = [2,3,5,5,1,1,4,6,8,0,9]
QuickSort(data,0,len(data)-1)
print data
5 选择排序
def select_sort(lists):
count = len(lists)
for i in range(0,count):
min_index = i
for j in range(i+1,count):
if lists[min_index]>lists[j]:
min_index=j
lists[min_index],lists[i]=lists[i],lists[min_index]
return lists
6 堆排序
描述
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。
def MAX_Heapify(heap,HeapSize,root): # 下滤
left = 2*root+1
right = left +1
larger = root
if left<HeapSize and heap[larger]<heap[left]:
larger=left
if right<HeapSize and heap[larger]<heap[right]:
larger=right
if larger!=root: #如果做了堆调整则larger的值等于左节点或者右节点的，这个时候做对调值操作
heap[larger],heap[root]=heap[root],heap[larger]
MAX_Heapify(heap,HeapSize,larger)
def Build_MAX_Heap(heap):#构造一个堆，将堆中所有数据重新排序
HeapSize = len(heap)
for i in range((HeapSize-2)/2,-1,-1): #从后往前出数
MAX_Heapify(heap,HeapSize,i)
def HeapSort(heap):
Build_MAX_Heap(heap)
for i in range(len(heap)-1,-1,-1): #将根节点取出与最后一位做对调，对前面len-1个节点继续进行对调整过程。
heap[0],heap[i] = heap[i],heap[0]
MAX_Heapify(heap,i,0)
return heap
7 归并排序
描述
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
def merge(left,right):
i=j=0
result = []
while i <len(left) and j<len(right):
if left[i]<=right[j]:
result.append(left[i])
i+=1
else:
result.append(right[j])
j +=1
result += left[i:]
result += right[j:]
return result
def merge_sort(lists):
if len(lists)<=1:
return lists
num = len(lists)/2
left = merge_sort(lists[:num])
right = merge_sort(lists[num:])
return merge(left,right)
基数排序
#!/usr/bin/env python
#encoding=utf-8
import math
def sort(a, radix=10):
"""a为整数列表， radix为基数"""
K = int(math.ceil(math.log(max(a)+1, radix))) # 用K位数可表示任意整数
for i in range(1, K+1): # K次循环
bucket = [[] for i in range(radix)] # 不能用 [[]]*radix，否则相当于开了radix个完全相同的list对象
for val in a:
bucket[val%(radix**i)//(radix**(i-1))].append(val) # 獲得整數第K位數字 （從低到高）
del a[:]
for each in bucket:
a.extend(each) # 桶合并
数组中的逆序对（归并排序）
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007 输入描述: 题目保证输入的数组中没有的相同的数字
class Solution:
count=0
def InversePairs(self, data):
MergeSort(data)
return self.count%1000000007
def MergeSort(self,lists):
if len(lists) <= 1:
return lists
num = int( len(lists)/2 )
left = MergeSort(lists[:num])
right = MergeSort(lists[num:])
r, l=0, 0
result=[]
while l<len(left) and r<len(right):
if left[l] < right[r]:
result.append(left[l])
l += 1
else:
result.append(right[r])
r += 1
self.count += len(left)-l
result += right[r:]
result += left[l:]
return result
part2 DP题
数字翻转
给你一个01构成的数组。请你找出最小翻转步数，使得数组满足以下规则： 1的后面可以是1或者0，但是0的后面必须是0。
样例：
给出 array = [1,0,0,1,1,1] , 返回2。 解释： 把两个0翻转成1。
给出 array = [1,0,1,0,1,0] , 返回2。 解释： 把第二个1和第三个1都翻转成0。
class Solution:
"""
@param nums: the array
@return: the minimum times to flip digit
"""
def flipDigit(self, nums):
# Write your code here
dp = [[0, 0] for i in range(len(nums))]
dp[-1][1 - nums[-1]] = 1
for i in range(len(nums)-2,-1,-1):
if nums[i]==1: #dp[i][1] 如果该位变成1的话共需要翻转几次
#dp[i][0] 如果该位变成0的话共需要翻转几次
dp[i][1]=min(dp[i+1][0],dp[i+1][1])
dp[i][0]=dp[i+1][0]+1
else:
dp[i][1] = min(dp[i+1][0],dp[i+1][1])+1
dp[i][0] = dp[i+1][0]
return min(dp[0][0],dp[0][1])
丑数
把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
#动态规划，递推关系：k[i] = min(k[t2]*2, k[t3]*3, k[t5]*5)
class Solution:
def GetUglyNumber_Solution(self, index):
if index==0:
return 0
if index==1:
return 1
t2=t3=t5=0
numbers=[1]*index
for i in range(1,index):
numbers[i]=min(numbers[t2]*2,numbers[t3]*3,numbers[t5]*5)
if numbers[i] ==numbers[t2]*2:
t2 +=1
if numbers[i]==numbers[t3]*3:
t3 +=1
if numbers[i]==numbers[t5]*5:
t5 +=1
return numbers[index-1]
买卖股票的最佳时机 II （与最大子列和相似）
假设有一个数组，它的第i个元素是一个给定的股票在第i天的价格。设计一个算法来找到最大的利润。你可以完成尽可能多的交易(多次买卖股票)。然而,你不能同时参与多个交易(你必须在再次购买前出售股票)。
class Solution:
"""
@param prices: Given an integer array
@return: Maximum profit
"""
def maxProfit(self, prices):
# write your code here
total = 0
low, high = sys.maxint, sys.maxint
for x in prices:
if x > high: #当前价格如果还大于high 则持股
high = x
else: # 若小于等于high 可以卖了再买入
total += high - low
high, low = x, x
return total + high - low
最大连续乘积子串(动态规划)
def MaxProductSubstring(a):
if a==None or len(a)==0:
return 0
maxEnd = minEnd = maxResult = a[0]
for i in range(1,len(a)):
end1 = maxEnd * a[i]
end2 = maxEnd * a[i]
maxEnd = max(max(end1,end2),a[i])
minEnd = min(min(end1,end2),a[i]) # 因为是负数 但绝对值最大
maxResult=max(maxResult,maxEnd)
return maxResult
字符串编辑距离
题目描述
给定一个源串和目标串，能够对源串进行如下操作：
- 在给定位置上插入一个字符
- 替换任意字符
- 删除任意字符
写一个程序，返回最小操作数，使得对源串进行这些操作后等于目标串，源串和目标串的长度都小于2000。
def EditDistance(source,target):
lenS = len(source)
lenT = len(target)
DP = [[0]*(lenT+1)]*(lenT+1)
for i in range(lenS+1):
DP[i][0]=i
for j in range(lenT+1):
DP[0][j]=j
for i in range(1,lenS+1):
for j in range(1,lenT+1):
if source[i-1]==target[j-1]:
DP[i][j] = DP[i-1][j-1]
else:
DP[i][j]=1+min(DP[i-1][j],DP[i][j-1])
return DP[lenS][lenT]
交叉字符串
给出三个字符串:s1、s2、s3，判断s3是否由s1和s2交叉构成。
class Solution:
"""
@param s1: A string
@param s2: A string
@param s3: A string
@return: Determine whether s3 is formed by interleaving of s1 and s2
"""
def isInterleave(self, s1, s2, s3):
# write your code here
if not s1 or not s2 or not s3:
return False
if len(s1)+len(s2)!=len(s3):
return False
f =[[False]*(len(s2)+1) for i in range(len(s1)+1)]
f[0][0] = True
for i in range(1,len(s1)+1):
f[i][0]= s1[:i]==s3[:i]
for i in range(1,len(s2)+1):
f[0][i]= s2[:i]==s3[:i]
for i in range(1,len(s1)+1):
for j in range(1,len(s2)+1):
if s1[i-1]==s3[i+j-1]:
f[i][j] = f[i-1][j]
if s2[j-1]==s3[i+j-1]:
f[i][j] = f[i][j-1]
return f[-1][-1]
if __name__=="__main__":
#N,M = map(int, raw_input().split())
A= Solution()
s1 = "aabcc"
s2 = "dbbca"
s3= "aadbbcbcac"
print A.isInterleave(s1,s2,s3)
最长无重复字符的子串
给定一个字符串，请找出其中无重复字符的最长子字符串。
class Solution:
"""
@param s: a string
@return: an integer
"""
def lengthOfLongestSubstring(self, s):
# write your code here
if len(s)==0:
return 0
ans = 0
left = 0 # 记录合法的左边界index
last = {}
for i in range(len(s)):
# 子串中出现重复字符，变更left至上一次s[i]出现位置之后，使得子串合法
if s[i] in last and last[s[i]]>=left:
left = last[s[i]]+1
last[s[i]]=i
ans = max(ans,i-left+1)
return ans
01背包问题
# -*- coding:utf-8 -*-
def easy_package(weight,value,package):
N = len(weight)
M=package
weight.insert(0,0)
value.insert(0,0)
f = [[0]*(M+1) for I in range(N+1)] #NxM matrix
for i in range(1,N+1):
for j in range(1,M+1):
if weight[i]<=j:
f[i][j]=max(f[i-1][j],f[i-1][j-weight[i]]+value[i])
else:
f[i][j] = f[i-1][j]
return f[N][M]
# w[i]：第i个物体的重量
# - p[i]：第i个物体的价值
# - f[i][j]：前i个物体放入容量为j 包的最大价值
# - f[i-1][j]：前i个物体放入容量为j 包的最大价值
# - f[i-1][j-w[i]]：前i-1个物体放入容量为j-w[i] 包的最大价值
# f[i][j]=max{f[i-1][j-w[i]]+v[i]（j>=w[i]） , f[i-1][j]}
if __name__=="__main__":
weight = [2,2,6,5,4]
value = [6,3,5,4,6]
package = 10
print easy_package(weight,value,package)
优化空间后的 01背包问题
# -*- coding:utf-8 -*-
def easy_package(weight,value,package):
N = len(weight)
M=package
weight.insert(0,0)
value.insert(0,0)
f = [0]*(M+1) #(M+1) matrix
for i in range(1,N+1):
for m in range(0,M+1)[::-1]:
if m>= weight[i]:
f[m] = max(f[m],f[m-weight[i]]+value[i])
return f[M]
# 先考虑一下上面的状态转移方程如何实现
# 肯定有一个主循环i = 1...N,每次算出来二维数组dp[i][0..V]的所有值。
# 那么如果只用一个数组f[0...V],能不能保证第i次循环结束后f[v]就是我们定义的状态f[i][v]呢？
# f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，
# 能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？
# 事实上，这要求在每次主循环中我们以v=V...0的顺序推f[v]，
# 这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。
if __name__=="__main__":
weight = [2,2,6,5,4]
value = [6,3,5,4,6]
package = 10
print easy_package(weight,value,package)
完全背包问题
题目
有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价格是w[i].求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大
转化为01背包求解
最简单的想法是：考虑到第i种物品最多选V/c[i]件，于是可以把第i种物品转换为V/c[i]件费用及价值均不变的物品，然后求解这个01背包问题。但是这样完全没有改进时间复杂度，但这毕竟给了我们将完全背包转换为01背包问题的思路：将一种物品拆成多件物品
O(VN)的算法
for I = 1 ... N
for v = 0 ... V
f[v] = max{f[v], f[v-cost] + weight}
你会发现，这个伪代码与01背包的伪代码只有v的循环次序不同而已。为什么这样一改就行呢？首先，想想为什么01背包问题中要按照v=V…0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-c[i]]。而现在完全背包的特点恰好是每种物品可选无限件，所以在考虑“加选一件dii种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[i][c-v[i]],所以就可以并且必须采用v=0…V的顺序循环
def solve3(vlist,wlist,totalWeight,totalLength):
"""完全背包问题"""
resArr = np.zeros((totalWeight)+1,dtype=np.int32)
for i in range(1,totalLength+1):
for j in range(1,totalWeight+1):
if wlist[i] <= j:
resArr[j] = max(resArr[j],resArr[j-wlist[i]]+vlist[i])
return resArr[-1]
if __name__ == '__main__':
v = [0,60,100,120]
w = [0,10,20,30]
weight = 50
n = 3
result = solve3(v,w,weight,n)
print(result)
（硬币问题） 动态规划 (其实是完全背包问题)
如果我们有面值为 1 元、3 元和 5 元的硬币若干枚，如何用最少的硬币凑够 11 元？ (表面上这道题可以用贪心算法，但贪心算法无法保证可以求出解，比如 1 元换成 2 元的时候)
d(i)=min{ d(i-vj)+1 }，其中 i-vj >=0，vj表示第 j 个硬币的面值;
Min=[x for x in range(12)];
VN=[1,3,5];
for i in range(1,12,1):
for j in range(3):
if VN[j]<=i and Min[i-VN[j]]+1<Min[i]:
Min[i]=Min[i-VN[j]]+1;
print(Min[1::1]);
换硬币问题(完全背包)
用足够多的 1 分，2 分和 5 分硬币凑出 1 元钱，一共有多少种方法？(541)
def coinsCount(coins,amount):
result = [0]*(amount+1)
result[0] = 1
for coin in coins:
for i in range(1,amount+1):
if i>=coin:
result[i] += result[i-coin]
return result[-1]
n个骰子的点数
题目： 把n个骰子仍在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
动态规划思想
假设f(m,n)表示投第m个骰子时，点数之和n出现的次数,投第m个骰子时的点数之和只与投第m-1个骰子时有关。
递归方程：f(m,n)=f(m-1,n-1)+f(m-1,n-2)+f(m-1,n-3)+f(m-1,n-4)+f(m-1,n-5)+f(m-1,n-6)，表示本轮点数和为n出现次数等于上一轮点数和为n-1，n-2，n-3，n-4，n-5，n-6出现的次数之和。
初始条件：第一轮的f(1),f(2),f(3),f(4),f(5),f(6)均等于1.
def probability(n,dmax=6,dmin=1): # the minimum number in saizi is 1
dp = [0]*(n*dmax+1)
for i in range(dmin,dmax+1):
dp[i]=i
for i in range(2,n+1): # 第I个骰子扔过后的结果
for j in range(dmin*i,dmax*i+1)[::-1]:
for k in range(dmin,dmax+1):
if j>k:
dp[j] +=dp[j-k]
print dp
LIS 问题
一个序列有 N 个数：A[1],A[2],…,A[N]，求出最长非降子序列的长度。 (讲 DP 基本都会讲到的一个问题 LIS：longest increasing subsequence)
# -*- coding:utf-8 -*-
定义 d(i)，表示前 i 个数中以 A[i]结尾的最长非降子序列的长度
d(i) = max{1, d(j)+1},其中 j<i,A[j]<=A[i]
def LIS(nums):
d = [0]*len(nums)
answer = 1
for i in range(len(nums)):
d[i]=1
for j in range(i):
if nums[j]<=nums[i] and (d[j]+1)>d[i]:
d[i] = d[j]+1
answer = max(d)
return answer
if __name__=="__main__":
data = [5,3,4,8,6,7]
print LIS(data)
最长公共子序列 LCS（longest common sequence） 问题
c[i,j]表示Xi 和 Yj 的LCS的长度
c[i,j]= 0 if(I or j ==0)
= c[I-1,j-1]+1. If x[I]=y[j]
= max(c[I-1][j],c[I][j-1]). If x[I]!=y[j]
def LCS(s1,s2):
length1 = len(s1)
length2 = len(s2)
s1.insert(0,0)
s2.insert(0,0)
c = [[0]*(length2+1)]*(length1+1)
for i in range(1,len(c)):
for j in range(1,len(c[0])):
if s1[i]==s2[j]:
c[i][j] = c[i-1][j-1]+1
else:
c[i][j] = max(c[i-1][j],c[i][j-1])
return c[-1][-1]
if __name__=="__main__":
s1=[1,3,4,5,6,7,7,8]
s2=[3,5,7,4,8,6,7,8,2]
print LCS(s1,s2)
划分单词问题
给出一个字符串s和一个词典，判断字符串s是否可以被空格切分成一个或多个出现在字典中的单词。
样例
给出
s = "lintcode"
dict = ["lint","code"]
返回 true 因为”lintcode”可以被空格切分成”lint code”
class Solution:
"""
@param: s: A string
@param: dict: A dictionary of words dict
@return: A boolean
"""
def wordBreak(self, s, dict):
# write your code here
# f[i] means that until i ,it can be break into dict words
# f[i] is true if f[I-j]is true and f[I-j:i] is in dict (1<=j<=min(maxlength,i))
if len(dict)==0:
return len(s) == 0
n = len(s)
f = [False] *(n+1)
f[0] = True
maxLength = max([len(w) for w in dict])
for i in range(1,n+1):
for j in range(1,min(maxLength,i)+1):
if not f[i-j]:
continue
if s[i-j:i] in dict:
f[i] = True
break
return f[n]
part3. 树题
之字型打印二叉树
class Solution:
def Print(self, pRoot):
# write code here
if not pRoot:
return []
nodeStack=[pRoot]
result =[]
direction = 1
while nodeStack:
res = []
nextStack=[]
for i in nodeStack:
res.append(i.val)
if i.left:
nextStack.append(i.left)
if i.right:
nextStack.append(i.right)
nodeStack = nextStack[:]
if direction==-1:
res.reverse()
result.append(res) #result.extend(res)
direction *=-1
return result
不同的二叉查找树（动态规划）
给出 n，问由 1…n 为节点组成的不同的二叉查找树有多少种？
class Solution:
"""
@param n: An integer
@return: An integer
"""
def numTrees(self, n):
#The case for 3 elements example
# Count[3] = Count[0]*Count[2] (1 as root)
# + Count[1]*Count[1] (2 as root) 左边有几个数字 右边有几个数字
# + Count[2]*Count[0] (3 as root)
# Therefore, we can get the equation:
# Count[i] = ∑ Count[0...k] * count[ k+1....i] 0<=k<i-1
maxType = [1,1,2]
if n<=2:
return maxType[n]
maxType = maxType+[0]*(n-2)
for i in range(3,n+1):
for j in range(0,i):
maxType[i] += maxType[j]*maxType[i-j-1]
return maxType[-1]
最近公共祖先LCA问题
问题描述
求有根树的任意两个节点的最近公共祖先。
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def getLCA(root,node1,node2):
if root==None:
return None
if root==node1 or root==node2:
return root
left = getLCA(root.left,node1,node2)
right = getLCA(root.right,node1,node2)
if(left!=None and right!=None):
return root
elif left!=None:
return left
elif right!=None:
return right
else:
return None
若为二叉搜索树的话(BST)
二叉搜索树是经过排序的，位于左子树的节点都比父节点小，位于右子树的节点都比父节点大。既然要找最低的公共祖先节点，我们可以从根节点开始进行比较。
若当前节点的值比两个节点的值都大，那么最低的祖先节点一定在当前节点的左子树中，则遍历当前节点的左子节点；
反之，若当前节点的值比两个节点的值都小，那么最低的祖先节点一定在当前节点的右子树中，则遍历当前节点的右子节点；
这样，直到找到一个节点，位于两个节点值的中间，则找到了最低的公共祖先节点。
def getLCA(root,node1,node2):
if root==None or root==node1 or root==node2:
return root
if root.val > max(node1.val,node2,val):
return getLCA(root.left,node1,node2)
elif root.val < min(node1.val,node2.val):
return getLCA(root.right,node1,node2)
else:
return root
二叉树的深度
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
class Solution:
def TreeDepth(self, pRoot):
# write code here
if pRoot is None:
return 0
else:
left_deepth=self.TreeDepth(pRoot.left)
right_deepth=self.TreeDepth(pRoot.right)
return max(left_deepth,right_deepth)+1
树的子结构
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
# -*- coding:utf-8 -*-
class TreeNode:
def **init**(self,
x): self.val = x self.left = None self.right = None
class Solution:
def HasSubtree(self, pRoot1, pRoot2):
if pRoot2==None or pRoot1==None: return False
if self.judgeSame(pRoot1,pRoot2):
return True
else:
result1=self.HasSubtree(pRoot1.left,pRoot2)
result2=self.HasSubtree(pRoot1.right,pRoot2)
result=result1 or result2
return result
def judgeSame(self,pRoot1, pRoot2):
if pRoot2==None:
return True
if(pRoot1!=None and pRoot2==None):
return False
if (pRoot2 != None and pRoot1 == None):
return False
if(pRoot1.val!=pRoot2.val):
return False
return self.judgeSame(pRoot1.left,pRoot2.left) and self.judgeSame(pRoot1.right,pRoot2.right)
重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回构造的TreeNode根节点
def reConstructBinaryTree(self, pre, tin):
# write code here
if(len(pre)==0) or(len(tin)==0)：
return None
rootValue = pre[0]
root = TreeNode(rootValue)
if len(pre)==1:
return root
rootTinIndex = tin.index(rootValue)
preStart = 1
preEnd = rootTinIndex + 1
tinStart = 0
tinEnd = rootTinIndex
if rootTinIndex>0:
root.left = self.reConstructBinaryTree(pre[preStart:preEnd],tin[tinStart:tinEnd])
if rootTinIndex<(len(pre)-1):
root.right =self.reConstructBinaryTree(pre[preEnd+1:],tin[tinEnd+1:])
return root
if __name__=="__main__":
A = Solution()
pre = [1,2,4,7,3,5,6,8]
tin = [4,7,2,1,5,3,8,6]
print A.reConstructBinaryTree(pre,tin)
part4 遍历与查找
字符串的任意全排列问题
def all_permulation(result,data,length):# 字符串的全排列 采用DFS思想
if len(result)==length:
global possible_answer
possible_answer.append(result[:])
return
for i in range(len(data)):
result.append(data[i])
all_permulation(result,data[:i]+data[i+1:],length)
result.pop(-1)
return
if __name__=="__main__":
data= ['a','b','c','d']
possible_answer=[]
all_permulation([],data,len(data))
print possible_answer
print len(possible_answer)
二分查找
注意height和low的初始值和while的判断条件
def BinarySearch(array,t):
low = 0
height = len(array)-1
while low < height:
mid = (low+height)/2
if array[mid] < t:
low = mid + 1
elif array[mid] > t:
height = mid - 1
else:
return array[mid]
return -1
二分查找(旋转数组的最小数字)
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
# -*- coding:utf-8 -*-
class Solution:
def minNumberInRotateArray(self, rotateArray):
# write code here
if len(rotateArray)==0:
return 0
index1=0
index2=len(rotateArray)-1
indexMid = index1
while rotateArray[index1]>= rotateArray[index2]:
if index2-index1==1:
indexMid=index2
break
indexMid=(index1+index2)/2
if rotateArray[indexMid]>=rotateArray[index1]:
index1 = indexMid
elif rotateArray[indexMid]<=rotateArray[index2]:
index2=indexMid
return rotateArray[indexMid]
两个排序数组的中位数
两个排序的数组A和B分别含有m和n个数，找到两个排序数组的中位数，要求时间复杂度应为O(log (m+n))。
class Solution:
"""
@param: A: An integer array
@param: B: An integer array
@return: a double whose format is *.5 or *.0
"""
def findMedianSortedArrays(self, A, B):
# write your code here
n = len(A)+len(B)
if n %2 ==1:
return self.findKth(A,B,n/2+1)
else:
small = self.findKth(A,B,n/2)
big = self.findKth(A,B,n/2+1)
return (small+big)/2.0
def findKth(self,A,B,k):
if len(A)==0:
return B[k-1]
if len(B)==0:
return A[k-1]
if k==1:
return min(A[0],B[0])
a = A[k/2-1] if len(A)>=k/2 else None
b = B[k/2-1] if len(B)>=k/2 else None
if b ==None or (a!=None and a<b): #delete k/2 small numbers
return self.findKth(A[k/2:],B,k-k/2)
else:
return self.findKth(A,B[k/2:],k-k/2)
if __name__=="__main__":
A=[1,2,3,4]
B=[4,5,6]
sol = Solution()
print sol.findMedianSortedArrays(A,B)
partition查找(29.最小的k个数)
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4
时间复杂度为O(nlogn)
# -*- coding:utf-8 -*-
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
if(tinput==None or k==None or k>len(tinput) or k<0):
return None
start = 0
end = len(tinput)-1
index = self.Partition(tinput,start,end)
while(index!=(k-1)):
if index>k-1:
end = index-1
index = self.Partition(tinput,start,end)
else:
start = index +1
index = self.Partition(tinput,start,end)
return tinput[:k]
def Partition(self,data,start,end):
#sort this partition into two parts : one parts less than key, one parts more than key
# return the index of key
if(data==None or start<0 or end>=len(data) or start>end):
return #error
key = data[start]
while(start<end):
while start<end and data[end]>=key:
end -=1
if start<end:
data[start] = data[end]
while start<end and data[start]<=key:
start +=1
if start<end:
data[end] = data[start]
data[start]=key
return start
两数之和
给一个整数数组，找到两个数使得他们的和等于一个给定的数 target。
你需要实现的函数twoSum需要返回这两个数的下标, 并且第一个下标小于第二个下标。注意这里下标的范围是 0 到 n-1。
class Solution(object):
def twoSum(self, nums, target):
#hash用于建立数值到下标的映射
hash = {}
#循环nums数值，并添加映射
for i in range(len(nums)):
if target - nums[i] in hash:
return [hash[target - nums[i]], i]
hash[nums[i]] = i
#无解的情况
return [-1, -1]
三数之和
给出一个有n个整数的数组S，在S中找到三个整数a, b, c，找到所有使得a + b + c = 0的三元组。
注意事项 在三元组(a, b, c)，要求a <= b <= c。
结果不能包含重复的三元组。
class Solution(object):
'''
题意：求数列中三个数之和为0的三元组有多少个，需去重
暴力枚举三个数复杂度为O(N^3)
先考虑2Sum的做法，假设升序数列a，对于一组解ai,aj, 另一组解ak,al
必然满足 i<k j>l 或 i>k j<l, 因此我们可以用两个指针，初始时指向数列两端
指向数之和大于目标值时，右指针向左移使得总和减小，反之左指针向右移
由此可以用O(N)的复杂度解决2Sum问题，3Sum则枚举第一个数O(N^2)
使用有序数列的好处是，在枚举和移动指针时值相等的数可以跳过，省去去重部分
'''
def threeSum(self, nums):
nums.sort()
res = []
length = len(nums)
for i in range(0, length - 2):
if i and nums[i] == nums[i - 1]:
continue
target = nums[i] * -1
left, right = i + 1, length - 1
while left < right:
if nums[left] + nums[right] == target:
res.append([nums[i], nums[left], nums[right]])
right -= 1
left += 1
while left < right and nums[left] == nums[left - 1]:
left += 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
elif nums[left] + nums[right] > target:
right -= 1
else:
left += 1
return res
part5 线性数据结构
给出一个字符串（假设长度最长为1000），求出它的最长回文子串，你可以假定只有一个满足条件的最长回文串。
最长回文子串
class Solution(object):
# Python O(N^2)
def longestPalindrome(self, s):
ansl, ansr, maxx = 0, 1, 0
length = len(s)
for i in range(1, length * 2): #分为长度为奇数和偶数的情况
if i & 1 :
left = i //2
right = left
else :
left = i //2 - 1
right = left + 1
while (left >= 0) and (right < length) and (s[left] == s[right]):
left -= 1
right += 1
left += 1
right -= 1
if right - left > maxx:
maxx = right - left
ansl = left
ansr = right
return s[ansl: ansr + 1]
买卖股票的最佳时机
假设有一个数组，它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。
class Solution:
"""
@param prices: Given an integer array
@return: Maximum profit
"""
def maxProfit(self, prices):
# write your code here
total = 0
low, high = sys.maxint, 0
for x in prices:
if x - low > total:
total = x - low
if x < low:
low = x
return total
装最多水的容器
给定 n 个非负整数 a1, a2, …, an, 每个数代表了坐标中的一个点 (i, ai)。画 n 条垂直线，使得 i 垂直线的两个端点分别为(i, ai)和(i, 0)。找到两条线，使得其与 x 轴共同构成一个容器，以容纳最多水。
class Solution(object):
'''
题意:任取两个a[i]、a[j] 使得min(a[i], a[j]) * abs(i - j)最大化
用两个指针从两侧向中间扫描，每次移动数值较小的指针，用反证法可以证明
总是可以得到最优答案
'''
def maxArea(self, height):
left, right = 0, len(height) - 1
ans = 0
while left < right:
if height[left] < height[right]:
area = height[left] * (right - left)
left += 1
else:
area = height[right] * (right - left)
right -= 1
ans = max(ans, area)
return ans
链表中环的入口结点
一个链表中包含环，请找出该链表的环的入口结点。
第一步，找环中相汇点。分别用p1，p2指向链表头部，p1每次走一步，p2每次走二步，直到p1==p2找到在环中的相汇点。
第二步，找环的入口。接上步，当p1==p2时，p2所经过节点数为2x,p1所经过节点数为x,设环中有n个节点,p2比p1多走一圈有2x=n+x; n=x;可以看出p1实际走了一个环的步数，再让p2指向链表头部，p1位置不变，p1,p2每次走一步直到p1==p2; 此时p1指向环的入口。
class Solution:
def EntryNodeOfLoop(self, pHead):
# write code here
if(pHead==None or pHead.next==None):
return None
p1 = pHead
p2 = pHead
while(p2!=None and p2.next!=None):
p1=p1.next
p2 = p2.next.next
if(p1==p2):
p2 = pHead
while(p1!=p2):
p1 = p1.next
p2 = p2.next
if p1==p2:
return p1
return None
反转链表
# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
# 返回ListNode
def ReverseList(self, pHead):
# write code here
pNew=None
pCur=pHead
while(pCur!=None):
pHead = pCur.next
pCur.next=pNew
pNew=pCur
pCur=pHead
return pNew
合并k个排序链表 并且返回合并后的排序链表
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
class Solution:
"""
@param lists: a list of ListNode
@return: The head of one sorted list.
"""
from heapq import heappop, heappush
def mergeKLists(self, lists):
if not lists:
return None
trav = dummy = ListNode(-1)
heap = []
for link_list in lists:
if link_list:
self.heappushNode(heap, link_list)
while heap:
node = heappop(heap)[1]
trav.next = node
trav = trav.next
if trav.next:
self.heappushNode(heap, trav.next)
return dummy.next
def heappushNode(self, heap, node):
heappush(heap, (node.val, node))# input the key and the node
包含min的最小栈
创建一个辅助栈 来保存每个当前情况下的min值
class Solution:
stack=[]
aux_stack=[]
def push(self, node):
self.stack.append(node)
self.aux_stack.append(max(aux_stack[-1],node));
def pop(self):
# write code here
self.aux_stack.pop()
return self.stack.pop()
def top(self):
return self.stack[-1]
def min(self):
return aux_stack[-1]
顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10
其实zip还是反过来会这个二维数组操作，但要注意写成zip(*)，表示这是一个zip的逆操作。
class Solution:
# matrix类型为二维列表，需要返回列表
def printMatrix(self, matrix):
if matrix==None or len(matrix)==0:
return None
a=[]
while matrix:
a.extend(list(matrix.pop(0)))
matrix=zip(*matrix)
matrix.reverse()
return a
Version2
def printMatrix(matrix):
result = []
while True:
result.extend(matrix.pop(0))
if matrix!=[] :
matrix = turn(matrix)
else:
break
return result
def turn(matrix):
originRows = len(matrix)
originCols = len(matrix[0])
answer = []
for i in range(originCols):
tmp = []
for j in range(originRows):
tmp.append(matrix[j][i])
answer.append(tmp)
answer.reverse()
return answer
翻转字符串
“How Are You” ->"”You Are How”
单词的构成：无空格字母构成一个单词
输入字符串是否包括前导或者尾随空格？可以包括，但是反转后的字符不能包括
如何处理两个单词间的多个空格？在反转字符串中间空格减少到只含一个
class Solution:
"""
@param: s: A string
@return: A string
"""
def reverseWords(self, s):
# write your code here
sList = list(s)
while len(sList)!=0 and sList[0]== " ":
del sList[0]
while len(sList)!=0 and sList[-1] == " ":
del sList[-1]
if len(sList)==1 or len(sList)==0:
return "".join(sList)
index_tmp = 0
while index_tmp<=len(sList)-2:
if sList[index_tmp]==" " and sList[index_tmp+1]==" ":
del sList[index_tmp]
else:
index_tmp +=1
for i in range(0,len(sList)/2):
sList[i],sList[-1-i] = sList[-1-i],sList[i]
begin = 0
end = 0
for i in range(len(sList)):
if sList[i] == " " or i==len(sList)-1:
end = i-1
if i == len(sList)-1:
end = i
if sList[end]>="Z"
for j in range(0, (end-begin)/2):
sList[begin+j],sList[end-j] = sList[end-j],sList[begin+j]
begin = i+1
return "".join(sList)
if __name__=='__main__':
A = Solution()
print A.reverseWords("How are You") #You are How
数学运算
数值的整数次方
实现函数 double Power(double base, int exponent)
考虑 base是否为0 考虑exponent为正数负数为0
数组中只出现一次的两个数字
题目描述 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
此题考察的是异或运算的特点：即两个相同的数异或结果为0。 此题用了两次异或运算特点： （1）第一次使用异或运算，得到了两个只出现一次的数相异或的结果。 （2）因为两个只出现一次的数肯定不同，即他们的异或结果一定不为0，一定有一个位上有1。另外一个此位上没有1，我们可以根据此位上是否有1，将整个数组重新划分成两部分，一部分此位上一定有1，另一部分此位上一定没有1，然后分别对每部分求异或，因为划分后的两部分有这样的特点：其他数都出现两次，只有一个数只出现一次。因此，我们又可以运用异或运算，分别得到两部分只出现一次的数。
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
# write code here
if len(array)<2:
return None
firstXOR = 0
for i in range(len(array)):
firstXOR = firstXOR ^ array[i]
flag = 1
while((flag^firstXOR)==0):
flag = flag <<1
a = b = 0
for i in range(len(array)):
if (array[i]&flag) ==0:
a = a^array[i]
else:
b = b^array[i]
return [a,b]
大数乘法
def multi(strA,strB):
negative = False
listA = list(strA)
listB = list(strB)
if listA[0]=='-':
negative = not negative
del listA[0]
if listB[0] =='-':
negative = not negative
del listB[0]
lenA = len(listA)
lenB = len(listB)
result = [0 for i in range(lenA+lenB)]
for i in range(1,lenA+1):
for j in range(1,lenB+1):
result[-(i+j)+1] +=int(listA[-i])*int(listB[-j])
for i in range(len(result)-1,0,-1):
if result[i]>=10:
result[i-1] +=result[i]//10
result[i] = result[i]%10
while(result[0]==0):
del result[0]
result = ''.join(map(str,result))
if negative:
result = '-'+result
return result
if __name__=='__main__':
a = "-123"
b = '456'
res=multi(a,b)
print('multi',res)
print('ok',int(a)*int(b))
大数加法
def addOperation(strA,strB):
listA = map(int,list(strA))
listB = map(int,list(strB))
while len(listA)<len(listB):
listA.insert(0,0)
while len(listB)<len(listA):
listB.insert(0,0)
result = [0 for i in range(len(listA)+1)]
for i in range(1,len(listA)+1):
result[-1*i] = listA[-1*i]+listB[-1*i]
for i in range(len(result)-1,0,-1):
if result[i]>=10:
result[i-1] +=result[i]//10
result[i] = result[i]%10
while(result[0]==0):
del result[0]
result = ''.join(map(str,result))
return result
if __name__=='__main__':
a = "123771321312"
b = '4561231231'
res=addOperation(a,b)
print('addOperation',res)
print('ok',int(a)+int(b))
最多有多少个点在同一条直线上
class Point:
def __init__(self, a=0, b=0):
self.x = a
self.y = b
class Solution:
"""
@param points: an array of point
@return: An integer
"""
def maxPoints(self, points):
# write your code here
len_points = len(points)
if len_points<=1:
return len_points
max_count = 0
for index1 in range(len_points):
p1 = points[index1]
gradients = {}
infinite_count = 0
duplicate_count = 0
for index2 in range(index1,len_points):
p2 = points[index2]
dx = p2.x-p1.x
dy = p2.y-p1.y
if dx==0 and dy==0:
duplicate_count +=1
if dx==0:
infinite_count +=1
else:
gra = float(dy)/dx
gradients[gra]=(gradients[gra] + 1 if gradients.has_key(gra) else 1)
max_count = max(max_count,infinite_count)
for k,v in gradients.items():
v +=duplicate_count
max_count = max(v,max_count)
return max_count
