Sword finger offer array question type summary

Updating …

Category
1. Unordered array

Concept ： Unordered array
advantage ： Insert fast
shortcoming ： Search slow , Delete slowly , Fixed size
2. Ordered array

Concept ： The elements in the array are arranged according to certain rules .

advantage ： High search efficiency . You can use binary search when searching according to the element value , Much more efficient than unordered arrays , It is especially obvious when there is a large amount of data . about leetcode There are many topics for finding element classes in , If there is no prior explanation, it is an ordered array , You can sort the array in advance , Search again , Dichotomy or other methods can .

shortcoming ： Slow insertion and deletion . When inserting elements , First, determine the minor of the element , Then, all elements after the subscript are moved back to be inserted , So an ordered array is more suitable for frequent searching , However, there are few insert and delete operations .

1. Search in a two-dimensional array
Title Description ：

In a two-dimensional array （ Each one-dimensional array has the same length ）, Each row is sorted in ascending order from left to right , Each column is sorted in ascending order from top to bottom . Please complete a function , Enter such a two-dimensional array and an integer , Determine whether the array contains the integer .

Their thinking ：
Because the two-dimensional array is incremented from top to bottom , The particularity of increasing from left to right , Traversing the entire matrix to find is not the intention of this topic . Summing up the law, we can find that ： You should start from the upper right or lower left corner of the matrix .

Take the upper right corner as an example , First select the number in the upper right corner , If the number is equal to the number you are looking for , The search process ends ; If the number is greater than the number you are looking for , It means that other elements in the column are larger than the number to be searched , You can delete the column ; If the number is less than the number you are looking for , It means that other elements in the line are also smaller than the number to be searched , You can delete the line .

such , Each comparison can eliminate a row or a column , And narrow the search , The time complexity is O(n).

java Code ：

// Start at the bottom left corner and find 
class Solution{
    
	public boolean find(int [][]arrays,int target)
	{
    
		if(arrays==null)
			return false;
		int row=arrays.length;// Row number 
		int col=arrays[0].length;// Number of columns 
		for(int i=row-1,j=0;i>=0 && j<col;)
		{
    
			if(arrays[i][j]==target)
				return true;
			else if(arrays[i][j]>target) // It is impossible to be in this line 
				i--;
			else // It is impossible to be in this column 
				j++;
		}
		return false;
	}
}

2. Minimum number of rotation array

Title Description ：

Move the first elements of an array to the end of the array , We call it rotation of arrays . Enter a rotation of an array that is not sorted by subtraction , Output the smallest element of the rotation array . For example, an array of {3,4,5,1,2} by {1,2,3,4,5} A rotation of , The minimum value of the array is 1. All elements given are greater than 0, If the array size is 0, Please return 0.

Their thinking ：
If the entire array is ordered , Then we must think of using half search to realize . For rotating arrays , We found that , It can actually be divided into two sorted subarrays , And the elements of the preceding array are not smaller than those of the following array , And the minimum value is just the boundary between the two arrays , thus , We can get the following solution .

First use two pointers low and high Point to the first and last elements of the array respectively , Then you can find the middle element mid. For this intermediate element , There are two situations ：（1） This element is greater than or equal to low Pointing elements , At this point, the smallest element is specified in mid Behind , You can put low=mid;（2） The intermediate element is less than or equal to high Pointing elements , So the smallest element is mid Before , Sure high=mid. Particular attention ： Not here +1 perhaps -1, Because only in this way can we guarantee low Always in the first array ,high Always in the second array . In turn, cycle , At the end of the day low and high Difference between 1 when ,low Points to the last of the first array ,high Points to the first of the second array （ That is the minimum value we are looking for ）.

Obviously , The time complexity of the above search is O(logN).

java Code ：

public int minNumberInRotateArray(int [] array) {
    
        /*  Three situations ： （1） Put the front 0 Elements moved to the end , That is, sorting the array itself , The first is the minimum  （2） In general, binary search , When high-low=1 when ,high That's the minimum  （3） If the leading and trailing elements and the intermediate elements are equal , You can only search in order  */
        int len=array.length;
        if(len==0)
            return 0;
        int low=0,high=len-1;
        if(array[low]<array[high]) // Sort the array itself 
            return array[low];
        while(low<high){
    
            int mid=low+(high-low)/2;
            if(array[low]==array[mid] && array[high]==array[mid])
                return minInOrder(array);// In this case, you can only search in sequence 
            if(array[mid]>=array[low])
                low=mid;
            else if(array[mid]<=array[high])
                high=mid;
            if(high-low==1)
                return array[high];
        }
        return -1;
    }
    public int minInOrder(int [] array) {
     // In order to find 
         int min=array[0];
         for(int num:array){
    
             if(num<min)
                 min=num;
         }
          return min;
     }

3.K-Sum
​ Such questions usually give an array and a value , Let's find two in this array / Three /K The sum of the values is equal to the given value target.

Example ：TWO SUM（ Find the sum of two numbers in an array as the target value ）
for example ：target=5 arrays[5]={12,3,4,5,1} Array 1+4 Equal to the target value 5, Return their corresponding subscripts , Returns if it does not exist 0

Their thinking ：

1. Violence solution ： Most common , But it takes a long time , Only as an alternative ,

2.hash-map： Build a hash-map Loop through once

3.two-pointers： Position the size of the radical sum of two pointers to move the other . The number of pointers set here depends on K The number of .3Sum You can set 3 A pointer to the , Fix two , Move another .

// Violence law 
class Solution{
    
	public int Two_Sum(int arrays[],int target)
	{
    
		for(int i=0;i<arrays.length;i++)
		{
    
			for(int j=1;j<arrays.length;j++)
			{
    
				if(arrays[i]+arrays[j]==target)
				{
    
					return i,j;
				}
			}
		}
	}
}

c++ Code ：

bool hash_twosum(int *array,int len,int target,int *i,int *j)//i,j Subscript indicating the result , Start to 0
{
    
	map<int,int>index;  // Indexes 
	map<int,int>::iterator it;  // Value iterator 
	for(int x=0;x<len;x++)
	{
    
		index[array[x]]=x;// The array element is  11,12,13,14,15  Index index[11]=0 index[12]=1 index[13]=2 index[14]=3 index[15]=4
	}
	for(x=0;x<len;x++)
	{
    
		int other=target-array[x]; // Whether the remaining numbers are in the array 
		it=index.find(other); // If this index exists 
		if(it!=index.end()&& it!=index.find(array[x]))// If found or not to the end 
		{
    
			*i=x;
			*j=it->second;
			return true;
		}
	}
	return false;
}

// Double finger needling ：
class Solution{
    
	public int Two_Sum(int arrays[],int target)
	{
    
		int left=0;
		int right=arrays.length-1;
		while(left<right)
		{
    
			if(arrays[left]+arrays[right]==target)
				return left,right;
			else if(arrays[left]+arrays[right]<target)
				left++;
			else if(arrays[left]+arrays[right]>target)
				right--;
		}
	}
}

expand ： Look in the binary tree two sum
Their thinking ：
Middle order ergodic binary tree , Put the results into an array , Then use the double pointer to find

// Key code 
void inoder(BTREE T,vector<int> &a)
{
    
	if(T==NULL)
		return ;
	inoder(T->lchild,a);
	a.push_back(T->data);
	inoder(T->rchild,a);
}

bool findtarget(BTREE T,int target)
{
    
	vector<int> a;
	inoder<T,a>; //a Store node value 
	int left=0,right=n-1;
while(left<right)
{
    
	if(a[left]+a[right] ==target)
		return left,right;
	else if(a[left]+a[right] <target)
		left++;
	else if(a[left]+a[right] >target)
		right--;
	else 
		return true;
}
return false;
}

4. Determine whether there are duplicate numbers in the array
Their thinking ： use hash You can finish the table directly , If there are duplicate numbers , Then the counter adds 1

bool isrepeat(vector<int> &nums)
{
    
	map<int,int> dict;// use hash surface , The initial values are all 0
	for(num:nums)
	{
    
		dict[num]++;// Add the value of the corresponding subscript with the same number 1
		if(dict[num]>1)
			return true;
	}
	return false;
}

5. Interval problem
This kind of question usually gives an array containing multiple sub arrays , Then judge whether the intervals coincide true or false.

Problem solving skills ：

1. Press start Sort
2. In the previous interval end And the last interval start Find the intersection
Example :252 meeting room[easy]（https://leetcode.com/problems/meeting-rooms/）

Topic understanding ： Given an array , Include the start time and end time of each meeting [[s1,e1],[s2,e2],…], Judge whether a person can attend all the meetings .

test case:

Example1:

Input: [[0,30],[5,10],[15,20]]Output: falseExample2:Input: [[7,10],[2,4]]Output: true

Their thinking ： In this topic , If one person is going to attend all the meetings , Then all meetings should not coincide , So we just need to judge what the next meeting started start > At the end of the previous meeting end You can , If end>start, Just go back to false. First of all, we have to do the start Sort , And then judge start and end

class Solution{
    
 
    public boolean canAttendMeetings(Interval[] intervals){
    
 
        Arrays.sort(intervals,(x,y)->(x.start-y.start));
 
        //i from 1 Start , Because it involves judging the previous array end
 
        for (int i =1;i <intervals.length;i++){
    
 
            if (intervals[i-1].end > intervals[i].start){
    
 
                return false;
 
            }
        }
}

6. Subarray class topic

Such questions are usually in an array containing multiple subarrays , Sum up / product , Maximum, minimum, etc .
Problem solving skills ：

The sliding window （sliding window）

Example ：209 Minimum Size Subarray Sum[Medium]

Topic understanding ： Give us a number , Let's find that the sum of subarrays is greater than or equal to the minimum length of the given value

test case:

Input: s = 7, nums = [2,3,1,2,4,3]

Output: 2

explain ： Satisfy subarray and =7 The minimum length array of is [4,3], therefore output=2

Their thinking ： Find a number greater than or equal to this number target, Like this testcase in ,[2,3,1,2,4,3], Add from front to back , The sum of the first four terms is 8. Greater than 7 了 , But our target yes 7, The following items are all positive integers , Keep going back , It will certainly be greater than target7, So this time we put left Move the pointer one bit to the right , It is equivalent to a sliding window （sliding window）.

7. The smallest number of array output permutations
for example ： [2,23,234] The minimum result is 223234

Their thinking ： Because the numbers involved may overflow , So a string is more appropriate , Convert to string –> a+b b+a Compare 2 23–>23 2, Join smaller numbers together

#include<iostream>
#include<vector>
#include<string>
using namespace std;
static bool cmp(int a,int b)
{
    
	std::string A=std::to_string(a)+std::to_string(b);
	std::string B=std::to_string(b)+std::to_string(a);
	return A<B;
}
string print(vector<int> numbers)
{
    
	sort(numbers.begin(),numbers.end(),cmp);
	string s;
	for(int ai:numbers)
	{
    
		s+=to_string(ai);
	}
	return s;
}
int main()
{
    
	vector<int> numbers;
	print(numbers);
	return 0;
}

8. Remove duplicate numbers from an ordered array , Returns the length of a non repeating number
Their thinking ： Double finger needling （ Covering method ）

//i The index representing the old array ,index Represents the index of the new array , Move the non repeating numbers to the front one by one 
int remove(vector<int> &a)   
{
    
	int i,index;
	index=1;//index Is the index of the second number 
	if(a.empty())
		return 0;
	for(i=1;i<a.size();i++)//i and index Is the index of the second number 
	{
    
		if(a[i]!=a[index-1])   
		{
    
			a[index]=a[i];
			index++;// Record the number of non repeating numbers 
		}
	}
	return index;
}

9、 Adjust the order of the array so that the odd number comes before the even number
Their thinking ：
1. Use the new array to store the new order , Scan the array first , Store odd numbers in a new array , Scan the array again and store even numbers in the array . It's more space consuming , Don't suggest .
2. With a double pointer , If you find an odd number and an even number , Then swap them .

// Law 1 
#include<iostream>
#include<vector>
using namespace std;
void ReOrderArray(vector<int> &a)
{
    
	if(a.empty())
		return ;
	vector<int> result;
	for(int i=0;i<a.size();i++)
	{
    
		if(a[i]<<2==1)
			result.push_back(a[i]);
	}
	for(i=0;i<a.size();i++)
	{
    
		if(a[i]<<2==0)
			result.push_back(a[i]);
	}
	a=result;
}
int main()
{
    
	vector<int> a;
	int b[5]={
    1,2,3,4,5};
	for(int i=0;i<5;i++)
	{
    
		a.push_back(b[i]);
	}
	ReOrderArray(a);
	for(i=0;i<a.size();i++)
	{
    
		cout<<a[i]<<" ";
	}
	return 0;
}

Array permutation

Title Description ： For example, an array of [1,2,3]. The result of permutation and combination is [1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2],[1,2,3]

Ideas ： Think of the array as two parts , Part is the first number , The other part is all the numbers after the first number , Exchange the first number with all the following numbers in turn , A typical recursive idea ;

void Fun()
{
    
	int a[5]={
    1,2,3,4,5];
	permutations(a,0,4);
}
void permutations(int a[],int m,int n)
{
    
	if(m==n)
	{
    
		for(int i=0;i<=n;i++)
		{
    
			cout<<a[i];
		}
		cout<<endl;
	}
	else
	{
    
		for(int j=m;j<=n;j++)
		{
    
			int temp=a[m];
			a[m]=a[i];
			a[i]=temp;
			permutations(a,m+1,n);
			temp=a[m];
			a[m]=a[i];
			a[i]=temp;
		}
	}
}

expand ： If it is to find the permutation and combination of strings ？
If it is to find all combinations of strings ： For example, there are three characters a,b,c, Then their combination is a,b,c,ab,ac,bc,abc.