python-剑指offer16-20
2021-01-07 00:29
标签：函数 python 第一个 one else coding 值栈 mic tom 16、树 操作给定的二叉树，将其变换为源二叉树的镜像。 17、数组 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下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. 方法一： 方法二： 方法三： 18、栈 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1）） 较好的思路：开一个新栈，此栈与数值栈一一对应，在元素入栈时，就记录处于每一个位置时的当前最小值，这样不论什么情况，不论之前如何出栈入栈，都能立即获取到最小值。 19、栈 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的） 解题思路：例如对于压入顺序 12345和弹出顺序45312，首先读到4，则从压入序列里依次压入1234，然后弹出4；读到5，则压入5，弹出5；读到3，栈顶恰好为3，弹出3；读到1，栈顶为2，应当继续压入直到压入1，但压入序列已经读完，没找到1，所以错误。 20、树 从上往下打印出二叉树的每个节点，同层节点从左至右打印。 解题思路：树的层次遍历，注意的是当root为空时要返回[]，而不是None。 python-剑指offer16-20 标签：函数 python 第一个 one else coding 值栈 mic tom 原文地址：https://www.cnblogs.com/xiximayou/p/12967006.html# 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 root == None:
return None
if root.left != None or root.right != None:
root.left,root.right = root.right,root.left
self.Mirror(root.left)
self.Mirror(root.right)
# -*- coding:utf-8 -*-
class Solution:
# matrix类型为二维列表，需要返回列表
def printMatrix(self, matrix):
# write code here
res=[]
i,j=0,0
d=0
vis=[[0 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
tmp=[[0,1],[1,0],[0,-1],[-1,0]]
while i>=0 and i
# -*- coding:utf-8 -*-
class Solution:
# matrix类型为二维列表，需要返回列表
def printMatrix(self, matrix):
# write code here
if not matrix:
return matrix
rows = len(matrix)
cols = len(matrix[0])
result = []
start = 0
# 判断是否继续往里走一圈
while cols > start * 2 and rows > start * 2:
# 走一圈的代码
end_x = cols - 1 - start
end_y = rows - 1 - start
# 打印第一行
for i in range(start, end_x+1):
result.append(matrix[start][i])
# 打印最后一列
if start end_y:
for i in range(start+1, end_y+1):
result.append(matrix[i][end_x])
# 打印最后一行
if start and start end_y:
for i in range(end_x-1, start-1, -1):
result.append(matrix[end_y][i])
# 打印第一列
if start and start :
for i in range(end_y-1, start, -1):
result.append(matrix[i][start])
start += 1
return result
# -*- coding:utf-8 -*-
class Solution:
# matrix类型为二维列表，需要返回列表
def printMatrix(self, matrix):
if not matrix:
return matrix
result = []
while len(matrix) > 0:
result.extend(matrix[0])
matrix = zip(*matrix[1:])[::-1]
return result
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.s1=[]
self.s2=[]
def push(self, node):
# write code here
self.s1.append(node)
if len(self.s2)==0:
self.s2.append(node)
else:
if node>self.s2[-1]:
self.s2.append(self.s2[-1])
else:
self.s2.append(node)
def pop(self):
# write code here
if len(self.s1)==0:
return None
del self.s2[-1]
res=self.s1[-1]
del self.s1[-1]
return res
def top(self):
# write code here
if len(self.s1)==0:
return None
else:
return self.s1[-1]
def min(self):
# write code here
if len(self.s1)==0:
return None
else:
return self.s2[-1]
class Solution:
def IsPopOrder(self, pushV, popV):
# write code here
stack = []
cur = 0
for pop in popV:
while len(stack)==0 or pop != stack[-1] and cur len(pushV):
stack.append(pushV[cur])
cur +=1
if cur == len(pushV) and stack[-1] != pop:
return False
else:
stack.pop()
return True
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回从上到下每个节点值列表，例：[1,2,3]
def PrintFromTopToBottom(self, root):
# write code here
if not root:
return []
stack=[root]
res=[]
while stack:
for i in range(len(stack)):
t=stack.pop(0)
res.append(t.val)
if t.left:
stack.append(t.left)
if t.right:
stack.append(t.right)
return res
上一篇：排序算法
下一篇：像宝石一样的Java原子类
文章标题：python-剑指offer16-20
文章链接：http://soscw.com/index.php/essay/40591.html