-
Notifications
You must be signed in to change notification settings - Fork 0
/
test_leetcode.py
82 lines (67 loc) · 2.57 KB
/
test_leetcode.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
from typing import List
import math
import collections
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def list_to_link(_list):
result_node = ListNode(_list[0])
node_tmp = result_node
for i in range(1, len(_list)):
node_tmp.next = ListNode(_list[i])
node_tmp = node_tmp.next
return result_node
def buildTree(preorder: List[int], inorder: List[int]) -> TreeNode:
def build(_preorder, pre_left, pre_right, _inorder, in_left, in_right):
if pre_left > pre_right or in_left > in_right:
return
# # 下面的判断可以节省一次递归,但是不加不影响最终结果
# if pre_left == pre_right:
# return TreeNode(preorder[pre_left])
# 前序的第一个结点一定是当前子树的根结点
tmp_root_data = _preorder[pre_left]
root = TreeNode(tmp_root_data)
# 查找结点在中序的位置,可以使用哈希表优化查找
in_root_idx = _inorder.index(tmp_root_data)
root.left = build(_preorder, pre_left + 1, pre_left + in_root_idx - in_left, _inorder, in_left,
in_root_idx - 1)
root.right = build(_preorder, pre_left + in_root_idx - in_left + 1, pre_right, _inorder, in_root_idx + 1,
in_right)
return root
return build(preorder, 0, len(preorder) - 1, inorder, 0, len(inorder) - 1)
#
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
# 原地旋转
# 借助一个数
# rows = 0
# cols = 0
n = len(matrix)
if n % 2 == 0:
rows = n // 2 # 行数
cols = n // 2 # 列数
else:
rows = (n + 1) // 2 - 1
cols = (n + 1) // 2
print(rows,cols)
for i in range(rows):
for j in range(cols):
tmp = matrix[i][j]
matrix[i][j] = matrix[n - j - 1][i]
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]
matrix[j][n-i-1] = tmp
return matrix
nums = [[1,2,3],[4,5,6],[7,8,9]]
ans = Solution().rotate(nums)
print(ans)