当前位置：网站首页>Algorithm interview high frequency problem solving guide [1]

Algorithm interview high frequency problem solving guide [1]

2022-07-24 03:36:00 【Choice～】

Blog home page ：choice~ The blog home page of
Welcome to pay attention to the likes and comments
This paper is written by choice~ original ,csdn First episode ！
Reference website ： Cattle from
Starting time ：2022 year 7 month 22 Japan
Your income is directly proportional to your irreplaceable
If you think the blogger's article is good , Please support the blogger for the third company
I'd like to introduce you to a job search question brushing harvest offer The place of Click to enter the website

Catalog

1.NC110 Rotated array

describe ：

discuss ：

Algorithm idea 1 ： Use extra arrays

Code display ：

Complexity analysis

Algorithm idea 2 ： Array flip

Their thinking ：

Code display ：

Complexity analysis

Algorithm idea 3 ： Array transformation

Code display ：

Complexity analysis

2.NC78 Reverse a linked list

describe ：

Solution 1 ： iteration

Java Reference code ：

Solution 2 ： recursive

C++ Reference code ：

Algorithm idea 3 ： Use extra stacks

Code display ：

1.NC110 Rotated array

describe ：

An array A There is n It's an integer , On the premise that no other array is allowed , Loop each integer to the right M（ M >=0） A place , the A The data in is from （A0 A1 ……AN-1 ） Transformation for （AN-M …… AN-1 A0 A1 ……AN-M-1 ）（ Last M The number loop moves to the front of M A place ）. If you need to consider the program to move data as little as possible , How to design a way to move ？

Data range ：0 < n \le 1000<n≤100,0 \le m \le 10000≤m≤1000

Advanced ： Spatial complexity O(1)O(1), Time complexity O(n)O(n)

This is a C Language gives OJ modular ：

/**
 *  Rotated array 
 * @param n int integer   The length of the array 
 * @param m int integer   Shift right distance 
 * @param a int Integer one-dimensional array   Given array 
 * @param aLen int a The length of the array 
 * @return int Integer one-dimensional array 
 * @return int* returnSize  Returns the number of rows in the array 
 */
int* solve(int n, int m, int* a, int aLen, int* returnSize ) {

}

discuss ：

This question is Cattle from Interview High frequency list questions NC110 Rotated array , Medium , Related enterprises and related positions all need this question , You can take this question and brush it well .

The probability of occurrence of this problem is very large The number of investigations is as high as 87 Time , What a huge number this is , The difficulty is also medium ,（ Look at the picture below ） The passing rate is also low ; We know why I explain this problem ！ So it is necessary to have a look

Title main information :

A length of nnn Array of , Rotate the whole array to the right mmm A place （mmm May be greater than nnn）
Cycle to the right, that is, the last mmm Elements are placed at the top of the array , front n−mn-mn−m The elements are moved back in turn
You cannot use additional array space

Algorithm idea 1 ： Use extra arrays

Their thinking ：

You can use extra arrays to put each element in the right place . Iterate over the original array , Subscript the original array to i Put the elements in the new array with the subscript (i+m) mod n （ To prevent the length of the right shift from being greater than the length of the array , That's why there is surplus ） The location of , Finally, return a new array

The illustration ：

Code display ：

JAVA edition

import java.util.*;

public class Solution {

/**

* Rotated array

* @param n int integer The length of the array

* @param m int integer Shift right distance

* @param a int Integer one-dimensional array Given array

* @return int Integer one-dimensional array

*/

public int[] solve (int n, int m, int[] a) {

// write code here

// Extra new array

int[] newArr = new int[n];

// Iterate over the original array

for (int i = 0; i < n; ++i) {

// Array element rotation

newArr[(i + m) % n] = a[i];

}

return newArr;

}

Complexity analysis

Time complexity O(n)： among n Is the length of the array , Traverse array time O(n)

Spatial complexity O(n)： Additional new arrays take up space

Algorithm idea 2 ： Array flip

Their thinking ：

The method is based on the following facts ： Put the elements of the array To the right k Next time , The tail m mod n The first element will be moved to the head of the array , The rest of the elements Move backward m mod n A place .
This method is the flip of the array ： Flipping algorithm reference Reverse the double pointer method in the linked list Answer key | # Reverse a linked list #_ Niuke blog

1、 You can flip all the elements first , This tail m mod n The first element is moved to the head of the array ,

2、 Then flip [0,m mod n−1] The elements of the interval

3、 Last flip [m mod n,n−1] The elements of the interval can get the final answer .

example ：
With n=7,m=3 As an example, it is shown as follows ：

operation	result
Raw data	【1,2,3,4,5,6,7】
Flip all elements	【7,6,5,4,3,2,1】
Flip [0,m mod n −1] The elements of the interval	【5,6,7,4,3,2,1】
Flip [m mod n, n −1] The elements of the interval	【5,6,7,1,2,3,4】

Finally back to ：【5,6,7,1,2,3,4】

Code display ：

Python edition

class Solution:

def solve(self , n , m , a ):

# write code here

m = m % n

# An array of reverse

# Flip all

self.reverse(a, 0, n - 1);

# Flip again 【0,m-1】

self.reverse(a, 0, m - 1);

# Flip again 【m,n-1】

self.reverse(a, m, n - 1);

return a

def reverse(self, nums, start, end):

# Array flip

while start < end :

# Double pointer traversal flip

temp = nums[start];

nums[start] = nums[end];

nums[end] = temp;

start += 1;

end -= 1;

Complexity analysis

Time complexity ：O(N), among N Is the length of the array . Each element is flipped twice , altogether N Elements , So the total time complexity is O(2N)=O(N).
Spatial complexity ：O(1). Use constant level space variables

Algorithm idea 3 ： Array transformation

Their thinking ：

Simple and convenient method ： Array direct transformation

1、tmp = m mod n, Find the right shift distance

2、 use a[:tmp], a[tmp:] = a[-tmp:],a[:n-tmp] Direct transformation

Code display ：

Python edition

class Solution:

def solve(self , n , m , a ):

# write code here

# Get the moving distance

tmp = m % n

# Swap moving arrays

a[:tmp], a[tmp:] = a[-tmp:],a[:n-tmp]

return a

Complexity analysis

Time complexity ：O(n), among n Is the length of the array . Move in all n Elements
Spatial complexity ：O(1). Use constant level space variables

The lines ：

After learning the idea of this problem, you can solve the following problems ：

BM99. Rotate the matrix clockwise

Method ： Triple flip （ Recommended ）

Ideas ：

Moving right in a cycle is equivalent to moving from mmm A place to start , The left and right parts are regarded as a whole . namely abcdefg Move right 3 position efgabcd Can be seen as AB Flip into BA（ Here, lowercase letters are regarded as array elements , Capital letters as a whole ）. Since it's a flip, we can use reverse function .

specific working means :

step 1： because mmm May be greater than nnn, So you need to nnn Remainder , Because the length of each time is nnn The rotation array of is equivalent to no change .
step 2： Flip the entire array for the first time , Get the reverse order of the array , It has satisfied the right shift, and the whole appears on the left .
step 3： The second time will be on the left mmm Elements are flipped separately , Because although it moved to the left , But in reverse order .
step 4： The third time will be on the right n−mn-mn−m Elements are flipped separately , So this part is also in reverse order .

Icon ：

Java Code implementation :

publicclassSolution {

publicint[] solve (intn, intm, int[] a) {

// Remainder , Because the length of each time is n The rotation array of is equivalent to no change

m = m % n;

// Reverse all array elements for the first time

reverse(a, 0, n - 1);

// The second time only reverses the beginning m individual

reverse(a, 0, m - 1);

// The third time only reverses the end m individual

reverse(a, m, n - 1);

returna;

}

// Inversion function

publicvoidreverse(int[] nums, intstart, intend){

while(start < end){

swap(nums, start++, end--);

}

// Exchange function

publicvoidswap(int[] nums, inta, intb){

inttemp = nums[a];

nums[a] = nums[b];

nums[b] = temp;

}

C++ Code implementation :

classSolution {

public:

vector<int> solve(intn, intm, vector<int>& a) {

// Remainder , Because the length of each time is n The rotation array of is equivalent to no change

m = m % n;

// Reverse all array elements for the first time

reverse(a.begin(), a.end());

// The second time only reverses the beginning m individual

reverse(a.begin(), a.begin() + m);

// The third time only reverses the end m individual

reverse(a.begin() + m, a.end());

returna;

}

};

Python Implementation code ：

classSolution:

def solve(self , n: int, m: int, a: List[int]) -> List[int]:

# Remainder , Because the length of each time is n The rotation array of is equivalent to no change

m = m % n

# Reverse all array elements for the first time

a.reverse()

b = a[:m]

# The second time only reverses the beginning m individual

b.reverse()

c = a[m:]

# The third time only reverses the end m individual

c.reverse()

a[:m] = b

a[m:] = c

returna

Complexity analysis ：

Time complexity ：O(n)O(n)O(n), Three times reverse The worst complexity of functions is O(n)O(n)O(n)
Spatial complexity ：O(1)O(1)O(1), No additional auxiliary space is used

Next, let's do it again

2.NC78 Reverse a linked list

describe ：

Given the head node of a single linked list pHead( The header node has a value , For example, in the figure below , its val yes 1), The length is n, After reversing the linked list , Return the header of the new linked list .

Data range ： 0\leq n\leq10000≤n≤1000

requirement ： Spatial complexity O(1)O(1) , Time complexity O(n)O(n) .

For example, when entering a linked list {1,2,3} when ,

After reversal , The original linked list becomes {3,2,1}, So the corresponding output is {3,2,1}.

The above conversion process is shown in the figure below ：

Let's look at the output style

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C Language declaration defines global variables. Please add static, Prevent duplicate definitions 
 *
 * C Language declaration defines global variables. Please add static, Prevent duplicate definitions 
 */

/**
 * 
 * @param pHead ListNode class  
 * @return ListNode class 
 */
struct ListNode* ReverseList(struct ListNode* pHead ) {
    // write code here
}

Relevant enterprise positions include Baidu Kwai , Large enterprises ...

Solution 1 ： iteration

When traversing a linked list , Set the... Of the current node next The pointer changes to point to the previous node . Because the node does not refer to its previous node , So you have to store its previous node in advance . Before changing the reference , You also need to store the latter node . Finally, the new header reference is returned .

The illustration ：

Java Reference code ：

/*

public class ListNode {

int val;

ListNode next = null;

ListNode(int val) {

this.val = val;

}

}*/

publicclassSolution {

publicListNode ReverseList(ListNode head) {

//pre The pointer ： Used to point to the inverted node , Initialize to null

ListNode pre = null;

// Current node pointer

ListNode cur = head;

// Loop iteration

while(cur!=null){

//Cur_next node , Always point to the current node cur The next node of

ListNode Cur_next = cur.next;

// The key to reversal ： The current node points to its previous node ( Note that this is not a two-way linked list , No precursor pointer )

cur.next = pre;

// to update pre

pre = cur;

// Update the current node pointer

cur = Cur_next ;

}

// Why return to pre？ because pre Is the head node after inversion

returnpre;

}

Complexity analysis ：

Time complexity ：O(N), among N It's the length of the list . You need to traverse the linked list once .

Spatial complexity ：O(1), Constant space complexity

Solution 2 ： recursive

Using recursive functions , Recursion to the last node of the list , This node is the head node after inversion , Write it down as ans
thereafter , Every time a function returns , Let the current node of the next node of next Pointer to current node .
At the same time, let the current node of next Pointer to NULL , So as to realize the local inversion from the end of the list
When all recursive functions are out of the stack , List reversal complete .

C++ Reference code ：

/*

struct ListNode {

intval;

struct ListNode *next;

ListNode(intx) :

val(x), next(NULL) {

}

};*/

classSolution {

public:

ListNode* ReverseList(ListNode* pHead) {

// Special judgement ： Be careful not to miss pHead->next==NULL The situation of

if(pHead==NULL || pHead->next==NULL){

returnpHead;

}

// Recursively call

ListNode* ans = ReverseList(pHead->next);

// Let the current node of the next node of next Pointer to current node

pHead->next->next=pHead;

// At the same time, let the current node of next Pointer to NULL , So as to realize the local inversion from the end of the list

pHead->next=NULL;

returnans;

}

};

Complexity analysis ：

Time complexity ：O(N), among N It's the length of the list . You need to reverse each node of the linked list .

Spatial complexity ：O(N), among N It's the length of the list . The space complexity mainly depends on the stack space of recursive calls , At most N layer

Algorithm idea 3 ： Use extra stacks

Their thinking ：

Create additional new stacks stack

Loop through the original linked list , And put the linked list elements on the stack , After the traversal is over , Put the elements in the stack out of the stack in turn and create a linked list

The illustration ：