剑指offer--day08

1.1 题目:二叉树镜像:操作给定的二叉树,将其变换为源二叉树的镜像。

1.2 思路:先交换根节点的两个子结点之后,我们注意到值为10、6的结点的子结点仍然保持不变,因此我们还需要交换这两个结点的左右子结点。做完这两次交换之后,我们已经遍历完所有的非叶结点。此时变换之后的树刚好就是原始树的镜像。交换示意图如下所示:

剑指offer--day08

 

1.3 代码:

 1 # -*- coding:utf-8 -*-
 2 # class TreeNode:
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 class Solution:
 8     # 返回镜像树的根节点
 9     def Mirror(self, root):
10         # write code here
11         if root == None:
12             return False
13         if root.left == None and root.right == None:
14             return root
15         temp = root.left
16         root.left = root.right
17         root.right = temp
18         
19         if root.left != None:
20             self.Mirror(root.left)
21         if root.right != None:
22             self.Mirror(root.right)

 

2.1 题目:顺时针打印矩阵:输入一个矩阵,按照从外向里以顺时针的顺序依次打印出每一个数字,例如,如果输入如下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.

2.2 思路:将结果存入vector数组,从左到右,再从上到下,再从右到左,最后从下到上遍历。

2.3 代码:

 1 # -*- coding:utf-8 -*-
 2 class Solution:
 3     # matrix类型为二维列表,需要返回列表
 4     def printMatrix(self, matrix):
 5         # write code here
 6         rows = len(matrix)
 7         cols = len(matrix[0])
 8         result = []
 9         if rows == 0 and cols == 0:
10             return result
11         left, right, top, buttom = 0, cols-1, 0, rows - 1
12         while left <= right and top <= buttom:
13             for i in range(left, right+1):
14                 result.append(matrix[top][i])
15             for i in range(top+1, buttom + 1):
16                 result.append(matrix[i][right])
17             if top != buttom:
18                 for i in range(left, right)[::-1]:
19                     result.append(matrix[buttom][i])
20             if left != right:
21                 for i in range(top+1, buttom)[::-1]:
22                     result.append(matrix[i][left])
23             left += 1
24             top += 1
25             right -= 1
26             buttom -= 1
27         return result

 

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

3.2 思路:使用两个stack,一个为数据栈,另一个为辅助栈。数据栈用于存储所有数据,辅助栈用于存储最小值。

  举个例子:

  入栈的时候:首先往空的数据栈里压入数字3,显然现在3是最小值,我们也把最小值压入辅助栈。接下来往数据栈里压入数字4。由于4大于之前的最小值,因此我们只要入数据栈,不压入辅助栈。

  出栈的时候:当数据栈和辅助栈的栈顶元素相同的时候,辅助栈的栈顶元素出栈。否则,数据栈的栈顶元素出栈。

  获得栈顶元素的时候:直接返回数据栈的栈顶元素。

  栈最小元素:直接返回辅助栈的栈顶元素。

3.3 代码:

 1 # -*- coding:utf-8 -*-
 2 class Solution:
 3     def __init__(self):
 4         self.stack = []
 5         self.min_stack = []
 6     def push(self, node):
 7         # write code here
 8         self.stack.append(node)
 9         if not self.min_stack or node <= self.min_stack[-1]:
10             self.min_stack.append(node)
11     def pop(self):
12         # write code here
13         if self.stack[-1] == self.min_stack[-1]:
14             self.min_stack.pop()
15         self.stack.pop()
16     def top(self):
17         # write code here
18         return self.stack[-1]
19     def min(self):
20         # write code here
21         return self.min_stack[-1]

 

参考:https://cuijiahua.com/

 

上一篇:遗传算法的C语言实现(一):以非线性函数求极值为例


下一篇:python day08