✅🎡 Personal homepage: Program ape chase
✅🎡 Series column: Algorithm set
✅🎡 Current status: create Java learning road (zero foundation to employment practice) series, which is currently updated to JAVAWEB development
✅🎡 About the author: Hello, everyone. I'm a program ape chaser, a new star creator in the whole stack field, and an algorithm enthusiast. I often rank in the top 30 of the weekly list of authors. I'm an unknown ACMer
✅🎡 Recommend a website that can't fail in question brushing, interview and job hunting—— Niuke.com
✅🎡 Personal famous saying: take advantage of youth, work hard, and give an account to yourself in the future!
Hello, everyone, I'm program ape chase. Through the last private letter in French, a little friend left a message saying, when will it be updated? see? It will come today.
catalogue
Search in two-dimensional array
Binary search-I
describe
Please realize binary search of ascending array without repeated numbers
Given an integer array nums with ascending elements and no repeated numbers and a target value target, write a function to search the target in nums. If the target value exists, return the subscript (the subscript starts from 0), otherwise return -1
Data range: 0 ≤ len (Num) ≤ 2 × 105, any value in the array meets ∣ val ∣ ≤ 109
Advanced: time complexity O(logn), space complexity O(1)
Example 1
Input:
[-1,0,3,4,6,10,13,14],13
Return value:
6
explain:
13 appears in nums with subscript 6
Example 2
Input:
[],3
Return value:
-1
explain:
Num is empty, return -1
Example 3
Input:
[-1,0,3,4,6,10,13,14],2
Return value:
-1
explain:
2 does not exist in nums, so -1 is returned
Problem solving code
import java.util.*;
public class Solution {
public int search (int[] nums, int target) {
int l = 0;
int r = nums.length - 1;
//Start from the beginning and end of the array until they meet fast template
while(l <= r){
//The value of the midpoint of each check
int m = (l + r) / 2;
if(nums[m] == target)
return m;
//Enter the left section
if(nums[m] > target)
r = m - 1;
//Enter the right section
else
l = m + 1;
}
//not found
return -1;}
}Search in two-dimensional array
describe
In a two-dimensional array (each one-dimensional array has the same length), each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. Please complete a function, input such a two-dimensional array and an integer, and judge whether the array contains the integer.
[
[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]
]
Given target = 7, return true.
Given target = 3, return false.
Data range: the length and width of the matrix meet 0 ≤ n,m ≤ 500, and the values in the matrix meet 0 ≤ val ≤ 109
Advanced: space complexity O(1), time complexity O(n+m)
Example 1
Input:
7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
Copy return value:
true
explain:
Exist 7, return true
Example 2
Input:
1,[[2]]
Return value:
false
Example 3
Input:
3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
Return value:
false
explain:
If 3 does not exist, false is returned
Problem solving code
public class Solution {
public boolean Find(int target, int [][] array) {
//Give priority to special fast template
if(array.length == 0)
return false;
int n = array.length;
if(array[0].length == 0)
return false;
int m = array[0].length;
//Start from the element in the bottom left corner to the left or up
for(int i = n - 1, j = 0; i >= 0 && j < m; ){
//The element is large, go up
if(array[i][j] > target)
i--;
//The element is small, go to the right
else if(array[i][j] < target)
j++;
else
return true;
}
return false;}
}Looking for peak
describe
Given an array num of length n, please find the peak value and return its index. The array may contain multiple peaks. In this case, just return any location.
1. Peak element refers to the element whose value is strictly greater than the left and right adjacent values. Strictly greater than, that is, there cannot be equal to
2. Assume nums[-1] = nums[n] = − ∞
3. There are nums[i] for all valid I= nums[i + 1]
4. Can you use the time complexity of O(logN) to solve this problem?
Data range:
1≤nums.length≤2×10^5
-2^31<=nums[i]<=2^31 − 1
If you enter [2,4,1,2,7,8,4], two peaks will be formed, one with index 1 and peak value 4, and the other with index 5 and peak value 8, as shown in the following figure:
Example 1
Input:
[2,4,1,2,7,8,4]
Return value:
1
explain:
Both 4 and 8 are peak elements. Index 1 of 4 or index 5 of 8 can be returned
Example 2
Input:
[1,2,3,1]
Return value:
2
explain:
3 is the peak element, and its index 2 is returned
Problem solving code
import java.util.*;
public class Solution {
public int findPeakElement (int[] nums) {
int left = 0;
int right = nums.length - 1;
//Dichotomy fast template
while(left < right){
int mid = (left + right) / 2;
//The right side is down, and there may not be a slope peak
if(nums[mid] > nums[mid + 1])
right = mid;
//On the right, it's going up. You must find the crest
else
left = mid + 1;
}
//One of the peaks
return right;}
}Reverse pairs in an array
describe
Two numbers in the array. If the previous number is greater than the following number, the two numbers form an inverse pair. Enter an array and find the total number of reverse pairs P in this array. And output the result of P's modulus of 1000000007. That is, output P mod 1000000007
Data range: for 50% of data, size ≤ 10^6
For 100% data, size ≤ 105
The values of all numbers in the array meet 0 ≤ val ≤ 1000000
Requirements: space complexity O(n), time complexity O(nlogn)
Enter Description:
The title ensures that the same number does not exist in the input array
Example 1
Input:
[1,2,3,4,5,6,7,0]
Return value:
7
Example 2
Input:
[1,2,3]
Return value:
0
Problem solving code
public class Solution {
public int mod = 1000000007;
public int mergeSort(int left, int right, int [] data, int [] temp){
// Stop dividing fast template
if (left >= right)
return 0;
//Take the middle
int mid = (left + right) / 2;
//Left right division
int res = mergeSort(left, mid, data, temp) + mergeSort(mid + 1, right, data, temp);
//Prevent overflow
res %= mod;
int i = left, j = mid + 1;
for (int k = left; k <= right; k++)
temp[k] = data[k];
for (int k = left; k <= right; k++) {
if (i == mid + 1)
data[k] = temp[j++];
else if (j == right + 1 || temp[i] <= temp[j])
data[k] = temp[i++];
//The left is larger than the right, and the answer increases
else {
data[k] = temp[j++];
// Statistical reverse order pair
res += mid - i + 1;
}
}
return res % mod;
}
public int InversePairs(int [] array) {
int n = array.length;
int[] res = new int[n];
return mergeSort(0, n - 1, array, res);}
}Algorithms are extremely important to programmers. The language and development platform are constantly changing, but those algorithms and theories remain unchanged. I vaguely remember my senior who played well (he got an offer in his sophomore year). He told me that if I want to find a good job, it must be essential to brush questions
At present, there are quite a lot of algorithm question brushing platforms. I would like to introduce a platform that I think is most closely related to big companies—— Niuke.com