Some coding tips

recursion control

How to prove the correct execution of recursive functions ？

• Mathematics in mathematical induction / Natural language <--> Programming language

Recursive writing method

• Strictly define the function of recursive function , Including the parameters , Return value ,Side-effct
• First commonly , after special
• Each call must narrow The scale of the problem
• The scale of each problem must be reduced to 1

Linked list creation

Head -->1-->2-->3-->4-->5-->null

Why do you like to ask a linked list in an interview （ A one-way ）

• Easy to understand
• The code is hard to write
• Examine the code's ability through the linked list itself

List reversal

List all combinations （side effect）

• combinations([1, 2, 3, 4], 2):
• [1, 2]、[1、3]、[1、4]、[2、3]、[2、4]、[3、4]

Recursive disadvantage ：

• Function call overhead
• stack overflow
• The scale of the problem ：n million Stack size

Cycle control

recursive --> Non recursive

• The generalized approach still requires the use of stacks
• Complex code , Don't solve the problem fundamentally

Log in and copy

      
      

       
       Node 
       
       CreateLinkedList(
       
       List
       
       <
       
       Integer
       
       > 
       
       values)
      
      
      
      

       
       
1.
      
      

Loop invariants （loop invariant）

• Is an assertion that defines the conditions that each variable satisfies
• ​​Var a, b;​​
• ​​While(){​​

​​}​​

Circular writing method

• Define loop invariants , And keep the loop invariant after each end of the loop body
• First general , Post special
• Each time you must advance the value of the variable involved in the loop invariant
• The scale of each push must be 1

List reversal

In the list delete_if

1. duplicate removal
2. The header node has no previous What do I do ？

1. Special treatment
2. Add virtual head node

Boundary control

for example ： Two points search Find elements in a binary array k, return k The subscript ​​binarySearch([1, 2, 10, 15, 100], 15) == 3​​

Binary search ideas ：

• Specify the value to find k Possible array in arr Inner subscript interval a, b
• Calculation interval a,b In the middle m
• if k<arr[m], Reduce the interval to a, m. Go ahead with the binary search
• if k>arr[m], Reduce the interval to m, b. Go ahead with the binary search

data structure

Trees -- Key points and difficulties

Write a program on the whiteboard ： Whiteboard 、 paper and pen 、Word file 、 Notepad Inconvenient to modify ; Indenting is inconvenient ; Alignment difficulties

There is no conflict in my heart ;

Think before you write ;

Don't be afraid to revise / rewrite

review

list ：

• Array -- Random access
• Linked list
• queue 、 Stack -- Pay attention to the interview

Trees ：

• Binary tree
• Search tree
• Pile up / Priority queue

Stack / queue / Priority queue

Map<K, V> / Set<K>

• HashMap / HashSet --> K.hashCode()
• TreeMap / TreeSet -- > K implements Comparable

chart ：

• Undirected graph
• Directed graph
• Directed acyclic graph
• Graph algorithm -- complex , Generally, no algorithm questions are given in the interview
• Depth-first traversal
• Breadth first traversal
• A topological sort
• Shortest path / Minimum spanning tree

Mathematical induction -- Used in coding

Used to prove that assertions hold true for all natural numbers

1. To prove to N=1 establish

1. prove N>1 when ： If for N-1 establish , So for N establish

The law of mathematical induction ： verification ：1+2+3+4+...+n=n(n+1)/2

• 1 = 1*2/2
• If 1+2+3+...+(n-1) = (n-1)n/2
• that 1+2+3+...+n = 1+2+3+...+(n-1)+n=(n-1)n/2+n = (n(n-1)+2n)/2=n(n+1)/2

Log in and copy

      
      

       
       int 
       
       sum(
       
       int 
       
       n){
       
       
  
       
       if (
       
       n 
       
       == 
       
       1)
       
       
    
       
       return 
       
       1;
       
       
  
       
       return 
       
       sum(
       
       n
       
       -
       
       1)
       
       +
       
       n;
       
       
}
      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.