当前位置:网站首页>Sword finger offer (2) -- for Huawei
Sword finger offer (2) -- for Huawei
2022-04-23 15:09:00 【White horse is not a horse·】
Catalog
- 11. Double pointer (√)
- 12. Double pointer ( Simple )(√)
- 13. Double pointer ( Simple )(√)
- 14. Search and backtracking algorithms ( secondary )
- 15. Search and backtracking algorithms ( secondary )
- 16. Sort ( Simple )(√)
- 17. Sort ( Simple )(√)
- 18. Search and backtracking algorithms ( secondary )
- 19. Search and backtracking algorithms ( secondary )
-
- 19.1 The finger of the sword Offer 64. seek 1+2+…+n
- 19.2 The finger of the sword Offer 68 - I. The nearest common ancestor of a binary search tree
- 19.2 The finger of the sword Offer 68 - I. The nearest common ancestor of a binary search tree
- 19.3 The finger of the sword Offer 68 - II. The nearest common ancestor of a binary tree
- 20. Divide and conquer algorithm ( secondary )
11. Double pointer (√)
10.1 The finger of the sword Offer 18. Delete the node of the linked list
- Title Description
- Code parsing
1) Method 1 : Traversal methods
class Solution {
public ListNode deleteNode(ListNode head, int val) {
ListNode result=head;
if(result.val==val) return result.next;
while(result!=null){
if(result.next.val==val){
result.next=result.next.next;
return head;
}
result=result.next;
}
return head;
}
}
2) Method 2 : Recursive method
class Solution {
public ListNode deleteNode(ListNode head, int val) {
// Recursive method
// A special case
if(head==null) return null;
// General situation
if(head.val==val) return head.next;
// recursive
head.next=deleteNode(head.next,val);
return head;
}
}
- matters needing attention
1) Ergodic method : Fine operation of linked list : You need to use an agent to operate , Then still point to the head linked list .
2) Recursive method : Special and general situations need to be handled well , Then there is the writing of recursive expressions ; And the return value .
10.2 The finger of the sword Offer 22. Last in the list k Nodes
- Title Description
- Code details
1) Method 1 : Two iterations , The first to find the length of the linked list , Find the specified location for the second time
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
// The core idea : Count the first traversal
// The second traversal to output
int num=0;
ListNode node=head;
while(node!=null){
num++;
node=node.next;
}
System.out.println("num="+num);
int size=num-k+1; // The difference is one 1
int num1=0;
while(head!=null){
num1++;
if(size==num1) return head;
head=head.next;
}
return head;
}
}
2) Method 2 : Traverse once , Use the speed pointer to get to the right place in one step
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
// Use the speed pointer , You can do it in one step
ListNode slow=head;
ListNode fast=head;
while(k-->0) fast=fast.next;
while(fast!=null){
fast=fast.next;
slow=slow.next;
}
return slow;
}
}
- matters needing attention
1) Selection of linked list : Be sure to use an agent to operate the linked list , Or you won't get back to your head
2) Method 1 : Two iterations , The first count , Second choice .
- Method 2 : The speed pointer is in place in one step
12. Double pointer ( Simple )(√)
12.1 The finger of the sword Offer 25. Merge two ordered linked lists
- Title Description
- Code display
1) Iterative method
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode result=new ListNode();
ListNode node=result; // result result The agent of
while(l1!=null && l2!=null){
if(l1.val<=l2.val){
node.next=l1;
l1=l1.next;
node=node.next;
}else{
node.next=l2;
l2=l2.next;
node=node.next;
}
}
// Then the above cycle , One of them broke , Connect the follow-up of the other :
if(l1==null) node.next=l2;
if(l2==null) node.next=l1;
return result.next; // It doesn't start with the head
}
}
2) Method 2 : The recursive method ( Elegance never goes out of style )
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// Cut off conditions : A special case
if(l1==null) return l2;
if(l2==null) return l1;
// General recursive conditions : There is a return value , Then there is the assignment operation
if(l1.val<=l2.val){
l1.next=mergeTwoLists(l1.next,l2);
return l1;
}else{
l2.next=mergeTwoLists(l1,l2.next);
return l2;
}
}
}
- matters needing attention :
1) Splicing of chain list : Need an agent , The back also needs to point to the head .
2) Recursive method : Be sure to think clearly about recursive expressions . Cut off expression
12.2 The finger of the sword Offer 52. The first common node of two linked lists
- Title Description : The specified linked list is congruent , Instead of equal values at nodes
- Code details
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// The equality here is that the nodes are the same , Not all nodes have the same value
//1) A special case
if(headA==null || headB==null ) return null;
//2) Agent model
ListNode nodeA=headA;
ListNode nodeB=headB;
//3)
// Will be able to A and B Connect and compare :
while(nodeA!=nodeB){
nodeA=nodeA==null?headB:nodeA.next;
nodeB=nodeB==null?headA:nodeB.next;
}
return nodeA;
}
}
- Note that
1) Put the two linked lists together , Then loop through , Can offset the distance difference , One operation
2) Romantic code meaning .
13. Double pointer ( Simple )(√)
13.1 The finger of the sword Offer 21. Adjust the array order so that odd numbers are in even numbers
- Title Description
- Code display
1) Method 1 : Double pointer ( Based on the idea of fast scheduling )
class Solution {
public int[] exchange(int[] nums) {
// Double pointer method : Even in front and odd in back , Then exchange
// Fast thinking : Must be in while In circulation , Add... To each step left<right Judge the condition .
int left=0;
int right=nums.length-1;
while(left<right){
// Find an even number on the left , Look for odd numbers on the right
while(left<right && nums[left]%2!=0) left++;
while(left<right && nums[right]%2!=1) right--;
// Exchange when you find it
int temp=nums[left];
nums[left]=nums[right];
nums[right]=temp;
}
return nums;
}
}
13.2 The finger of the sword Offer 57. And for s Two numbers of
- Title Description
- Code display ( Double pointer )
class Solution {
public int[] twoSum(int[] nums, int target) {
// Double pointer : One end and one tail , big , Add one to the right ; The small , Add one to the left
int left=0;
int right=nums.length-1;
while(left<right){
if(nums[left]+nums[right]<target){
left++;
}else if(nums[left]+nums[right]>target){
right--;
}else{
return new int[]{
nums[left],nums[right]};
}
}
return new int[2];
}
}
13.3 The finger of the sword Offer 58 - I. Flip word order
- Title Description
2. Code details
1) Method 1 : Using stack operations ; There is also the method of use split, Splitting strings works wonders
class Solution {
public String reverseWords(String s) {
// First split into string arrays
String[] arr=s.split(" ");
ArrayDeque<String> deque=new ArrayDeque<>();
// Push
for(String i: arr){
if(i!="") deque.push(i);
}
// Out of the stack
StringBuilder result=new StringBuilder();
while(deque.size()>0){
result.append(deque.pop());
if(deque.size()!=0) result.append(" ");
}
return result.toString();
}
}
- Note that
1) Flexible use of stack ; Encountered a string that needs to be modified , Remember to use StringBuilder
14. Search and backtracking algorithms ( secondary )
14.1 The finger of the sword Offer 12. Path in matrix
14.2 The finger of the sword Offer 13. The range of motion of the robot
15. Search and backtracking algorithms ( secondary )
15.1 The finger of the sword Offer 34. The path of a value in a binary tree
15.2 The finger of the sword Offer 36. Binary search tree and double linked list
15.2 The finger of the sword Offer 54. The second of binary search tree k Big node
16. Sort ( Simple )(√)
16.1 The finger of the sword Offer 45. Make the array the smallest number
-
Title Description
-
Need a deep understanding of sorting , Treat an integer array as a string , Then sort according to the sorting rules
-
Code details
class Solution {
public String minNumber(int[] nums) {
// The focus is on rewriting the sorting algorithm
//1) Convert array to integer first
String[] string=new String[nums.length];
for(int i=0;i<string.length;i++){
string[i]=String.valueOf(nums[i]);
}
//2) Rewrite the sorting method of string array , Use lambda expression , Shorthand // Be careful compareTo Use , If the sequence remains the same , So that's the order
// It's easy to get wrong : front - Back . Or compare the front with the back : It's ascending ; Back - front . Or compare the back with the front : It's descending
Arrays.sort(string,(String a,String b)->(a+b).compareTo(b+a));
// Convert the string array into a string
StringBuilder builder=new StringBuilder();
for(String i:string){
builder.append(i);
}
return builder.toString();
}
}
- matters needing attention
1) Make use of sorting algorithm
2) Common sorting algorithms should be able to write ( Quick line up , Bubble sort , Heap sort )
3) rewrite sort Sort : To be able to rewrite the sorting algorithm , According to your own rules 【a-b Negative numbers are in ascending order ;b-a Positive numbers are in reverse order 】
16.2 The finger of the sword Offer 61. Shunzi in playing cards
- Title Description
- Code instructions
1) Need to find the number of zeros , Then calculate the maximum value of the difference , See if the two match .
2) The core idea is a topic of finding rules .
class Solution {
public boolean isStraight(int[] nums) {
//1) Prioritize
Arrays.sort(nums);
//2) See if there are non-zero duplicates , And write down the number that is zero
int size=0;
for(int i=1;i<5;i++){
if(nums[i-1]==0){
size++;
}else{
if(nums[i]==nums[i-1]) return false;
}
}
//3) Calculate non-zero maximum - minimum value
int sum=nums[4]-nums[size];
//4) If both are less than or equal to 4, Then it's right
if(sum<=4) return true;
return false;
}
}
17. Sort ( Simple )(√)
17.1 The finger of the sword Offer 40. The smallest k Number ** Classic title , Be sure to watch more
1. Title Description 2. The code analysis ( Improvement of using fast platoon , The time complexity is O(n)class Solution {
public int[] smallestK(int[] arr, int k) {
// Improvement of fast exhaust
method(arr,0,arr.length-1,k);
return Arrays.copyOfRange(arr,0,k);
}
public static void method (int[] arr,int first,int end,int k){
int left=first;
int right=end;
//1) A special case
if(left>=end) return;
//2) General operation
int target=arr[left];
while(left<right){
//1) Look for left and right exchange values
while(left<right && arr[right]>target) right--;
while(left<right && arr[left]<=target) left++;
// Data exchange (arr[left],arr[right])
int temp=arr[left];
arr[left]=arr[right];
arr[right]=temp;
}
// Initial and intermediate exchange (arr[first],arr[left])
arr[first]=arr[left];
arr[left]=target;
//3) Recursive operation
if(left<k){
method(arr,left+1,end,k);
}else if(left>k){
method(arr,first,left-1,k);
}else{
return;
}
}
}
- matters needing attention
1) This topic has : Big pile top , Improved algorithm of fast scheduling and fast scheduling
2) Attention should be paid to the storage and elimination of data in large top reactor , Using the queue method , And the way to rewrite the big top heap ( The default is small top heap , The smallest number of them )
3) The idea of quick platoon must be mastered , The idea of recursion .( Improvement based on fast scheduling , It's just a change of direction )
17.2 The finger of the sword Offer 41. Median in data stream ( Difficult topics , Didn't do it )
18. Search and backtracking algorithms ( secondary )
18.1 The finger of the sword Offer 55 - I. The depth of the binary tree
18.2 The finger of the sword Offer 55 - II. Balanced binary trees
19. Search and backtracking algorithms ( secondary )
19.1 The finger of the sword Offer 64. seek 1+2+…+n
19.2 The finger of the sword Offer 68 - I. The nearest common ancestor of a binary search tree
19.2 The finger of the sword Offer 68 - I. The nearest common ancestor of a binary search tree
19.3 The finger of the sword Offer 68 - II. The nearest common ancestor of a binary tree
20. Divide and conquer algorithm ( secondary )
20.1 The finger of the sword Offer 07. Reconstruction of binary tree
20.2 The finger of the sword Offer 16. Integer power of value
20.3 The finger of the sword Offer 33. The post order traversal sequence of binary search tree
版权声明
本文为[White horse is not a horse·]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204231407524584.html
边栏推荐
- MySQL error packet out of order
- Nacos program connects to mysql8 0+ NullPointerException
- 【thymeleaf】处理空值和使用安全操作符
- Unity_ Code mode add binding button click event
- [NLP] HMM hidden Markov + Viterbi word segmentation
- 填充每个节点的下一个右侧节点指针 II [经典层次遍历 | 视为链表 ]
- About UDP receiving ICMP port unreachable
- Compiling OpenSSL
- Thread synchronization, life cycle
- Analysis of common storage types and FTP active and passive modes
猜你喜欢
Detailed explanation of C language knowledge points -- data types and variables [1] - carry counting system
How to use OCR in 5 minutes
setcontext getcontext makecontext swapcontext
分布式事务Seata介绍
LeetCode165-比较版本号-双指针-字符串
Share 20 tips for ES6 that should not be missed
Swift: entry of program, swift calls OC@_ silgen_ Name, OC calls swift, dynamic, string, substring
Mds55-16-asemi rectifier module mds55-16
Provided by Chengdu control panel design_ It's detailed_ Introduction to the definition, compilation and quotation of single chip microcomputer program header file
My raspberry PI zero 2W toss notes to record some problems and solutions
随机推荐
Have you really learned the operation of sequence table?
LeetCode162-寻找峰值-二分-数组
Async void caused the program to crash
LeetCode 练习——396. 旋转函数
Detailed explanation of C language knowledge points - data types and variables [2] - integer variables and constants [1]
Kubernetes详解(九)——资源配置清单创建Pod实战
Basic operation of circular queue (Experiment)
[proteus simulation] automatic range (range < 10V) switching digital voltmeter
Reptile exercises (1)
Swift protocol Association object resource name management multithreading GCD delay once
Sqlserver transaction and lock problem
如何设计一个良好的API接口?
What is the effect of Zhongfu Jinshi wealth class 29800? Walk with professional investors to make investment easier
How to design a good API interface?
Mysql连接查询详解
免费在upic中设置OneDrive或Google Drive作为图床
小红书 timestamp2 (2022/04/22)
Go basic reflection
nuxt项目:全局获取process.env信息
8.4 realization of recurrent neural network from zero