Leetcode topic - array

---

Preface

An array is a collection of the same type of data stored in continuous memory space .
Two things to note are ：
1. Array subscripts are all from 0 At the beginning .
2. The address of array memory space is continuous .
It is precisely because the addresses of the array in the memory space are continuous , So when we delete or add elements , It's hard to avoid moving the addresses of other elements .

One 、LeetCode—— Two points search

If an array is given in the title , And there are search operations , Give priority to binary search , Binary search method is a faster way to find , In most cases, binary search is basically used on the premise that the array is orderly . But it is also used in the case of disorder .

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left,right = 0,len(nums)-1
        while left<=right:
            mid = left+(right-left)//2 # To prevent spillage , You can use this as a fixed way to find the middle subscript 
            if nums[mid] == target: # If the middle value is equal to the target value , return mid
                return mid
            elif nums[mid] < target: # If it's less than the target , Then continue the recursive search on the right half 
                left = mid+1
            else:	# If it's greater than the target value , Then continue to search recursively on the left half 
                right = mid-1
        return -1

This topic is relatively simple , It can be seen as the basis of array . Binary search is also often done by recursion , The general idea is the same as the above .

Two 、LeetCode—— Remove elements

It can be said that there is no explicit operation to delete elements in the array ,, If you want to delete an element , Just overwrite this element , The method of overwriting is to move the elements behind the array forward .

1. Violence solution

Traversal array , When encounter is equal to x situations , Let the elements after this position move forward one position in turn . Because the elements that need to be deleted may be adjacent , therefore i Also one ahead .

//  Time complexity ：O(n^2)
//  Spatial complexity ：O(1)
class Solution {
    
public:
    int removeElement(vector<int>& nums, int val) {
    
        int size = nums.size();
        for (int i = 0; i < size; i++) {
    
            if (nums[i] == val) {
     //  Find the elements that need to be removed , Just move the array forward one bit 
                for (int j = i + 1; j < size; j++) {
    
                    nums[j - 1] = nums[j];
                }
                i--; //  Because the subscript i All the later values are moved forward by one bit , therefore i Also move forward one bit 
                size--; //  The size of the array -1
            }
        }
        return size;

    }
};

2、 Double finger needling

Double pointer is a very efficient idea , It is often used in arrays and linked lists .
In this question , We can define two pointers slow and fast, When the current element is not equal to x when , These two pointers move backward together , Be equal to x when ,fast Pointer backward ,slow The pointer doesn't change . And then use fast The element pointed to by the pointer is overwritten slow The element that the pointer points to . After the traversal is over , The length of the array is slow.

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        slow = fast = 0 # Initialization is 0
        while fast<len(nums):
            if nums[fast]!=val: # When you don't wait , Move backward together ; On equal terms ,slow unchanged ,fast Move backward 
                nums[slow]=nums[fast]
                slow+=1
            fast+=1
        return slow # Returns the length of the array 

3、 ... and 、LeetCode—— The square of an ordered array

1、 Violence solution

The solution to violence is simple , Not much explanation

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            nums[i] *= nums[i]
        nums = sorted(nums)
        return nums

2、 Double finger needling

'''  Double pointer method , Create an additional array to store the returned results .  Because the original array has been ordered , So the largest number after the square is either the first element or the last element in the original array .  Put the biggest on res Last position in array , Traverse in turn  '''
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        i,j,k = 0,len(nums)-1,len(nums)-1
        res = [-1]*len(nums)
        
        while i<=j:
            lm = nums[i]*nums[i]
            rm = nums[j]*nums[j]
            if lm > rm:
                res[k] = lm
                i += 1
            else:
                res[k] = rm
                j -= 1
            k -= 1
        return res

Four 、LeetCode—— Minimum length array

1、 Violence solution

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        res = float('inf') #res Initialize to infinity 
        sum,sublenth = 0,0 #sum For the current and ,sublenth Is the length of the qualified sequence 
        for i in range(0,len(nums)): #i Is the starting point of the subsequence 
            sum = 0
            for j in range(i,len(nums)): #j Is the end position of the subsequence 
                sum += nums[j]
                if sum>=target: # If the requirements are met , Calculate the length of the current sequence , And with res Compare 
                    sublenth = j-i+1
                    res = min(res,sublenth)
                    break # Just find one that meets the requirements , Just break
        return res if res != float('inf') else 0 # If res Not assigned , Just go back to 0

2、 The sliding window （ Double finger needling ）

So called sliding window , It's constantly adjusting the starting and ending positions of subsequences , So we can get the result that we want to think about .
In this topic, we realize the sliding window , The main points are as follows ：

1. What's in the window ？
2. How to move the start of a window ？
3. How to move the end of a window ？

The window is Satisfy it and ≥ s The smallest length of Continuous subarray .

How the start of the window moves ： If the value of the current window is greater than s 了 , The window is about to move forward （ It's time to shrink ）.

How the end of the window moves ： The end of the window is the pointer that traverses the array , Set the starting position of the window as the starting position of the array .

'''  The sliding window  '''
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:

        res = float('inf')
        subLenth = 0
        sum,index = 0,0  #sum For the current array element and ,index Is the starting position of the sliding window 
        for i in range(len(nums)):# The end position of the sliding window is the pointer traversing the array 
            sum += nums[i]
            while sum>=target:
                subLenth = i-index+1
                res = min(subLenth,res)
                sum -= nums[index] # Constantly changing the starting position of the sequence 
                index += 1
        return 0 if res==float("inf") else res

5、 ... and 、LeetCode—— Find the first and last positions of the elements in the sort array

Use two bisections to find , A binary search to find the left boundary , The other is to find the right boundary .
This question can be divided into three situations ：

1. target stay nums[0] ~ nums[n-1] in ,nums in target. for example nums = [5,7,7,8,8,10],target = 8, return [3,4].
2. target stay nums[0] ~ nums[n-1] in ,nums Does not exist in the target. for example nums = [5,7,7,8,8,10],target = 6, return [-1,-1].
3. target < nums[0] perhaps target > nums[n-1]. for example nums = [5,7,7,8,8,10], target = 4, return [-1,-1].

Find the left boundary ：

 def searchLeft(nums,target): # Looking for the left boundary 
            left,right = 0,len(nums)-1
            while(left<=right):
                mid = left+(right-left)//2
                if nums[mid]<target:
                    left=mid+1
                else: 
                    right=mid-1
            if nums[left]==target: 
                return left
            else:
                return -1

Ordinary binary search is , When nums[mid] == target when , Go straight back to mid, And in this question , Is to continue to look to the left , See if there are any and target Equal array elements .
Find the right boundary

 def searchRight(nums,target): # Look for the right border 
            left,right = 0,len(nums)-1
            while(left<=right):
                mid = left+(right-left)//2
                if nums[mid]>target:
                    right=mid-1
                else:
                    left=mid+1
            if nums[right]==target:
                return right
            else:
                return -1

When nums[mid]=target when , All the way to the right , See if there are any and target Equal array elements .

Don't forget that there is another situation ：

 if len(nums)==0 or nums[0]>target or nums[-1]<target:
            return [-1,-1]

Complete code ：

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def searchLeft(nums,target): # Looking for the left boundary 
            left,right = 0,len(nums)-1
            while(left<=right):
                mid = left+(right-left)//2
                if nums[mid]<target:
                    left=mid+1
                else:
                    right=mid-1
            if nums[left]==target:
                return left
            else:
                return -1
        def searchRight(nums,target): # Look for the right border 
            left,right = 0,len(nums)-1
            while(left<=right):
                mid = left+(right-left)//2
                if nums[mid]>target:
                    right=mid-1
                else:
                    left=mid+1
            if nums[right]==target:
                return right
            else:
                return -1
        if len(nums)==0 or nums[0]>target or nums[-1]<target:
            return [-1,-1]
        lb = searchLeft(nums,target)
        rb = searchRight(nums,target)
        return [lb,rb]

6、 ... and 、LeetCode—— Spiral matrix

There is no algorithm idea in this topic , Mainly to examine logic .

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        matrix = [[0] * n for _ in range(n)]
        left,right,up,down = 0,n-1,0,n-1
        number = 1
        while left<right and up<down:
            for x in range(left,right):
                matrix[up][x] = number
                number += 1
            for y in range(up,down):
                matrix[y][right] = number
                number += 1
            for x in range(right,left,-1):
                matrix[down][x] = number
                number += 1
            for y in range(down,up,-1):
                matrix[y][left] = number
                number += 1
            
            left += 1
            right -= 1
            up += 1
            down -= 1
        # For odd numbers, you need to assign a value to the middle 
        if n%2 != 0:
            matrix[n//2][n//2] = number

        return matrix