# -*- coding:utf-8 -*-
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
# 返回合并后列表
def Merge(self, pHead1, pHead2):
# write code here
p1 = pHead1
p2 = pHead2
p = ListNode(0)
pNew = p
while p1 and p2:
if p1.val <= p2.val:
p.next = p1
p = p.next
p1 = p1.next
else:
p.next = p2
p = p.next
p2 = p2.next
if not p1:
p.next = p2
elif not p2:
p.next = p1
return pNew.next
head1 = ListNode(1)
t1 = ListNode(3)
head1.next = t1
t2 = ListNode(5)
t1.next = t2
t2.next = None
head2 = ListNode(2)
t1 = ListNode(4)
head2.next = t1
t2 = ListNode(6)
t1.next = t2
t2.next = None
s = Solution()
print(s.Merge(head1, head2).next.val)
递归
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def HasSubtree(self, root1, root2):
# write code here
if not root1 or not root1:
return False
return self.doesTreeHashTree2(root1, root2) or self.HasSubtree(root1.right, root2) or self.HasSubtree(
root1.left, root2)
def doesTreeHashTree2(self, root1, root2):
if not root2:
return True
if not root1:
return False
if root1.val != root2.val:
return False
return self.doesTreeHashTree2(root1.left, root2.left) and self.doesTreeHashTree2(root1.right, root2.right)
s = Solution()
tree1 = TreeNode(1)
t1 = TreeNode(2)
t2 = TreeNode(3)
t3 = TreeNode(4)
t4 = TreeNode(5)
tree1.left = t1
tree1.right = t2
t1.left = t3
t1.right = t4
tree2 = TreeNode(2)
t3 = TreeNode(4)
t4 = TreeNode(5)
tree2.left = t3
tree2.right = t4
print(s.HasSubtree(tree1, tree2))
递归
# -*- coding:utf-8 -*-
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
# 返回镜像树的根节点
def Mirror(self, root):
# write code here
if not root:
return
if not root.left and not root.right:
return
temp = root.left
root.left = root.right
root.right = temp
if root.left:
self.Mirror(root.left)
elif root.right:
self.Mirror(root.right)
s = Solution()
tree1 = TreeNode(1)
t1 = TreeNode(2)
t2 = TreeNode(3)
t3 = TreeNode(4)
t4 = TreeNode(5)
tree1.left = t1
tree1.right = t2
t1.left = t3
t1.right = t4
s.Mirror(tree1)
print(tree1.right.right.val)
# -*- coding:utf-8 -*-
class Solution:
# matrix类型为二维列表,需要返回列表
def printMatrix(self, matrix):
# write code here
row = len(matrix)
con = len(matrix[0])
cir = 0
t = []
while row > 2 * cir and con > 2 * cir:
for i in range(cir, con - cir): # 右
t.append(matrix[cir][i])
if cir < row - cir - 1: # 下
for i in range(cir + 1, row - cir):
t.append(matrix[i][con - cir - 1])
if con - cir - 1 > cir and row - cir - 1 > cir: # 左
for i in range(con - cir - 2, cir-1, -1):
t.append(matrix[row - cir - 1][i])
if cir < con - cir - 1 and cir < row - cir - 2: # 下
for i in range(row - cir - 2, cir, -1):
t.append(matrix[i][cir])
cir += 1
return t
s = Solution()
a = [[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]]
t = s.printMatrix(a)
print(t)
要求min函数时间复杂度为O(1),因此增加辅助栈存 “当前最小元素“
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.q = []
self.mi = []
def push(self, node):
min = self.min()
if not self.mi or node <= min:
self.mi.append(node)
else:
self.mi.append(min)
self.q.append(node)
def pop(self):
if self.q:
self.mi.pop()
return self.q.pop()
def top(self):
if self.q:
return self.q\[-1\]
def min(self):
if self.mi:
return self.mi\[-1\]
s = Solution()
s.push(1)
s.push(2)
s.push(5)
s.push(3)
print(s.min())
print(s.pop())
print(s.top())
手机扫一扫
移动阅读更方便
你可能感兴趣的文章