剑指Offer-Python(16-20)
阅读原文时间:2023年07月11日阅读:1

# -*- 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())