preface
This article was published on the public account “Bigsai”. Please attach the author and the link to this article
Hello everyone, I’m Bigsai.
Recently, a lot of friends talked to me about how to brush questions. My advice is to first point at offer and hot100. There are some questions with very high importance and frequency.
0X01 Reverse the linked list
Li Kou 206 and jian offer24
Given the head node of a single linked list, reverse the list and return the reversed list.
Analysis:
The idea of flipping a linked list is not to create a new list node and then flip it on the original list. However, this diagram is a bit misleading. In fact, you can see the following diagram for a better understanding:
Specific implementation of the above two ideas, non-recursive and recursive implementation, non-recursive implementation is relatively simple, use a pre node to record the precursor node, when the downward enumeration can change the pointer to point to, the implementation code is:
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null||head.next==null)// If the node is NULL or a single node is returned
return head;
ListNode pre=head;// The precursor node
ListNode cur=head.next;// The current node is used for enumeration
while(cur! =null)
{
ListNode next=cur.next;
// Change the direction
cur.next=pre;
pre=cur;
cur=next;
}
head.next=null;// Set the head next node to null to prevent eventual loop formation
returnpre; }}Copy the codeThe recursion method is more clever, with the help of the recursive return process subtly change the pointer pointing and return value transfer, although the code is concise, but it is difficult to understand, here is a picture to help you understand:
The specific code is:
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null||head.next==null)// If the last node does not operate
return head;
ListNode node =reverseList(head.next);// Recurse to the bottom level and return
head.next.next=head;// The last node points to itself
head.next=null;//自己本来指向的next置为null
return node;// Return the last node (passed recursively)}}Copy the code0 x02 design LRU
For the stress link 146LRU caching mechanism, the title requirements are as follows:
Using your knowledge of data structures, design and implement an LRU caching mechanism. Implement the LRUCache class:
Capacity Initializes the LRU cache int GET (int key) Returns the value of the key if the key exists in the cache; otherwise -1 is returned. Void put(int key, int value) If the keyword already exists, change its data value. If the keyword does not exist, the set of keyword – values is inserted. When the cache reaches its maximum capacity, it should delete the oldest unused data values before writing new data to make room for new data values.
Advanced: Complete both operations in O(1) time complexity
Detailed analysis: an experience of falling on an LRU
The core of LRU is to use hash + double linked list. Hash is used for query. Double linked list realizes deletion only knowing that the current node can also be deleted with the complexity of O(1), but double linked list needs to consider the special case of head and tail Pointers.
The specific implementation code is:
class LRUCache {
class Node {
int key;
int value;
Node pre;
Node next;
public Node(a) {}public Node( int key,int value) {
this.key = key;
this.value=value; }}class DoubleList{
private Node head;/ / head node
private Node tail;/ / end nodes
private int length;
public DoubleList(a) {
head = new Node(-1, -1);
tail = head;
length = 0;
}
void add(Node teamNode)// The tail node is inserted by default
{
tail.next = teamNode;
teamNode.pre=tail;
tail = teamNode;
length++;
}
void deleteFirst(a){
if(head.next==null)
return;
if(head.next==tail)// If the object to be deleted happens to be tail, notice that the tail pointer is moved before it
tail=head;
head.next=head.next.next;
if(head.next! =null)
head.next.pre=head;
length--;
}
void deleteNode(Node team){
team.pre.next=team.next;
if(team.next! =null)
team.next.pre=team.pre;
if(team==tail)
tail=tail.pre;
team.pre=null;
team.next=null;
length--;
}
}
Map<Integer,Node> map=new HashMap<>();
DoubleList doubleList;// Store the sequence
int maxSize;
LinkedList<Integer>list2=new LinkedList<>();
public LRUCache(int capacity) {
doubleList=new DoubleList();
maxSize=capacity;
}
public int get(int key) {
int val;
if(! map.containsKey(key))return -1;
val=map.get(key).value;
Node team=map.get(key);
doubleList.deleteNode(team);
doubleList.add(team);
return val;
}
public void put(int key, int value) {
if(map.containsKey(key)){// You already have this key. Delete it and update it regardless of its length
Node deleteNode=map.get(key);
doubleList.deleteNode(deleteNode);
}
else if(doubleList.length==maxSize){// Does not contain and the length is less than
Node first=doubleList.head.next;
map.remove(first.key);
doubleList.deleteFirst();
}
Node node=newNode(key,value); doubleList.add(node); map.put(key,node); }}Copy the code0X03 Circular linked list
For stress link 141 and force link 142, force link 141 ring list requirements are:
Given a linked list, determine whether there is a ring in the list, O(1) memory solution.
Detailed analysis: circular list to find entry, really wonderful
The fast pointer fast takes 2 steps each time, and slow takes 1 step each time. The slow pointer takes N steps to the end, and the fast pointer takes 2N steps. The size of the ring must be less than or equal to N, so it must meet.
The specific code is:
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode fast=head;
ListNode slow=fast;
while(fast! =null&&fast.next! =null) {
slow=slow.next;
fast=fast.next.next;
if(fast==slow)
return true;
}
return false; }}Copy the codeForce link 142 is expanded in force link 141. If there is a ring, return to the node in the ring, just like the ring list below to return to node 2.
This problem is the need for mathematical transformation, the specific analysis can see the above detailed analysis, which mentions the steps of the big problem.
If you find the first intersection, one of them stops, the other one continues, and the next intersection happens to be a full circle, you can figure out that the length of the circle is y.
So what we know is that when we meet, fast takes 2x steps, slow takes x steps, and the ring length is Y. In addition, when the fast pointer and the slow pointer meet, the number of extra steps is just an integer multiple of the length y(the two are in the same position at the moment, so the fast pointer just makes an integer multiple of the number of turns to get together at the same position), and we can get 2x=x+ny(x=ny). Where, the x of the slow pointer and the x of the fast pointer are integer multiples of the circle length y.
In other words, we’re going to take x steps from the beginning to this point, and we’re going to take x steps from this point, so we’re going to go around and get back to this point. If slow starts at this point and fast starts at this point (taking one step at a time, which cancels out the distance slow took in the previous two steps), then taking x steps will still reach this point, but both Pointers are taking one step at a time this time, so once slow reaches the circle, the two Pointers start to converge.
The implementation code is:
public class Solution {
public ListNode detectCycle(ListNode head) {
boolean isloop=false;
ListNode fast=new ListNode(0);/ / the head pointer
ListNode slow=fast;
fast.next=head;
if(fast.next==null||fast.next.next==null)
return null;
while(fast! =null&&fast.next! =null) {
fast=fast.next.next;
slow=slow.next;
if(fast==slow)
{
isloop=true;
break; }}if(! isloop)// Return if there is no loop
return null;
ListNode team=new ListNode(-1);// Head is next to head
team.next=head;
while(team! =fast) {// Slow and fast start from the starting point and the current point respectively
team=team.next;
fast=fast.next;
}
returnteam; }}Copy the code0X04 Two stacks implement queues
Offer09 = offer09 = offer09
Implement a queue with two stacks. Implement appendTail and deleteHead to insert an integer at the end of the queue and delete an integer at the head of the queue. (If there are no elements in the queue, the deleteHead operation returns -1)
Analysis:
To solve this problem, we need to know what a stack is and what a queue is. The two common data structure formats are very simple. The characteristics of a stack are: last in, first out, and the characteristics of a queue are: first in, first out. A queue is just like queuing to buy something, which can only be entered at the back and left at the front. Therefore, the data structure of the two is different. Although they are entered and left at a single entrance, the import and export of stacks are the same, while the queues are different.
Stack1 is used as the data store, stack1 is used as the data store, and stack2 is used as the data store when the header is removed. Return and delete the top elements of the stack, and add stack2 sequentially to Stack1 to achieve a restore, but the insert time complexity of this operation is O(1), and the delete time complexity of O(n) is relatively high.
The implementation method is also shown to you:
class CQueue {
Stack<Integer>stack1=new Stack<>();
Stack<Integer>stack2=new Stack<>();
public CQueue(a) {}public void appendTail(int value) {
stack1.push(value);
}
public int deleteHead(a) {
if(stack1.isEmpty())
return -1;
while(! stack1.isEmpty()) { stack2.push(stack1.pop()); }int value= stack2.pop();
while(! stack2.isEmpty()) { stack1.push(stack2.pop()); }returnvalue; }}Copy the codeThis time complexity is not desirable because deleting is time-consuming and requires a lot of work each time. Is there a good way to make deleting easier?
Stack1 can be inserted sequentially, stack1 can be inserted sequentially, stack2 can be deleted sequentially, stack1 can be inserted sequentially, stack2 can be deleted sequentially.
When implemented, inserts are inserted directly into stack1, or removed from the top of stack2 if necessary, or added to stack2 if stack2 is empty. Here are some examples of deletions
The data is split into two parts, one for insertion and one for deletion, and stack2 is empty, adding all the data in Stack1. The time complexity of this operation is O(1), and the code is as follows:
class CQueue {
Deque<Integer> stack1;
Deque<Integer> stack2;
public CQueue(a) {
stack1 = new LinkedList<Integer>();
stack2 = new LinkedList<Integer>();
}
public void appendTail(int value) {
stack1.push(value);
}
public int deleteHead(a) {
// Add stack1 data to stack2 if the second stack is empty
if (stack2.isEmpty()) {
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
} // If stack2 is still empty, there is no data
if (stack2.isEmpty()) {
return -1;
} else {// Otherwise delete
int deleteItem = stack2.pop();
returndeleteItem; }}}Copy the code0X05 Binary tree sequence (sawtooth) traversal
Binary tree traversal, on the stress buckle 102,107,103.
Detailed analysis: an interview, by binary tree traversal hit
If ordinary binary tree traversal, it is not a difficult problem, but it will have a hierarchical return operation, you need to consider carefully.
Many people use two containers (queues) for hierarchical operations. In this case, we can use one queue directly. We first record the size of the queue before enumeration, len, and then iterate through the enumeration based on this size to get the complete layer data.
Another difficulty is the zigzag sequence (also known as zigzag printing) of binary trees. The first step is left to right and the second step is right to left. It is only necessary to record an odd and even number of layers for corresponding operations.
Here take the zigzag sequence traversal of likou 103 binary tree as a board to share the code:
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> value=new ArrayList<>();// The final result to be stored
if(root==null)
return value;
int index=0;/ / determine
Queue<TreeNode>queue=new ArrayDeque<>();
queue.add(root);
while(! queue.isEmpty()){ List<Integer>va=new ArrayList<>();// Temporarily used to store in value
int len=queue.size();// The number of nodes in the current layer
for(int i=0; i<len; i++){ TreeNode node=queue.poll();if(index%2= =0)// Add policies based on parity selection
va.add(node.val);
else
va.add(0,node.val);
if(node.left! =null)
queue.add(node.left);
if(node.right! =null)
queue.add(node.right);
}
value.add(va);
index++;
}
return value;
}
Copy the code0X06 Post-ordered traversal in binary tree (non-recursive)
Binary tree non-recursive traversal is also the focus of the inspection, for the order after the order traversal recursive implementation is very simple, non-recursive implementation or key skills oh.
Detailed analysis: Various traversals of binary trees (recursive, non-recursive)
For middle order traversal of binary tree, in fact, it is normal to throw the output when the node is accessed for the second time (the order before the first number), so we enumerate each node can not be deleted for the first time, we need to put it on the stack first, when the left child node processing is completed, then throw to access the node.
The core is only two steps, and the left and right sides of the leaf nodes are null, which can also satisfy the following conditions:
- Enumerates the current node (does not store output) and stores it in a stack, with the node referring to the left node until the left child is null.
- Throws top of stack access. If there is a right node, access the right node and repeat Step 1. If there is no right node, repeat Step 2.
The implementation code is:
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer>value=new ArrayList<Integer>();
Stack<TreeNode> q1 = new Stack();
while(! q1.isEmpty()||root! =null)
{
while(root! =null) {
q1.push(root);
root=root.left;
}
root=q1.pop();/ / throw
value.add(root.val);
root=root.right;// Prepare to access its right node
}
returnvalue; }}Copy the codeIt’s a bit of a challenge to do a recursive traversal where the third visit to the node comes back from the right child. If the current right child is pre or the current right node is null, then this point will be thrown. Otherwise, the right side of the node has not been accessed. We need to “recycle” it and use it later. If you don’t understand, you can see the details above.
The specific implementation code is:
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
TreeNode temp=root;// Enumeration of temporary nodes
List<Integer>value=new ArrayList<>();
TreeNode pre=null;// The front node
Stack<TreeNode>stack=new Stack<>();
while(! stack.isEmpty()||temp! =null) {while(temp! =null){
stack.push(temp);
temp=temp.left;
}
temp=stack.pop();
if(temp.right==pre||temp.right==null)// Need to pop up
{
value.add(temp.val);
pre=temp;
temp=null;// Needs to be rethrown from the stack
}else{ stack.push(temp); temp=temp.right; }}returnvalue; }}Copy the codeOf course, post-order traversal can also be used to reverse the results of the previous order (root right and left), but the interviewer is more interested in the method mentioned above.
0X07 Jumping steps (Fibonacci, Climbing stairs)
Climbing stairs and jumping steps is a classic problem, corresponding to offer10 and force buckle 70 questions, the requirements of the topic are:
Suppose you’re climbing stairs. It takes n steps to get to the top. You can climb one or two steps at a time. How many different ways can you climb to the top? ** Note: ** given n is a positive integer.
Analysis:
This problem is at the entry level DP, analyzing the results of the current KTH order, each person can climb one or two steps, so it could be from K-1 or K-2, so it’s a superposition of two subcases (you need to think about the initial case in particular), this idea that some people think of recursively, Yes, it’s possible to do it recursively but it’s less efficient to do it recursively (because this is a divergent recursion one breaks into two), and it’s a little bit better to do it with mnemonic search.
However, DP is a better method, and the core state transition equation is: DP [I]= DP [i-1]+ DP [i-2]. Some spatial optimization is even better, because only the first two values are used, so three values can be reused to save space.
class Solution {
public int climbStairs(int n) {
if(n<3)return n;
int dp[]=new int[n+1];
dp[1] =1;
dp[2] =2;
for(int i=3; i<n+1; i++) { dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
public int climbStairs(int n) {
int a = 0, b = 0, c = 1;
for (int i = 1; i <= n; i++) {
a = b;
b = c;
c = a + b;
}
returnc; }}Copy the codeOf course, some data very large redundant jump steps, you can use the matrix fast power to solve, but here is not introduced, interested can look in detail.
0 x08 TOPK problem
TOPK problem is really very classic, usually asked to have the smallest number of K, looking for the K is mostly TOPK this kind of problem, here is to buckle 215 to find the array of the KTH element as a board.
Detailed analysis: a take TOPK
There are many ways to solve the TOPK problem, if the optimized bubble or simple selection sort, the time complexity is O(NK), using the optimized heap sort O(n+klogn), but master the deformation of fast sorting can deal with almost all the problems (if the interview asks you to handwritten heap sort that is really a little difficult for you).
Each time the quicksort determines the pivot position of a number, divide the number into two parts: the number on the left is smaller than the number pivot, and the number on the right is larger than the number pivot. Thus, the k determines whether the number is in the pivot position, left or right. You can compress spatial iteration to call recursion and get the result.
Many people choose this pivot not to select the first one randomly in order to get past the test sample faster (in order to fight the tricky test sample), but I will choose the first pivot as my pivot.
class Solution {
public int findKthLargest(int[] nums, int k) {
quickSort(nums,0,nums.length-1,k);
return nums[nums.length-k];
}
private void quickSort(int[] nums,int start,int end,int k) {
if(start>end)
return;
int left=start;
int right=end;
int number=nums[start];
while (left<right){
while (number<=nums[right]&&left<right){
right--;
}
nums[left]=nums[right];
while (number>=nums[left]&&left<right){
left++;
}
nums[right]=nums[left];
}
nums[left]=number;
int num=end-left+1;
if(num==k)// stop when k is found
return;
if(num>k){
quickSort(nums,left+1,end,k);
}else {
quickSort(nums,start,left-1,k-num); }}}Copy the code0X09 Maximum string without repetition (array)
The problem could be a string or an array, but the logic is the same. The longest string without repeating characters is essentially the same as the longest subarray without repeating characters.
Given a string, find the length of the smallest string that does not contain repeated characters.
Analysis:
This problem gives you a string and asks you to find the longest substring that is not repeated. To learn the difference between a substring and a subsequence:
Substring: is continuous and can be regarded as part of the original string. Subsequence: not necessarily continuous, but the relative position of each element remains the same.
So how do we deal with that?
Brute force lookup, brute force lookup is certainly possible, but it’s too complicated to go into here. The idea chosen here is sliding window. Sliding window is to use an interval from left to right, and test the right first to find the maximum value of the interval without repetition. When there is repetition, the left side will move to the right until there is no repetition, and then repeat until the end. Find the largest substring in the entire process.
It is much faster to use arrays instead of hash tables:
class Solution {
public int lengthOfLongestSubstring(String s) {
int a[]=new int[128];
int max=0;// Record the maximum value
int l=0;//left uses I as right, when there is repetition left goes right
for(int i=0; i<s.length(); i++) { a[s.charAt(i)]++;while (a[s.charAt(i)]>1) {
a[s.charAt(l++)]--;
}
if(i-l+1>max)
max=i-l+1;
}
returnmax; }}Copy the code0 x10 sorting
Not really someone thought with a Arrays. Sort () just a matter of right, handwritten sorting or very high frequency, like a bubble, insert compared these simple everyone can, heap sort, hill, and radix sort examining, relatively high frequency is quick line, this bonus a merge sort is also very high frequency, two are typical partition algorithm, You can also compare quicksort to the TOPK problem above.
Sort the details of the ten sort have been detailed, we can refer to: programmers will know will be ten sort
Fast row:
Concrete implementation:
public void quicksort(int [] a,int left,int right)
{
int low=left;
int high=right;
// The sequence of the following two sentences must not be mixed, otherwise the array will be generated out of bounds!! Very important!!
if(low>high)// as a cut-off condition
return;
int k=a[low];// The extra space, k, is measured by the leftmost space, and the left side is smaller than it and the right side is larger than it.
while(low<high)// Make the left side less than a[low] and the right side greater than a[low].
{
while(low<high&&a[high]>=k)// Find the first stop less than k on the right
{
high--;
}
// Find the first one smaller than it
a[low]=a[high];// Put it in low position
while(low<high&&a[low]<=k)// Find the first one greater than k to the right of low and place it in position A [high] to the right
{
low++;
}
a[high]=a[low];
}
a[low]=k;// Assign and divide and conquer recursively
quicksort(a, left, low-1);
quicksort(a, low+1, right);
}
Copy the codeMerge sort:
The implementation code is:
private static void mergesort(int[] array, int left, int right) {
int mid=(left+right)/2;
if(left<right)
{
mergesort(array, left, mid);
mergesort(array, mid+1, right); merge(array, left,mid, right); }}private static void merge(int[] array, int l, int mid, int r) {
int lindex=l;int rindex=mid+1;
int team[]=new int[r-l+1];
int teamindex=0;
while (lindex<=mid&&rindex<=r) {// compare and merge
if(array[lindex]<=array[rindex])
{
team[teamindex++]=array[lindex++];
}
else{ team[teamindex++]=array[rindex++]; }}while(lindex<=mid)// When one is out of bounds, the rest can be added in sequence
{
team[teamindex++]=array[lindex++];
}
while(rindex<=r)
{
team[teamindex++]=array[rindex++];
}
for(int i=0; i<teamindex; i++) { array[l+i]=team[i]; }}Copy the codeconclusion
Well, today’s top 10 questions are really, really common in job interviews. I’d say on average you’ll encounter one of these questions every two job interviews (literally)!
Although the question is deep to learn, but learned to cache all know to slow down the hot data storage, tested all know to master the test point…… These ten questions are on the tip of my tongue.
Of course, this is only a very, very frequently asked question. If you want to hold the written test, you must continue to accumulate and brush the questions. Welcome to join my force button card group to brush the questions!
Original is not easy, ask praise attention support. Welcome to pay attention to personal public account: Bigsai.