2018-10-18剑指offer
leetcode不同路径二
class Solution(object):
def uniquePathsWithObstacles(self, obstacleGrid):
m=len(obstacleGrid)
n=len(obstacleGrid[0])
if m==0 and n==0:
return 0
dp=[[0 for i in range(n)] for k in range(m)]
for i in range(m):
for j in range(n):
if obstacleGrid[i][j]==1:
dp[i][j]=0
elif i==0 and j==0:
dp[i][j]=1
elif i==0:
dp[0][j]=dp[0][j-1]
elif j==0:
dp[i][0]=dp[i-1][0]
else:
dp[i][j]=dp[i-1][j]+dp[i][j-1]
return dp[-1][-1]
if __name__ == '__main__':
s1=[[0,0]]
s=Solution()
print(s.uniquePathsWithObstacles(s1))
不同路径一
class Solution(object):
def uniquePaths(self, m, n):
if m==1 or n==1:
return 1
dp = [[1 for i in range(m)] for k in range(n)]
for i in range(n):
for j in range(m):
dp[i][j]=dp[i-1][j]+dp[i][j-1]
return dp[-1][-1]
if __name__ == '__main__':
S=Solution()
print(S.uniquePaths(7,2))
最小的组合数
from itertools import permutations
class Solution:
def PrintMinNumber(self, numbers):
if numbers is None or len(numbers) <=0:
return ''
n=len(numbers)
l1=list(permutations(numbers,len(numbers)))
l2=[]
for i in l1:
tmp=''
for each in i:
tmp=tmp+str(each)
l2.append(tmp)
l3 = [int(i) for i in l2]
return min(l3)
if __name__ == '__main__':
l=[3,32,321]
s=Solution()
print(s.PrintMinNumber(l))
是否为平衡二叉树
class Solution:
def __init__(self):
self.flag=true
def getDepth(self,pRoot):
if pRoot==None:
return 0
return max(self.getDepth(pRoot.left),self.getDepth(pRoot.right))
def IsBalanced_Solution(self, pRoot):
if pRoot==None:
return True
if abs(self.getDepth(pRoot.left)-self.getDepth(pRoot.right))>1:
return False
return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
去除出现次数为偶数的数
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
l2=list(set(array))
for i in l2:
array.remove(i)
for i in array:
if i in l2:
l2.remove(i)
return l2
if __name__ == '__main__':
s=Solution()
l1=[4,6,1,1,1,1]
print(s.FindNumsAppearOnce(l1))
