1, Definition of array
An array is a collection of data of the same type stored in a continuous memory space
2, Attention
(1) Subscript index: array subscripts start from 0
(2) Memory space address continuity: when deleting or adding elements, the addresses of other elements 3 should be moved
(3) The elements of the array cannot be deleted and can only be overwritten
3, Loop invariant rule
Loop ---- > boundary treatment ---- > definition of interval ---- > invariant
4, Classic array topic
Four classic array topics, each topic represents a type and an idea.
1. Binary search
(1) Example 704. Binary search
(2) Train of thought
1. The premise is that the array is an ordered array. At the same time, the title also emphasizes that there are no duplicate elements in the array, because once there are duplicate elements, the element subscript returned by binary search method may not be unique.
2. Loop invariant rule: generally, the left closed right closed interval is adopted, that is [left, right].
**3. Note: while left < = right:**
4. Note that return -1 should not be put into else, so that when the target does not exist, it will return None instead of - 1
(3) Complexity analysis:
Time complexity: O(logn)
Space complexity: O(1)
(4) Code
def search(self, nums: List[int], target: int) -> int:
left = 0
right = len(nums) - 1
while left <= right: # Candidate area has value
mid = (left + right) // 2
if nums[mid] > target:
right = mid -1
elif nums[mid] < target:
left = mid + 1
else:
return mid
return -1 # Change according to the meaning of the question(5) Related topic recommendation (force buckle)
35. Search insertion position – explain
- 34. Find the first and last positions of elements in the sorted array [medium]
- Square root of 69.x
- 367. Effective complete square
(6) Summary
🐷 Note the return statement after the while loop ends
2. Double finger needling
(1) Example 27. Remove element
(2) Train of thought
**Double finger needle method (fast and slow pointer method): * * complete two for loops under one for loop through one fast pointer and one slow pointer. [constant level space complexity]
🌿 1. Ordinary double pointer
(3) Complexity analysis:
Time complexity: O(n), where n is the length of the sequence. You only need to traverse the sequence up to two times.
Space complexity: O(1)
(4) Code
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
n = len(nums)
left = 0 # left is a slow pointer pointing to the next position to be output
for right in range(n): # right is a fast pointer to the element currently to be processed (traversal)
if nums[right] != val: # Then nums[right] must be output and placed in the left position
nums[left] = nums[right]
left += 1 # The left and right pointers move to the right at the same time (the right pointer moves to the right automatically in a cycle)
# When num [right] = = Val: only the right pointer moves to the right automatically because of the loop
return left # The value of left is the length of the array to be output2. Double pointer optimization
Complexity analysis:
Time complexity: O(n), where n is the length of the sequence. You only need to traverse the sequence once.
Space complexity: O(1)
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
n = len(nums)
left = 0 # The two pointers are initially at the beginning and end of the array, moving to the middle to traverse the sequence
right = n - 1
while left < right: # When the left and right pointers coincide, all elements in the array are traversed
if nums[left] == val:
nums[left] = nums[right-1]# Copy the element pointed to by right to the left position, that is, delete the original value at the left position
right -= 1 # right shift left one bit
left += 1 # left shift right one bit
return left
~~Num [left] = num [right] ~ ~ why not this sentence???
(5) Related topic recommendation (force buckle)
- 26. Remove duplicates from the sort array
- 283. Move zero
- 844. Compare strings with backspace
- 977. Square of ordered array
(6) Summary
🐷 left is a slow pointer pointing to the next position to be output;
🐷 right is a fast pointer to the element currently to be processed
🐷 The value of left is the length of the array to be output
🐷 Use O(1) extra space and In situ Modify the input array.
- Ordinary double finger acupuncture:
🎍 The relative position of the element has not changed
🎍 Both the left and right pointers start at 0
🎍 for loop traverses right (it can also be changed to while loop)
🎍 You only need to traverse the sequence up to two times
- Double pointer Optimization:
🎍 The relative position of the element has changed
🎍 The left pointer starts from 0 and the right pointer starts from n-1; Move to the middle and traverse the sequence.
🎍 while loop left < right
🎍 You only need to traverse the sequence one more time
🎍 Avoid repeated assignment of elements that need to be retained
3. Extension of double pointer method
The double pointer method optimizes the solution of time complexity O(n^2) to O(n). In other words, it is reduced by one order of magnitude. The title is as follows:
Double pointers to record the front and back pointers to reverse the linked list:
Use the double pointer to determine the ring:
3. General solution
(1) Examples 26. Remove duplicates from the sort array
(2) Train of thought
"General solution" is a method for "data is orderly, and the same element reserves k bits at most"
- Since K identical numbers are reserved, we can directly retain the first k numbers.
- For any subsequent number, the premise that it can be retained is to compare it with the k-th element in front of the current write position. If it is different, it will be retained.
Complexity analysis
Time complexity: O(n)
Space complexity: O(1)
🌿 code
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
def process(nums, k): # Keep k same numbers
idx = 0 # idx, pointing to the position to be inserted
# IDX < K: keep the first k numbers directly
# nums[idx-k] != x: Keep the number different from the first k numbers
for x in nums:
if idx < k or nums[idx-k] != x:
nums[idx] = x
idx += 1
return idx
return process(nums, 1) #Call function (3) Related topic recommendation (force buckle)
4. Sliding window
(1) Examples
(2) Idea:
Sliding window: constantly adjust the start position and end position of the subsequence, so as to get the results we want.
The subtlety of sliding window is to continuously adjust the starting position of subsequence according to the current subsequence and size. Thus, the violent solution of O(n^2) is reduced to O(n).
Detailed process:
Two pointers start and end are defined to represent the start position and end position of the sub array (sliding window) respectively. The maintenance variable sum stores the sum of elements in the sub array (that is, the sum of elements from num [start] to num [End]).
In the initial state, both start and end point to the subscript 0, and the value of sum is 0.
In each iteration, add num [End] to sum. If sum ≥ s, update the minimum length of the sub array (at this time, the length of the sub array is end − start+1), then subtract num [start] from sum and move start right until sum < S. in this process, also update the minimum length of the sub array. At the end of each iteration, move end right.
(3) Complexity analysis
Time complexity: O(n), where n is the length of the array. The pointers start and end can be moved up to N times each.
Space complexity: O(1).
(4) Code
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
if not nums: # Array is empty
return 0
n = len(nums)
start = end = 0 # The starting position pointer of the sliding window is start; End position pointer end
sum = 0 # Sum stores the sum of successive subarrays, with an initial value of 0
res = n + 1 # res stores the minimum length of the subarray, and the initial value is a larger impossible value
# perhaps res = float("inf") # Define an infinite number
while end < n:
sum += nums[end]
while sum >= target: # sum may want to loop minus num [start], so use while instead of if
res = min(res, end - start + 1) # Minimum length of update subarray
## Ready to shrink the sliding window
sum -= nums[start] # Subtract num [start] from sum until sum < target
start += 1 # The start pointer moves to the right to narrow the window
end += 1 # The end pointer moves to the right to traverse the array
return 0 if res == n + 1 else res # If res == n + 1, there is no such subarray(5) Related topic recommendation (force buckle)
- 904. The fruit basket [medium] problem is not understood??
- 76. Minimum coverage substring [difficult] skip??
(6) Summary
- Define an infinite number
res = float("inf")
# Or the array length is exceeded
res = n + 1 - Minimum length representation of subarray
end - start + 1
- Minimum length of update subarray
res = min(res, end - start + 1) # Built in min function, unknown complexity ## Compared with the two, the following ternary writing method can be adopted res = res if res < end - start + 1 else end -start + 1
- The key to solving the problem is how to move the starting position of the window, that is, the second while loop
5. Simulation method
(1) Examples
(2) Train of thought
This problem does not involve any algorithm, but the simulation process.
Method: layer by layer simulation
The matrix can be regarded as several layers, first fill in the elements of the outermost layer of the matrix, then fill in the elements of the sub outer layer of the matrix, until fill in the elements of the innermost layer of the matrix.
The k-th layer of the definition matrix is all vertices with a distance of K from the nearest boundary. For example, the outermost elements of the matrix in the figure below are all layer 1, the sub outer elements are all layer 2, and the innermost elements are all layer 3.
[[1, 1, 1, 1, 1, 1],
[1, 2, 2, 2, 2, 1],
[1, 2, 3, 3, 2, 1],
[1, 2, 3, 3, 2, 1],
[1, 2, 2, 2, 2, 1],
[1, 1, 1, 1, 1, 1]]
For each layer, fill in all elements in clockwise order from the top left. Assuming that the upper left corner of the current layer is located at (top,left) and the lower right corner is located at (bottom,right), fill in the elements of the current layer in the following order.
- Fill in the upper elements from left to right, from (top,left) to (top,right). Fill in the right element from top to bottom, from (top+1,right) to (bottom,right).
- If left < right and top < bottom, fill in the lower elements from right to left, followed by (bottom,right − 1) to (bottom,left+1), and fill in the left elements from bottom to top, followed by (bottom,left) to (top+1,left).
- After filling in the elements of the current layer, increase left and top by 1 respectively, and decrease right and bottom by 1 respectively. Enter the next layer and continue to fill in elements until all elements are filled in.
(3) Complexity analysis
Time complexity: O(n2), where n is a given positive integer. The size of the matrix is n × n. Each element in the matrix needs to be filled in.
Space complexity: O(1). In addition to the returned matrix, the spatial complexity is constant.
(4) Code
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
matrix = [[0]*n for _ in range(n)] # Initialize an n x n square matrix with all zeros
left, right, top, bottom = 0, n-1, 0, n-1
num = 1 # num is the filling element, and the initial value is 1
while left <= right and top <= bottom: # boundary condition
# Traverse the [left, right] column of the top row from left to right
for col in range(left, right+1):
matrix[top][col] = num
num += 1
# Traverse the [top+1,bottom] row of the right column from top to bottom. Note that range is a left closed and right open interval
for row in range(top+1, bottom+1):
matrix[row][right] = num
num += 1
# Traverse the lower elements from right to left, from (bottom,right − 1) to (bottom,left+1)
for col in range(right-1,left, -1):
matrix[bottom][col] = num
num += 1
#Traverse the left element from bottom to top, from (bottom,left) to (top+1,left)
for row in range(bottom, top, -1):
matrix[row][left] = num
num += 1
#Increase left and top by 1 respectively, and decrease right and bottom by 1 respectively. Enter the next layer and continue to traverse until all elements are traversed.
left += 1
top += 1
right -= 1
bottom -= 1
return matrix(5) Related topic recommendation (force buckle)
-
54. Spiral matrix [medium]
-
Sword finger Offer 29 Print matrix clockwise
(6) Summary
-
Output in reverse order [large number first, decimal number last, left closed and right open]
for i in range(5,2,-1): print(i) # output 5 4 3 -
Set the boundary value and adhere to the principle of loop invariants [close left and open right]
When simulating by layer, each color represents an edge. The processing rules at each corner can be different, but it is best to follow the rules of closing left and opening right to prevent confusion. As shown in the figure:
[the external chain image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-6enwxz4t-1627466108622) (/ users / Yangying / library / Application Support / typora user images / image-20210601181227390. PNG)]
Don't understand 54 Why must an if judgment statement be added to the spiral matrix? If not, there will be an error?
And 59 Spiral matrix II will not make an error with or without if judgment statement??
I don't understand why I close left and open right is different from what they say??