Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitf0e9e34

Browse files
add
1 parentbff29ea commitf0e9e34

File tree

6 files changed

+239
-123
lines changed

6 files changed

+239
-123
lines changed

‎.idea/workspace.xml

Lines changed: 88 additions & 83 deletions
Some generated files are not rendered by default. Learn more aboutcustomizing how changed files appear on GitHub.

‎MapReduce_and_filter.py

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
# -*- coding:UTF-8 -*-
2+
importfunctools
3+
# Python3.x和Python2.x对于map、reduce、filter的处理变得不同
4+
# Python3.x中map和filter的输出是一个map型和filter型, 需要从里面取出需要的值
5+
# Python2.x中map和filter输出的直接是一个list
6+
# Python3.x中使用reduce需要引入functools
7+
8+
# 使用map把list中的int变为str
9+
map(str, [1,2,3,4,5,6,7,8,9])
10+
# 使用map()把名字规范化, 首字母大写,其余小写
11+
defstandardName(s):
12+
returns.capitalize()
13+
print([xforxinmap(standardName, ['adam','LISA','barT'])])
14+
# 在Python2.x中应该使用print(map(standardName, ['adam', 'LISA', 'barT']))
15+
16+
# 使用reduce()输出一个list的所有数的乘积
17+
defprod(aList):
18+
returnfunctools.reduce(lambdax,y:x*y,aList)
19+
print(prod([1,2,3,4,5]))
20+
21+
# 使用filter()打印100以内的素数
22+
defisPrime(n):
23+
isPrimeFlag=True
24+
ifn<=1:
25+
isPrimeFlag=False
26+
i=2
27+
28+
whilei*i<=n:
29+
ifn%i==0:
30+
isPrimeFlag=False
31+
break
32+
i+=1
33+
returnnifisPrimeFlagelseNone
34+
print(filter(isPrime,range(101)))
Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
'''
2+
查找二叉搜索树两个结点的最低公共祖先
3+
'''
4+
5+
# -*- coding:utf-8 -*-
6+
classTreeNode:
7+
def__init__(self,x):
8+
self.val=x
9+
self.left=None
10+
self.right=None
11+
classSolution:
12+
deffindParent(self,pNode1,pNode2,root):
13+
ifpNode1==NoneorpNode2==None:
14+
return
15+
ifpNode1==pNode2:
16+
return
17+
val1=pNode1.val
18+
val2=pNode2.val
19+
whileroot!=None:
20+
if (val1-root.val)* (val2-root.val)<=0:
21+
returnroot.val
22+
elifval1>root.valandval2>root.val:
23+
root=root.right
24+
else:
25+
root=root.left
26+
27+
returnFalse
28+
29+
pNode1=TreeNode(8)
30+
pNode2=TreeNode(6)
31+
pNode3=TreeNode(10)
32+
pNode4=TreeNode(5)
33+
pNode5=TreeNode(7)
34+
pNode6=TreeNode(9)
35+
pNode7=TreeNode(11)
36+
37+
pNode1.left=pNode2
38+
pNode1.right=pNode3
39+
pNode2.left=pNode4
40+
pNode2.right=pNode5
41+
pNode3.left=pNode6
42+
pNode3.right=pNode7
43+
44+
S=Solution()
45+
print(S.findParent(pNode3,pNode7,pNode1))

‎Target Offer/二叉树的最低公共祖先.py

Lines changed: 49 additions & 40 deletions
Original file line numberDiff line numberDiff line change
@@ -1,45 +1,54 @@
1-
'''
2-
查找二叉搜索树两个结点的最低公共祖先
3-
'''
4-
5-
# -*- coding:utf-8 -*-
1+
# 二叉树的最低公共祖先
2+
"""
3+
Definition of TreeNode:
4+
"""
65
classTreeNode:
7-
def__init__(self,x):
8-
self.val=x
9-
self.left=None
10-
self.right=None
6+
def__init__(self,val):
7+
self.val=val
8+
self.left,self.right=None,None
119
classSolution:
12-
deffindParent(self,pNode1,pNode2,root):
13-
ifpNode1==NoneorpNode2==None:
14-
return
15-
ifpNode1==pNode2:
16-
return
17-
val1=pNode1.val
18-
val2=pNode2.val
19-
whileroot!=None:
20-
if (val1-root.val)* (val2-root.val)<=0:
21-
returnroot.val
22-
elifval1>root.valandval2>root.val:
23-
root=root.right
24-
else:
25-
root=root.left
10+
"""
11+
@param root: The root of the binary search tree.
12+
@param A and B: two nodes in a Binary.
13+
@return: Return the least common ancestor(LCA) of the two nodes.
14+
"""
2615

27-
returnFalse
28-
29-
pNode1=TreeNode(8)
30-
pNode2=TreeNode(6)
31-
pNode3=TreeNode(10)
32-
pNode4=TreeNode(5)
33-
pNode5=TreeNode(7)
34-
pNode6=TreeNode(9)
35-
pNode7=TreeNode(11)
16+
deflowestCommonAncestor(self,root,A,B):
17+
# write your code here
18+
ifroot==None:
19+
returnFalse
20+
pathA=self.storeNodes(root,A)[0]
21+
pathB=self.storeNodes(root,B)[0]
22+
ifpathAandpathB:
23+
lenA,lenB=len(pathA),len(pathB)
24+
diff=abs(lenA-lenB)
25+
iflenA>lenB:
26+
markA=lenA-diff-1
27+
markB=lenB-1
28+
else:
29+
markA=lenA-1
30+
markB=lenB-diff-1
31+
whilemarkA>=0andmarkB>=0:
32+
ifpathA[markA]==pathB[markB]:
33+
returnpathA[markA]
34+
markA-=1
35+
markB-=1
3636

37-
pNode1.left=pNode2
38-
pNode1.right=pNode3
39-
pNode2.left=pNode4
40-
pNode2.right=pNode5
41-
pNode3.left=pNode6
42-
pNode3.right=pNode7
37+
defstoreNodes(self,root,targetNode):
38+
ifroot==NoneortargetNode==None:
39+
return []
40+
elifroot.val==targetNode.val:
41+
return [[targetNode]]
42+
stack= []
43+
ifroot.left:
44+
stackLeft=self.storeNodes(root.left,targetNode)
45+
foriinstackLeft:
46+
i.insert(0,root)
47+
stack.append(i)
48+
ifroot.right:
49+
stackRight=self.storeNodes(root.right,targetNode)
50+
foriinstackRight:
51+
i.insert(0,root)
52+
stack.append(i)
53+
returnstack
4354

44-
S=Solution()
45-
print(S.findParent(pNode3,pNode7,pNode1))

‎Target Offer/二维数组查找.py

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -45,6 +45,24 @@ def Find(self, array, target):
4545
else:
4646
returnTrue
4747
returnFalse
48+
# 扩展, 输出数组中target的个数
49+
defsearchMatrix(self,matrix,target):
50+
ifmatrix==Noneorlen(matrix)==0:
51+
return0
52+
rows=len(matrix)
53+
cols=len(matrix[0])
54+
row,col=0,cols-1
55+
count=0
56+
whilerow<=rows-1andcol>=0:
57+
ifmatrix[row][col]>target:
58+
col-=1
59+
elifmatrix[row][col]<target:
60+
row+=1
61+
else:
62+
count+=1
63+
col-=1
64+
returncount
65+
4866

4967
array= [[1,2,8,9],
5068
[2,4,9,12],
@@ -53,10 +71,14 @@ def Find(self, array, target):
5371
array2= []
5472
array3= [['a','b','c'],
5573
['b','c','d']]
74+
array4= [[62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80],[63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81],[64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82],[65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83],[66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84],[67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85]]
75+
76+
5677
findtarget=Solution()
5778
print(findtarget.Find(array,10))
5879
print(findtarget.Find(array,30))
5980
print(findtarget.Find(array,13.0))
6081
print(findtarget.Find(array,''))
6182
print(findtarget.Find(array2,10))
6283
print(findtarget.Find(array3,'b'))
84+
print(findtarget.searchMatrix(array4,81))

‎Target Offer/求前n项和.py

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -15,6 +15,7 @@ def sum0(self, n):
1515
# 利用非0值作两次非运算返回false, 0作两次非运算返回True
1616
defsumN(self,n):
1717
fun= {False:self.sum0,True:self.sumN}
18+
# 此处的fun[not not n] 不能写作func[not not n-1], 否则测试用例为0的话, 就会无限次迭代
1819
returnn+fun[notnotn](n-1)
1920

2021
defSum_Solution2(self,n):

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp