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

- Flow Chart77 blogs
- Java38 blogs
- Python30 blogs
- MySQL16 blogs
- Linux16 blogs
- Android15 blogs
- Administration13 blogs
- Database12 blogs
- more...

Daily Recommendation

©2020 ioDraw All rights reserved

Huawei Hongmeng system learning notes 9- Ecological construction of developers JavaScript Do a simple guess number games Centralized processing （mean centering） The myth and truth of JS Experimental summary of basic key knowledge ( whole ) Detailed explanation PHP Medium die,exit,returnPython Student information management system ( Lite )re Common methods of modules stata Basic operation of linear regression analysis flutter study -- Search box Docker Import of containers and mirrors , export