《剑指offer》---顺时针打印矩阵

本文算法使用python3实现

1. 问题1

1.1 题目描述：

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

输入矩阵为 $$ \begin{bmatrix} 1 & 2 & 3 & 4 \ 5 & 6 & 7 & 8 \ 9 & 10 & 11 & 12 \ 13 & 14 & 15 & 16 \ \end{bmatrix} $$

输出为1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10

时间限制：1s；空间限制：32768K

1.2 思路描述：

（1）将矩阵第一行加入result中，同时删除第一行。

（2）对剩余矩阵进行逆时针旋转90度，继续取其第一行

（3）直到矩阵被删除为空为止。

1.3 程序代码：

class Solution:

	def printMatrix(self, matrix):

         # 每次将矩阵第一行加入result列表

		result = []

		while matrix:

			result += matrix.pop(0)

			if not matrix :

				break

			matrix = self.turnMatrix(matrix)

		return result

	def turnMatrix(self, matrix):

        # 对矩阵进行逆时针旋转90度操作

		rows = len(matrix)

		cols = len(matrix[0])

		resMatrix = []

		for j in range(cols):

			temp = []

			for i in range(rows):

				temp.append(matrix[i][j])

			resMatrix.append(temp)

		resMatrix.reverse()

		return resMatrix

2. 问题2

2.1 题目描述：

顺时针旋转填充数组。

输入为1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16

输出矩阵为 $$ \begin{bmatrix} 1 & 2 & 3 & 4 \ 12 & 13 & 14 & 5 \ 11 & 16 & 15 & 6 \ 10 & 9 & 8 & 7 \ \end{bmatrix} $$

时间限制：1s；空间限制：32768K

2.2 思路描述：

（1）给一个 $ m \times n $ 的矩阵，和矩阵的开始坐标 $ x、y $，顺序填充该矩阵的最外围边缘。

（2）不断缩小矩阵的规模（每次高度和长度各减少2），直到 $ m $ 和 $ n $ 有一个为0，则说明该填充结束。

（3）当 $ m < n $ 时，最后一次剩余的不再是一个矩阵，而是一行，需要单独定义如何填充。

\[\begin{bmatrix} 1 & 2 & 3 & 4 \\ 10 & 11 & 12 & 5 \\ 9 & 8 & 7 & 6 \\ \end{bmatrix}
\]

（4）当 $ m > n $ 时，最后一次剩余的不再是一个矩阵，而是一列，同样也需要单独定义如何填充。

\[\begin{bmatrix} 1 & 2 & 3 \\ 10 & 11 & 4 \\ 9 & 12 & 5 \\ 8 & 7 & 6 \\ \end{bmatrix}
\]

2.3 程序代码：

class Solution():

	def FillMatrix(self, m, n, count):

		# 创建 m*n的列表

		matrix = [[0]*n for i in range(m)]

		x = 0; y = 0; cnt =1

		while m>0 and n>0:

		 	if m == 1:

		 		for k in range(y, y+n):

		 			matrix[x][k] = cnt

		 			cnt += 1

		 		break

		 	if n == 1:

		 		for k in range(x, x+m):

		 			matrix[k][y] = cnt

		 			cnt += 1

		 		break

		 	matrix, cnt = self.FillEdge(x, y, m, n, cnt, matrix)

		 	x += 1

		 	y += 1

		 	m -= 2

		 	n -= 2

		return matrix

	def FillEdge(self, x, y, m, n, cnt, matrix):

		i = x; j = y

		while j < y+n-1:

			matrix[i][j] = cnt

			j += 1

			cnt += 1

		while i < x+m-1:

			matrix[i][j] = cnt

			i += 1

			cnt += 1

		while j > y:

			matrix[i][j] = cnt

			j -= 1

			cnt += 1

		while i > x:

			matrix[i][j] = cnt

			i -= 1

			cnt += 1

		return matrix, cnt

巴特西