题18--顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字
举个简单的例子如下：
例如，如果输入如下矩阵：
[[ 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.
对于本题不涉及较为常见的数据结构，但是该题的解题思路非常的关键和重要
image.png
对于该题的解决思路关键在于两点，一点就是判断是否还可以走圈，第二走圈需要几步？
判断是否需要走圈，书中是这样得到判断条件的
image.png
对于走圈需要几步，书中是这样得到判断条件的
image.png
image.png
下面为代码和注释部分：
该题可以有递归的解法，为了便于理解其逻辑性，采用如下的方法
import numpy as np
from numpy import *
class solution(object):
def __init__(self,mat_number):
self.mat_number=mat_number
def print_matrix(self):
arr=[]#用于存放顺时针打印出的数字
rows=int(np.shape(self.mat_number)[0])#得到行数
print (rows)
columns=int(np.shape(self.mat_number)[1])#得到列数
print(columns)
starts=0#开始的圈的起始点
if self.mat_number==[]:
return []#两个鲁棒性
while rows>starts*2 and columns>starts*2:#书中得出的走圈的前提条件
endx=columns-1-starts#进行四步走的时候，遍历的最后一列的索引值
endy=rows-1-starts#进行四步走的时候，遍历的最后一行的索引值
for i in range(starts,endx+1):
num=self.mat_number[starts][i]#第一行的每一个数
arr.append(num)#将其加入到列表中
"""
不管怎么样，第一步从左到右都是必须的，只要矩阵不为空
因此不需要if 判断
"""
if starts<endy:#说明此时是有两列的，因此，可以由上往下走
for i in range(starts+1,endy+1):
num=self.mat_number[i][endx]
arr.append(num)
if starts<endx and starts<endy:#首先要确保至少有两行，其次确保至少有两列
for i in range(endx-1,starts-1,-1):#从后往前遍历，即走圈的第三步
num=self.mat_number[endy][i]
arr.append(num)
if starts<endx and starts<endy-1:#必须保证有两行以上
for i in range(endy-1,starts,-1):
num=self.mat_number[i][starts]
arr.append(num)
starts+=1#切记最后改变第一个起始点的位置坐标
return arr
def main():
mat_number=np.mat(np.arange(16).reshape((4,4)))
s=solution(mat_number)
print (s.print_matrix())
if __name__=='__main__':
main()
题19--包含min函数的栈
定义栈的数据结构，请在该数据结构中实现一个能够得到最小值的min函数，调用min,pop,push的时间度为O(1)
此题的含义可以解释如下：
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
假设压入栈的所有数字均不相等。
例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，
但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
下面为代码部分
class solution(object):
def IsPopOrder(self, pushV, popV):
if pushV == [] or popV == []:
return False
stack = []
for i in pushV:
stack.append(i)
if stack[-1] != popV[0]:
continue
else:
stack.pop()
popV.pop(0)
while len(stack) > 0 and stack[-1] == popV[0]:
stack.pop()
popV.pop(0)
if len(stack) == 0:
return True
else:
return False
def main():
s=solution()
pushV = [1, 2, 3, 4, 5]
popV = [4, 5, 3, 2, 1]
print (s.IsPopOrder(pushV,popV))
if __name__=='__main__':
main()
