牛客网:剑指Offer_编程题python2.7(3)

公司实习比在学校搞课题要紧张。。。上传一波存货


树的子结构

输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def HasSubtree(self, pRoot1, pRoot2):
# write code here
if not pRoot1 or not pRoot2:
return False
return self.is_subtree(pRoot1, pRoot2) or self.HasSubtree(pRoot1.left, pRoot2) or self.HasSubtree(pRoot1.right, pRoot2)
#判断两个二叉树是否相同
def is_subtree(self, a, b):
if not b:
return True
if not a or a.val != b.val:
return False
return self.is_subtree(a.left, b.left) and self.is_subtree(a.right, b.right)

二叉树的镜像

操作给定的二叉树,将其变换为源二叉树的镜像。所有的左节点和右节点val交换

1
2
3
4
5
6
7
8
9
10
class Solution:
# 返回镜像树的根节点
def Mirror(self, root):
# write code here
if root == None:
return
else:
root.left, root.right= root.right,root.left #交换
self.Mirror(root.left) #左子树递归
self.Mirror(root.right) #右子树递归

顺时针打印矩阵

输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下4 X 4矩阵: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

分成两步,用pop()读取第一行的数,剩余矩阵逆时针旋转90度,循环直到最后矩阵为空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
# matrix类型为二维列表,需要返回列表
def printMatrix(self, matrix):
# write code here
res = []
while matrix:
res = res+matrix.pop(0)
# 矩阵为空时结束
if not matrix:
break
matrix = self.turn(matrix)
return res

# 矩阵旋转90度
def turn(self, matrix):
n = len(matrix)
m = len(matrix[0])
new = []
# 以最后一列的开始往前遍历
for i in range(m-1,-1,-1):
newcol = []
# 以第一行的开始往下遍历
for j in range(n):
newcol.append(matrix[j][i])
new.append(newcol)
return new

包含min函数的栈

定义栈的数据结构,请在该类型中实现一个能够得到栈中所含最小元素的min函数(时间复杂
度应为O(1))。

栈的数据结构可以用数组来表示 list.pop() list.append() 要求min的时间复杂度为O(1)需要在出栈入栈的时候就知道最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
def __init__(self):
self.res = [] #栈的数据结构
self.min_res = [] #设最小值
def push(self, node):
# write code here
self.res.append(node)#基本的入栈语法
#如果最小值列表为空/当前的最小值小于存入min_res的最后一位数
#就把值加入到min_res中
if not self.min_res or node<self.min_res[-1]:
self.min_res.append(node)
# 否则把min_res[-1]再存一次,保证self.min_res[-1]永远是最小值
else:
self.min_res.append(self.min_res[-1])

def pop(self):
# write code here
if not self.res:
val = self.res.pop()#基本出栈语法
self.min_res.pop() #也要pop出一个数
def top(self):
# write code here
return self.res[-1]
def min(self):
# write code here
return self.min_res[-1]