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 code

Three, 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 code

Second, 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 codeRun the Autopep methodAfter running, watch carefullyIt is very convenient to use, configuration is not difficult to help you code readability and beauty oh.

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