add · HyperLoco/AlgorithmsByPython@f0e9e34 · GitHub
Skip to content

Commit f0e9e34

Browse files
Jack-Lee-HiterJack-Lee-Hiter
committed
add
1 parent bff29ea commit f0e9e34

6 files changed

Lines changed: 239 additions & 123 deletions

File tree

‎.idea/workspace.xml‎

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

‎MapReduce_and_filter.py‎

Lines changed: 34 additions & 0 deletions

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

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+
class TreeNode:
7+
def __init__(self, x):
8+
self.val = x
9+
self.left = None
10+
self.right = None
11+
class Solution:
12+
def findParent(self, pNode1, pNode2, root):
13+
if pNode1 == None or pNode2 == None:
14+
return
15+
if pNode1 == pNode2:
16+
return
17+
val1 = pNode1.val
18+
val2 = pNode2.val
19+
while root != None:
20+
if (val1 - root.val) * (val2 - root.val) <= 0:
21+
return root.val
22+
elif val1 > root.val and val2 > root.val:
23+
root = root.right
24+
else:
25+
root = root.left
26+
27+
return False
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
class TreeNode:
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
class Solution:
12-
def findParent(self, pNode1, pNode2, root):
13-
if pNode1 == None or pNode2 == None:
14-
return
15-
if pNode1 == pNode2:
16-
return
17-
val1 = pNode1.val
18-
val2 = pNode2.val
19-
while root != None:
20-
if (val1 - root.val) * (val2 - root.val) <= 0:
21-
return root.val
22-
elif val1 > root.val and val2 > 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-
return False
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+
def lowestCommonAncestor(self, root, A, B):
17+
# write your code here
18+
if root == None:
19+
return False
20+
pathA = self.storeNodes(root, A)[0]
21+
pathB = self.storeNodes(root, B)[0]
22+
if pathA and pathB:
23+
lenA, lenB = len(pathA), len(pathB)
24+
diff = abs(lenA - lenB)
25+
if lenA > lenB:
26+
markA = lenA - diff - 1
27+
markB = lenB - 1
28+
else:
29+
markA = lenA - 1
30+
markB = lenB - diff - 1
31+
while markA >= 0 and markB >= 0:
32+
if pathA[markA] == pathB[markB]:
33+
return pathA[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+
def storeNodes(self, root, targetNode):
38+
if root == None or targetNode == None:
39+
return []
40+
elif root.val == targetNode.val:
41+
return [[targetNode]]
42+
stack = []
43+
if root.left:
44+
stackLeft = self.storeNodes(root.left, targetNode)
45+
for i in stackLeft:
46+
i.insert(0, root)
47+
stack.append(i)
48+
if root.right:
49+
stackRight = self.storeNodes(root.right, targetNode)
50+
for i in stackRight:
51+
i.insert(0, root)
52+
stack.append(i)
53+
return stack
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
return True
4747
return False
48+
# 扩展, 输出数组中target的个数
49+
def searchMatrix(self, matrix, target):
50+
if matrix == None or len(matrix) == 0:
51+
return 0
52+
rows = len(matrix)
53+
cols = len(matrix[0])
54+
row, col = 0, cols - 1
55+
count = 0
56+
while row <= rows - 1 and col >= 0:
57+
if matrix[row][col] > target:
58+
col -= 1
59+
elif matrix[row][col] < target:
60+
row += 1
61+
else:
62+
count += 1
63+
col -= 1
64+
return count
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

0 commit comments

Comments
 (0)