Sword finger offer high quality code

Hello everyone , I am a Nefelibat.

Take algorithm notes on your blog , Because I want to push I insist on brushing several algorithm problems every day , At the same time, I hope to share my experience with you , I hope you have a good time reading

Catalog

Interviewers often consider

The normalization of code

Be careful ： When the candidate is writing code , It is best to name variables and functions with complete English word combinations .

Code integrity

subject ： Integer power of value

Ideas

Code

Comprehensive and efficient code

  subject ： Print from 1 To the biggest n digit

Ideas

Code

Ideas

Code

  Turn the problem into a problem of numerical arrangement , Recursion makes code simpler

  The test case

Expand

subject ： Delete the node of the linked list

Ideas

Existing problems ：

If the node to be deleted is at the end of the linked list , Traverse the linked list to get the pre order node of this node , Then there is no next node ,  If there is only A node , Then set the head node of the linked list to nullptr.

Code

Use cases

subject ： Delete duplicate nodes in the list

Ideas

Code （ Follow up needs to see ）

Use cases

subject ： Regular Expression Matching

Ideas

Code

  Use cases

subject ： String representing the value

Ideas

Code

  Use cases

subject ： Adjust the array order so that the odd Numbers precede the even Numbers

Ideas

Improve your thinking

  Code

  Extended topics ： Put negative numbers in an array in front of non negative numbers

  Extended topics ： An array can be 3 Divisible numbers are placed where they cannot be 3 Before the number of divisions

Code

  Use cases

subject ： The penultimate in a linked list K Nodes

Ideas

Code

The problem is

Improve the code

Use cases

subject ： The entry node of the ring in the linked list

Ideas

  Code

Use cases

subject ： Reverse a linked list

Ideas

Code

Use cases

subject ： Merge two ordered linked lists

Ideas

Code

Use cases

  subject ： The substructure of a tree （ Compared with the linked list , The pointer of the tree is more difficult ）

Ideas

Code

Use cases

  Be careful

---

Interviewers often consider

Check the quality of the code from the correctness and robustness of the program , For example, the detection of output parameters , How to handle errors and exceptions , Naming method .

The normalization of code

Be careful ： When the candidate is writing code , It is best to name variables and functions with complete English word combinations .

Code integrity

Check whether the code completes the basic functions , Whether the input boundary value can get the correct output 、 Various use cases are handled .

subject ： Integer power of value

With handwritten code C In language pow() function .

Ideas

It is necessary to consider that the index is less than 1 The situation of . When the exponent is negative , First take the absolute value of the index , Calculate the result and then take the reciprocal . But when the base number is 0 When you count down, you will report an error , Special treatment required , Again 0 Of 0 Power is mathematically meaningless , So take 0 And take 1 Are acceptable .

Code

Comprehensive and efficient code

If the index is larger , Need to do 31 Times multiplication , Find a number 32 Power , If you already know its 16 Power , So as long as it's in 16 Square it again on the basis of power , It's like this 32 To the power, we need to do 5 Times multiplication .

 

We use right shift instead of division 2, The efficiency of bit operation is relatively high

  subject ： Print from 1 To the biggest n digit

Input number n, From... In order 1 To the biggest n A decimal number , Such as input 3, Then print out 1,2,3,...999

Ideas

The easiest thing to think of is to find the largest n digit , Then cycle from 1 Start printing , The code is as follows ：

Code

  But when you type n Very big time , Will it overflow ？

Ideas

Solution of analog digital addition on string , Large numbers can be represented by strings . When a string represents a number , Every character in the string is 0-9 Between a certain character , Used to represent a digit in a number . Because the biggest number is n position , We need a length of n+1 String , The last bit in the string is the closing symbol \0, When the actual number is not enough n When a , Put... In the first half of the string 0. Increment A string representing a number number To add 1,PrintNumber Print out number,

When do we need to stop at number increase 1, After each increment , call strcmp() A string representing a number number And the biggest n digit “99...99”, Only in “99..99” Add 1 When , Will generate a carry based on the first character ,

Code

 

  Turn the problem into a problem of numerical arrangement , Recursion makes code simpler

  The test case

1、 A functional test , Input 1,2,3,..

2、 Special input test , Input -1,0

Expand

In the previous code . We use it char One character of represents one digit in decimal number ,8bit The characters of can be listed at most 256 Characters ,2 Of 8 Power , But decimal numbers 0-9 It can only mean 10 A digital , because char Characters can make full use of memory , So is there a more efficient way to represent large numbers ？

subject ： Delete the node of the linked list

stay o(1) Delete node in time , Follow the header pointer and node pointer of a single linked list .

Ideas

Traverse the linked list to find the node to be deleted , And delete nodes from the linked list .

Existing problems ：

If the node to be deleted is at the end of the linked list , Traverse the linked list to get the pre order node of this node , Then there is no next node ,  If there is only A node , Then set the head node of the linked list to nullptr.

Code

Use cases

Delete header node , Delete tail node , Delete the linked list with only one node

subject ： Delete duplicate nodes in the list

In a sorted list , How to delete duplicate nodes

Ideas

Traverse the linked list from scratch , If the current node has the same value as the next node , Just delete

Code （ Follow up needs to see ）

 

Use cases

Duplicate nodes are located at the head of the linked list 、 The tail , middle , There are no duplicate nodes in the linked list , Pointing to the chain header node is nullptr The pointer , All nodes in the linked list are duplicated .

subject ： Regular Expression Matching

Set a function to match the containing “.” and “*” Regular expression of , In the pattern “.” Can represent any character ,“*” Indicates that the character in front of it can appear any number of times , for example ,“aaa” And “a.a” and “ab*ac*a” matching .

Ideas

When the second character in the pattern is not “*” when , If the first character in the string matches the first character in the pattern , Then both the character and the pattern move backward by one character , Then match the remaining strings and patterns , If the first character in the string does not match the first character in the pattern , return false.

When the second character in the pattern is “*” when , Move two characters backward on the pattern , amount to “*” And the characters before it are ignored ,

Code

 

 

  Use cases

String and pattern string are nullptr Or an empty string , The schema string summary contains “.” and “*”, The pattern string matches or does not match the input string

subject ： String representing the value

The implementation uses a function to judge whether the string represents a value

for example “12e“,"1a3.14" Not numerical

Ideas

use A,B, C The three parts respectively code the integer of the value 、 Decimal and exponential parts , First, scan the integer part of the value , If you encounter “.”, Scan the decimal part of the value , If you encounter e perhaps E, Scan the exponential part of the value .

Code

 

  Use cases

Positive numbers 、 negative 、 Contains values that do not contain integer parts , Include values that do not contain decimal parts , Include values that do not include exponential parts ; The input string or mode string is nullptr, An empty string .

subject ： Adjust the array order so that the odd Numbers precede the even Numbers

Ideas

If you don't think about time , Scan this number from the beginning , Every time you encounter an even number , Take out this number , Move the number after this number forward by one digit , There is a space at the end of the number , Put the even number into this space , The time complexity of moving once is o(n), So the time complexity is o(n2)

Improve your thinking

When scanning the array, even numbers appear in front of odd numbers , Exchange two numbers , Point to the first number of the array with a pointer , move backward , A pointer points to the last number of the array , Move forward , If the previous pointer points to an even number , And the second pointer points to an odd number , Exchange two numbers .

  Code

  Extended topics ： Put negative numbers in an array in front of non negative numbers

  Extended topics ： An array can be 3 Divisible numbers are placed where they cannot be 3 Before the number of divisions

To solve this kind of problem , Just modify the judgment conditions , Therefore, this logical framework can be abstracted , Use a separate function to judge whether the number meets the standard .

Code

  Use cases

Even and odd numbers in the array alternate , All input arrays appear before odd numbers , All the odd numbers entered appear before the even numbers , Input nullptr The pointer , The array contains only one number

subject ： The penultimate in a linked list K Nodes

Ideas

1、 First traverse to the end of the linked list , Then go back k Step , But the one-way linked list has no forward pointer

2、 Traverse the linked list from scratch , The list has n Nodes , So the last one K Nodes, even from the beginning n-K+1 Nodes

3、 The second method needs to traverse the linked list 2 Time , If the interviewer asks to traverse the linked list 1 Time , Then the second method is not feasible , You need two pointers , The first pointer traverses from the beginning k-1 When a node , The second pointer starts from the head node of the linked list , So the distance between the two pointers is k-1, When the first pointer reaches the tail , The second pointer points to the... Of the linked list K Nodes .

Code

The problem is

If the input header node points to a null pointer , The number of nodes of the input linked list is less than k, Input k yes 0, Deal with these three problems separately .

Improve the code

Use cases

The first k The first node is the head node of the linked list , Tail node ; The head node of the linked list is nullptr, The total number of nodes in the linked list is less than k,k be equal to 0.

subject ： The entry node of the ring in the linked list

Ideas

The first step is to determine whether the linked list contains rings , Define two pointers , At the same time, start from the head node of the linked list , One step at a time , The other pointer takes two steps at a time , If two hands meet , Then the linked list has rings , If a pointer reaches the end of the linked list , Then there is no ring .

The second step is to find the entrance of the ring , Suppose a linked list contains n Nodes , A pointer goes first n Step , Then another pointer starts from the beginning , A pointer starts from the tail , The node where two pointers meet is the entry node . Then count from this node , Return to this node again, and the count ends .

  Code

Use cases

The linked list contains or does not contain rings , There are multiple or only one node in the linked list , The chain header node is nullptr The pointer

subject ： Reverse a linked list

Ideas

At our adjustment node i When , Need to know node i Previous node of h, We will i Of next Pointer to h

Code

Use cases

There are multiple nodes in the list , There is a node in the list , The chain header node is nullptr The pointer

subject ： Merge two ordered linked lists

Enter two ascending ordered linked lists , Merge these two linked lists and make the nodes in the new linked list still be sorted incrementally .

 

Ideas

1、 Linked list 1 The head node of is smaller than the linked list 2 The value of the head node of , So linked list 1 The head node of is the head node of the merged linked list .

2、 In the remaining nodes , Linked list 2 The head node of is smaller than the linked list 1 Head node of , So linked list 2 The head node of is the head node of the remaining nodes

Because the merging steps are the same , So this can be seen as a recursive process .

Code

 

Use cases

The two linked lists to be merged have multiple nodes ; The values of nodes are different from each other or there are multiple nodes with equal values ; Two linked list summaries have only one node ; The head pointers of the two linked lists are nullptr.

  subject ： The substructure of a tree （ Compared with the linked list , The pointer of the tree is more difficult ）

Input two binary trees A and B, Judge B Is it right? A Substructure of .

Ideas

First step , stay A Found in and B The same node as the root node of R, The second step , Judge A China and Israel R Whether the subtree of the root node contains and B Same structure .

Code

The first step is to traverse the tree , Tree traversal can be recursive , It can cycle , Recursive method is simpler .

 

Use cases

A and B It's an ordinary binary tree ,B No A Substructure of ,A and B One or two root nodes of are nullptr The pointer ,A or B There is no left index or right index .

  Be careful

1、 Every time you use a pointer , We all have to ask ourselves whether this pointer can be nullptr, If it is nullptr What to do with .

2、 Because the computer says there is error in decimal , We cannot use symbols directly == Judge whether two decimals are equal , If the absolute value of the difference between two decimals is very small , It can be considered equal .