Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.
First, write first
I heard you’re still writing a two-layer for loop to solve the sum of two numbers?
LeetCode 2: Sum of two numbers transfer gate: the median of two sorted arrays, “most” technical solution!
LeetCode 第 3 题 : Longest loop transport gate: Horse-and-cart algorithm to solve longest loop! Manacher
LeetCode 4 题 conversion of string to integer (ATOI) : Solve ATOI with “foolish old man removing mountains” method, think clever!
Continue solving LeetCode, the longest public prefix
One of LeetCode’s “most classic” algorithm problems: the sum of three numbers
The sum of the nearest three numbers, wonderful
LeetCode: Valid parentheses
Delete duplicates in LeetCode: delete duplicates in LeetCode
The container that holds the most water is the container that holds the most water
LeetCode 11 string multiplication: LeetCode string multiplication, what do you do?
LeetCode reverses the string. I’m cheating again!
LeetCode013: Reverses the word III in the string
LeetCode reverse string transfer gate: LeetCode next problem, product of arrays other than itself
Duplicate element transfer gate: Draw a diagram of the process with duplicate elements
Today I would like to share with you LeetCode arrays and strings. Question 16: Spiral matrix, and question 17: Spiral matrix ⅱ are born for the interview. I am looking forward to your participation.
Here’s another Python skill: using autopep8.
“Use the utility in the API is recommended in the project. But if you Use it in an interview, You will definitely fail.”
Part 1
Two, today’s first question
Given a matrix containing m x n elements (m rows, n columns), return all elements in the matrix in a clockwise spiral order.
Example:
Input: [[1.2.3 ],
[ 4.5.6 ],
[ 7.8.9] output: [1.2.3.6.9.8.7.4.5] Input: [[1.2.3.4],
[5.6.7.8],
[9.10.11.12] output: [1.2.3.4.8.12.11.10.9.5.6.7]
Copy the codeThree, the analysis
This topic, looks relatively simple, but the difficulty is still some, and a little bit big, a simple think, is not to turn around? You start with the first element and go around, and each time you go around, the radius of the circle decreases by one, and you go around until you encounter a repeating element, yeah, that’s the idea. How do you do that? Would you? Take a look at the diagram below
Fourth, the problem solving
Superficially, time complexity: O(n) Space complexity: O(n) (1) code
class Solution(object) :
def spiralOrder(self, matrix) :
""" :type matrix: List[List[int]] :rtype: List[int] """
row = len(matrix) # line number
col = len(matrix[0]) if row > 0 else 0 # column number
total = row * col # number of elements
ans = [] # store results
i = 0
while len(ans) < total:
# go right, I stays the same
for rightcol in range(i, col - i):
ans.append(matrix[i][rightcol])
downrow = -1 # Out-of-bounds marking
# go down, rightcol unchanged
for downrow in range(i + 1, row - i):
ans.append(matrix[downrow][rightcol])
if downrow == -1:
break
icol = -1
# Go left, downrow unchanged
for icol in range(rightcol - 1, -1 + i, -1):
ans.append(matrix[downrow][icol])
if icol == -1:
break
# Go up, ICOL unchanged
for uprow in range(downrow - 1, i, -1):
ans.append(matrix[uprow][icol])
i += 1 # Circle down one space
return ans
Copy the code(2) Submit the results
Test data: 22 groups running time: 24ms beat percentage :99.71%
Part 2
1, today’s second question
Given a positive integer n, generate a square matrix containing all elements from 1 to n^2 in a clockwise spiral order.
Example:
Input:3Output: [[1.2.3 ],
[ 8.9.4 ],
[ 7.6.5]]Copy the codeSecond, the analysis
This problem, which is the exact reverse of the last problem, goes from a two-dimensional matrix to a one-dimensional matrix, from a one-dimensional matrix to a two-dimensional matrix, and the same thing is that the data is given,
Third, the problem solving
Superficially, time complexity: O(n) Space complexity: O(n) (1) code
class Solution(object) :
def generateMatrix(self, n) :
""" :type n: int :rtype: List[List[int]] """
ans = [[0] * n for i in range(n)] # Helical matrix
total = n * n # total number of elements
i = 0 # start subscript
j = 1 # Record element values
while j <= total:
# right
for rightcol in range(i, n - i):
ans[i][rightcol] = j
j += 1
downrow = -1 # Out-of-bounds marking
# come on down
for downrow in range(i + 1, n - i):
ans[downrow][rightcol] = j
j += 1
if downrow == -1:
break
icol = -1
# left.
for icol in range(rightcol - 1, -1 + i, -1):
ans[downrow][icol] = j
j += 1
if icol == -1:
break
# going up
for uprow in range(downrow - 1, i, -1):
ans[uprow][icol] = j
j += 1
i += 1 # Circle minus one
return ans
Copy the code(2) Submit the results
Test data: 20 groups running time: 28ms beat percentage :98.21%
Part 3
Skills: Using the Python automatic specification code autopep8
(1) Module installation
pip install outopep8
Copy the code(2) Configure Pyecharm
Pycharm – > File – > Setting – > Tools – > External Tools autopep8 Arguments : –in-place –aggressive –aggressive $FilePath$ Working directory : $FileDir$ Output filters : $FILE_PATH$\:$LINE$\:$COLUMN$\:.*
(3) Practical application
Example source code
I believe that adhere to, there will always be harvest, I do not harvest your support!
The idea is complex, the implementation is fun. As long as you don’t give up, there will be famous day. — “Old Watch doggerel”
Like to see the message forwarding, four support, the original is not easy. Ok, see you next time, I love the cat love technology, more love si si’s old cousin Da Mian ଘ(˙꒳˙)ଓ Di Di