python 数据结构习题
旋转图像
给定一个n×n的二维矩阵表示一个图像。将图像顺时针旋转90度。你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。例如，给定matrix=[[1，2，3]，[4，5，6]，[7，8，9]]，原地旋转输入矩阵，使其变为[[7，4，1]，[8，5，2]， [9，6，3]]。要求设计满足题目条件的如下方法： def rotate(self， matrix: List[List[int]]) -> None:
输入用例3 1 2 3 4 5 6 7 8 9
输出用例7 4 1 8 5 2 9 6 3
输入用例4 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
import sys
def rotate(matrix):
n = len(matrix)
for i in range(n): # 主对角线翻转
for j in range(n - i):
matrix[i][j], matrix[n - j - 1][n - i - 1] = matrix[n - j - 1][n - i - 1], matrix[i][j]
for i in range(n // 2): # 水平翻转
for j in range(n):
matrix[i][j], matrix[n - i - 1][j] = matrix[n - i - 1][j], matrix[i][j]
def matrixStr(M):
s = ''
for vec in M:
s += ' '.join(map(str, vec))
s += '\n'
return s
if __name__ == '__main__':
m = int(sys.stdin.readline())
A = []
for i in range(m):
A.append(list(map(int, sys.stdin.readline().split(' ')))) # 读入矩阵\n
rotate(A)
print(matrixStr(A))
实现strStr()
给定一个haystack字符串和一个needle字符串，在haystack字符串中找出needle字符串出现的第一个位置（从0开始），如果不存在则返回-1。例如，输入 haystack="hello"，needle="ll"，输出结果为2。要求设计满足题目条件的如下方法： def strStr(self， haystack: str， needle: str) -> int:
输入用例hello ll
输出用例2
输入用例aaaa bba
输出用例-1
import sys
def strStr(haystack, needle):
count = 0
for i in needle:
if i in haystack:
count = count + 1
if i not in haystack:
count = count - 1
print(count)
if __name__ == '__main__':
m = sys.stdin.readline()
f = sys.stdin.readline()
strStr(m,f)
螺旋矩阵II
给定一个正整数n，生成一个包含1到n
2
所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。例如，输入3，输出结果如下： [ [ 1, 2, 3 ], [ 8, 9, 4 ], [ 7, 6, 5 ] ] 要求设计满足题目条件的如下方法： def generateMatrix(self,n:int)->List[List[int]]:
输入用例12
输出用例[[1, 2, 3], [8, 9, 4], [7, 6, 5]]
输入用例6
输出用例[[1, 2, 3], [8, 9, 4], [7, 6, 5]]
class Solution:
def generateMatrix(self, n):
# 顺时针方向（右下左上）
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
dn = 0 # 方向指针\n
res = [[0] * n for _ in range(n)] # 初始化\n
x = y = 0 # 位置\n
for i in range(1, n * n + 1):
res[x][y] = i # 下一步位置\n
temp_x = x + dx[dn]
temp_y = y + dy[dn] # 判断下一步位置是否合理，若合理则更新位置，若不合理则改变方向并更新位置\n
if 0 <= temp_x < n and 0 <= temp_y < n and res[temp_x][temp_y] == 0:
x, y = temp_x, temp_y
else:
dn = (dn + 1) % 4
x += dx[dn]
y += dy[dn]
return res
test = Solution()
n = 3
test.generateMatrix(n)
print(test.generateMatrix(n))