First of all, I will introduce the meaning of the algorithm for us . In the actual project , There are many scenarios in which the algorithm is used , as “Java8 in Hashmap Using red and black trees to achieve ”,“
Redis Bottom use LRU Come in and do the elimination strategy ”,“ Many problems in the field of big data are based on TopK”,“JS In the prototype chain, the loop detection is similar to the linked list ”,“ Particularly complex business logic often involves DAG
”,“MySql Why index B+ tree ”,“Oracle How to realize the windowing function in ” Wait, wait, wait . in short ,
It is precisely because the algorithm title only retains the essential elements , The other unimportant parts were discarded , Therefore, we can build an optimal environment for each person to learn to solve problems
, And growth and improvement in this environment , Will have a profound impact on the career of a software engineer , Even the first life . therefore , Please have an ingenuity ,
You can choose not to learn to master algorithms , But please don't delay others' progress . one's nobility lasts forever , A long way to go , Precious , I'll see you again !
<> One ,LeetCode 350 topic Find the difference between two sets
<>1.1 Topic analysis
Let's start with a topic ： The first 350 topic ： The intersection of two arrays
demand ： Given two arrays , Write a function to calculate their intersection .
Instance code
input : nums1 = [1,2,2,1], nums2 = [2,2] output : [2,2] input : nums1 = [4,9,5], nums2 = [9,
4,9,8,4] output : [4,9]
According to the example code analysis ：
* The output should appear the same number of times as two sets given together .
* We don't want to test the sorting problem here
* First of all, when you take this topic , We should first think about using map To map
, Why can we look at that like this , Because we need to find the elements in the intersection of two arrays , At the same time, it should be consistent with the number of times in both arrays , As a result, we need to control the number of times of each value string , So the mapping relationship becomes < element , The number of times an element appears >
<>1.2 Topic explanation
on analysis , Suppose we have two arrays, which are ; nums1=[1,2,2,2] , nums2=[2,2]
First, we define a map Used to store data in one of the arrays , Loop into the array
for the first time map There is no such element in, so value by 1
second , Three times map If there is this element in value+1 And so on , It's like using map calculation wordCount
First, we need to judge map Is this data in , If so, add them ( The logic behind it is the same )
The second stage
First define an empty array . We have it now map after ,map It stores each of our elements and the number of their occurrences , And then we're going through it nums2 This array , Take each element map in get Data if get It's the data value Frequency reduction 1, Put this key Copy to empty array .
<>1.3 code analysis
public static int[] intersect(int[] nums1, int[] nums2) { // Empty operation if (nums1 ==
null|| nums1.length == 0 || nums2 == null || nums2.length == 0) { return new int
[0]; } //1. Define a map Used to store the values that appear in an array value Number of storage occurrences HashMap<Integer, Integer> map =
new HashMap<>(); for (int i = 0; i < nums1.length; i++) { Integer integer = map.
get(nums1[i]); if (integer == null) { map.put(nums1[i], 1); } else { map.put(
nums1[i], integer + 1); } } int k = 0; for (int i = 0; i < nums2.length; i++) {
Integer integer= map.get(nums2[i]); if (integer != null) { if (integer > 0) {
nums2[k] = nums2[i]; map.put(nums2[i], integer - 1); k++; } } } return Arrays.
copyOfRange(nums2, 0, k); }
<>1.4 Advanced topics （ optimization ）
premise : First, we need to sort the two arrays
What if the given array is already ordered ? How will you optimize your algorithm ? Let's analyze it , Suppose both arrays are ordered , Respectively ： nums1=[1,2,2,2] , nums2=[2,2]
Problem solving steps ：
<1> If the elements of the two pointers are not the same , We move the small pointer back and we're judging
<2> If the two elements are the same , Then both pointers move backward at the same time
<3> Until any array is terminated .
<>1.5 code analysis
public static int[] intersect2(int[] nums1, int[] nums2) { if (nums1 == null ||
nums1.length == 0 || nums2 == null || nums2.length == 0) { return new int[0]; }
int i = 0, j = 0, k = 0; Arrays.sort(nums1); Arrays.sort(nums2); while (i <
nums1.length && j < nums2.length) { if (nums1[i] > nums2[j]) { j++; } else if (
nums1[i] < nums2[j]) { i++; } else { nums2[k] = nums1[i]; i++; j++; k++; } }
return Arrays.copyOfRange(nums2, 0, k); }
<> Two ,LeetCode 14 Longest Common Prefix
<>2.1 Topic analysis
Let's start with a topic ： The first 14: Longest Common Prefix
demand ： Write a function to find the longest common prefix in a string array . If there is no public prefix , Return to ""
Instance code
input : ["flower","flow","flight"] output : "fl" input : ["dog","racecar","car"] output : ""
Topic analysis ：
We're looking for the longest common prefix , So first of all, the prefix is public , We can find him in any element . Suppose we look for the longest common prefix from an array , So first of all , We can set the first element as the base element x0. If the array is [“flow”,“flower”,“flight”],flow That's our benchmark element x0.
Then we just need to compare the base element with the following elements in turn （ Suppose the following elements are x1,x2,x3…）,
Update benchmark elements continuously , Until the base element and all elements satisfy the condition for the longest common prefix , You can get the longest common prefix .
Comparison process ：
* If strs[i].indexOf(x0,x) ==
0, Skip it directly （ Because at this time x namely x1 Longest common prefix for ）, Compare the next element .（ as flower and flow Compare ）
* If strs[i].indexOf(x0,x) != 0,
The base element is truncated x Last element of , Again and again x1 Compare , Until satisfied strs[i].indexOf(x0,x) ==
0, At this time, the intercepted x by x and x1 Longest common prefix for .（ as flight and flow Compare , Cut out in turn flow-flo-fl, until fl It was cut out , here fl by flight and flow Longest common prefix for ）
<>2.2 Graphic analysis
<>2.3 code analysis
public static String longestCommonPrefix(String[] strs) { if (strs.length==0 ||
strs[0].length()==0){ return ""; } String mondel = strs[0].substring(0, strs[0]
.length() - 1); for (int i = 0; i < strs.length; i++) { if (mondel.length()==0){
return ""; } if (strs[i].indexOf(mondel)!=0){ while (true){ mondel=mondel.
substring(0,mondel.length()-1); if (mondel.length()==0){ break; } if (strs[i].
indexOf(mondel)==0){ break; } } } } return mondel==null? "":mondel; }
<> Three ,LeetCode The best time to buy and sell stocks （I,II）
The frequency of interview is very high . Change the conditions a little , We can't defend ourselves . How can we solve this kind of problem ? Let's start with the cheapest one .
<>3.1 121 topic The best time to buy and sell stocks I
<>3.1.1 Topic analysis
Let's start with a topic ： The first 121 topic ： The best time to buy and sell stocks I
demand ： Give an array , Its first i An element is a given stock number i Day's price .
If you are only allowed to complete one transaction at most （ That is to buy and sell a stock once ）, Design an algorithm to calculate the maximum profit you can make .
be careful ： You can't sell stocks before you buy them .
Examples 1：
input : [7,1,5,3,6,4] output : 5
explain ： In the 2 day （ Stock price = 1） When to buy , In the 5 day （ Stock price = 6） When to sell , Maximum profit = 6-1 = 5 .
be careful ： Note that profits cannot be 7-1 = 6, Because the selling price needs to be greater than the buying price ; meanwhile , You can't sell stocks before you buy them .
Examples 2:
input : [7,6,4,3,1] output : 0
explain ： under these circumstances , No deal completed , So the maximum profit is 0.
<>3.2.2 Graphic analysis
Suppose we buy the next day , Sell on the day when earnings are high
Execution process
Second execution
The third execution … and so on , When we're done with the loop maxV You get the maximum benefit from the entire array .
<>3.1.3 code analysis
public static int maxProfit(int[] prices) { int maxProfit = 0, fi = 0, maxV = 0
; for (int i = 1; i < prices.length; i++) { fi = Math.max(maxProfit + prices[i]
- prices[i - 1], 0); maxV = Math.max(fi, maxV); maxProfit = fi; } return maxV; }
<>3.2 122 topic The best time to buy and sell stocks II
<>3.2.1 Topic analysis
Let's start with a topic ： The first 122 topic ： The best time to buy and sell stocks II
demand ： Give an array , Its first i An element is a given stock number i Day's price .
Design an algorithm to calculate the maximum profit you can make . You can do as many deals as you can （ Buy and sell a stock many times ）.
be careful ： You can't participate in multiple transactions at the same time （ You have to sell the stock before you buy it again ）
Examples 1
input : [7,1,5,3,6,4] output : 7
explain : In the 2 day （ Stock price = 1） When to buy , In the 3 day （ Stock price = 5） When to sell , The exchange is profitable = 5-1 = 4 .
subsequently , In the 4 day （ Stock price = 3） When to buy , In the 5 day （ Stock price = 6） When to sell , The exchange is profitable = 6-3 = 3 .
Examples 2:
input : [1,2,3,4,5] output : 4
explain : In the 1 day （ Stock price = 1） When to buy , In the 5 day （ Stock price = 5） When to sell , The exchange is profitable = 5-1 = 4 .
Notice that you can't be in the 1 Day and day 2 Day after day buying stocks , Then sell them .
Because it is involved in multiple transactions at the same time , You have to sell the stock before you buy it again .
Example 3
input : [7,6,4,3,1] output : 0
explain : under these circumstances , No deal completed , So the maximum profit is 0.
<>3.2.2 Graphic analysis
Suppose our data is ：[7, 1, 5, 3, 6, 4]
From the image above , We can observe A+B+C The sum of is equal to the difference DD The height difference of the corresponding continuous peak and valley .
<>3.2.3 code analysis
public int maxProfit(int[] prices) { int maxProfit=0; for (int i = 1; i <
prices.length ; i++) { if (prices[i] > prices[i - 1]) { maxProfit += prices[i] -
prices[i - 1]; } } return maxProfit; }
<> Four ,LeetCode 189 Rotate array
<>4.1 Topic analysis
Let's start with a topic ： The first 189 topic ： Rotate array
demand ： Give an array , Moves the elements in the array to the right k Locations , among k It is a non negative number
Examples 1:
input : [1,2,3,4,5,6,7] and k = 3 output : [5,6,7,1,2,3,4]
explain :
Turn right 1 step : [7,1,2,3,4,5,6]
Turn right 2 step : [6,7,1,2,3,4,5]
Turn right 3 step : [5,6,7,1,2,3,4]
Examples 2:
input : [-1,-100,3,99] and k = 2 output : [3,99,-1,-100]
explain :
Turn right 1 step : [99,-1,-100,3]
Turn right 2 step : [3,99,-1,-100]
be careful ：
Think of as many solutions as you can , There are at least three different ways to solve this problem .
The required space complexity is O(1) Of In situ algorithm .
<>4.2 Graphic analysis
Suppose our array is [1,2,3,4,5,6],I=6 And k=3
By observing, we can get , We want to get the final result . We just need to invert all the elements , And then reverse the front k Elements , Then reverse the back l-k Elements , You can get the results you want .
<>4.3 code analysis
public static void rotate(int[] nums, int k) { revers(nums, 0, nums.length);
revers(nums, 0, k % nums.length); revers(nums, k % nums.length, nums.length); }
public static void revers(int[] nums, int start, int end) { int length = end -
start; for (int i = 0; i < length / 2; i++) { int num = nums[start + i]; nums[
start+ i] = nums[start + length - i - 1]; nums[start + length - i - 1] = num; }
System.out.println(Arrays.toString(nums)); }
Technology