数组的相关算法题

1. 螺旋矩阵

描述：
给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

示例:

输入: 3
输出:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]

解题思路：
模拟螺旋矩阵的生成方式，即先按照顺序在第一行从左到右生成，然后在最后一列从上到下生成，然后在最后一列从右到左生成，然后在第一列从下到上生成，彼此之间不能有交叉。但这样只能生成最外层的数，要想完整地生成矩阵我们可以每生成一整行或者一整列就把这一整行或一整列去掉，只对剩下的做如上生成操作。

代码：

def generateMatrix(n):
    ans = [[0 for _ in range(n)] for _ in range(n)]
    u, d, l, r = 0, n-1, 0, n-1
    num = 1
    while num <= n*n:
        for i in range(l, r+1):
            ans[u][i] = num
            num += 1
        u += 1  # 去掉这一行
        for j in range(u, d+1):
            ans[j][r] = num
            num += 1
        r -= 1  # 去掉这一列
        for m in range(r, l-1, -1):
            ans[d][m] = num
            num += 1
        d -= 1  # 去掉这一行
        for i in range(d, u-1, -1):
            ans[i][l] = num
            num += 1
        l += 1  # 去掉这一列
    return ans


n = 3
result = generateMatrix(n)
print(result)

2. 旋转图像

描述：
给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。

说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1:
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],

原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

示例2：
给定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],

原地旋转输入矩阵，使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]

解题思路：
找规律，将一个二维数组旋转后和原数组比较。得到规律，然后验证规律是否正确。首先以一个3*3的二维数组做测试：

before:

a[0][0]	a[0][1]	a[0][2]
a[1][0]	a[1][1]	a[1][2]
a[2][0]	a[2][1]	a[2][2]

after:

a[2][0]	a[1][0]	a[0][0]
a[2][1]	a[1][1]	a[0][1]
a[2][2]	a[1][2]	a[0][2]

以a[i][j]来表示二维数组的元素。基本上就是将二维数组的行转换成了列。稍有不同的是，转换后的列是倒序的。那么这道题就只需要简单的行列互换，然后将转换后的二维数组中的数组元素倒序一下就可以了。

def rotate(matrix):
	for i in range(len(matrix)):
		for j in range(i+1, len(matrix)):
			matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
		for i in range(len(matrix)):
			matrix[i].reverse()
		return