1. Sum of two numbers
Topic introduction
Given an integer array nums and an integer target value target, please find the two integers with sum as the target value in the array and return their array subscripts.
You can assume that each input will correspond to only one answer. However, the same element in the array cannot appear repeatedly in the answer.
You can return answers in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9 Output:[0,1] Explanation: because nums[0] + nums[1] == 9 ，return [0, 1] .
Example 2:
Input: nums = [3,2,4], target = 6 Output:[1,2]
Example 3:
Input: nums = [3,3], target = 6 Output:[0,1]
Tips:
- 2 <= nums.length <= 103
- -109 <= nums[i] <= 109
- -109 <= target <= 109
- There will only be one valid answer
Source: LeetCode
Link: https://leetcode-cn.com/problems/two-sum
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
Topic realization
The easiest way to think of is to enumerate every number x in the array and find out whether target - x exists in the array. When we use the method of traversing the entire array to find target - x, we need to note that each element before X has already matched x, so we don't need to match it any more. Each element cannot be used twice, so we only need to look for target - x in the elements after X.
class Solution {
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[0];
}
}
Note that the reason for the high time complexity of the previous solution is that the time complexity of finding target - x is too high.
Therefore, we need a better method to quickly find whether there are target elements in the array. If it exists, we need to find its index.
Using the hash table, the time complexity of finding target - x can be reduced from O(N) to O(1).
We create a hash table. For each x, we first query whether target - x exists in the hash table, and then insert x into the hash table to ensure that X does not match itself.
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (hashMap.containsKey(target - nums[i])) {
return new int[]{hashMap.get(target - nums[i]), i};
}
hashMap.put(nums[i], i);
}
return new int[0];
}
}
164. Maximum spacing
Topic introduction
Given an unordered array, find out the maximum difference between adjacent elements of the array after sorting.
If the number of array elements is less than 2, 0 is returned.
Example 1:
input: [3,6,9,1] output: 3 explain: The sorted array is [1,3,6,9], Where adjacent elements (3,6) and (6,9) There is a maximum difference between 3.
Example 2:
input: [10] output: 0 explain: The number of array elements is less than 2, so 0 is returned.
explain:
- You can assume that all elements in the array are non negative integers and the values are within the range of 32-bit signed integers.
- Please try to solve this problem under the condition of linear time complexity and space complexity.
Source: LeetCode
Link: https://leetcode-cn.com/problems/maximum-gap
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
Topic realization
We first check the criticality of the incoming array, and then sort the array. Just call the library function directly.
Then compare them in pairs from left to right, find out the largest spacing, and then re assign it to maxSpace.
class Solution {
public int maximumGap(int[] nums) {
if (nums == null || nums.length < 2) return 0;
Arrays.sort(nums);
int maxSpace = 0;
for (int i = 1; i < nums.length; i++) {
maxSpace = Math.max(maxSpace, nums[i] - nums[i - 1]);
}
return maxSpace;
}
}
240. Search two-dimensional matrix II
Topic introduction
Write an efficient algorithm to search a target value target in m x n matrix.
The matrix has the following characteristics:
- The elements of each row are arranged in ascending order from left to right.
- The elements of each column are arranged in ascending order from top to bottom.
Example 1:
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5 Output: true
Example 2:
Input: matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20 Output: false
Tips:
- m == matrix.length
- n == matrix[i].length
- 1 <= n, m <= 300
- -109 <= matix[i][j] <= 109
- All elements of each row are arranged in ascending order from left to right
- All elements of each column are arranged in ascending order from top to bottom
- -109 <= target <= 109
Same title:
Source: LeetCode
Link: https://leetcode-cn.com/problems/search-a-2d-matrix-ii
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
Topic realization
If target = 5, let's see how to find quickly without using violent search.
Start from the upper right corner, 15 > 5, so we need to move to the left. Why not move down, because the number down is greater than 15.
After moving to the left, 11 > 5, so we need to move to the left. Why not move down, because the number down is greater than 11.
After moving to the left, 7 > 5, so we need to move to the left. Why not move down, because the number down is greater than 7.
After moving to the left, 4 < 5, so we need to move down. Why not move to the left, because the number to the left is smaller than 4.
After moving down, 5 = 5, so we need to return true.
Maybe the above steps are not difficult to understand, but some people may think, why not start searching from 1 in the upper left corner? The reason is very simple. The lower side of 1 in the upper left corner is larger than 1, the right side of 1 in the upper left corner is larger than 1, and both are larger. How do you know whether to go down or Cuan right? Similarly, the 30 in the lower right corner is also similar. Looking left is smaller than 30, and looking up is smaller than 30. Both are small. How do you know whether it should be left or on the ridge? Therefore, the positive solution is to search from 18 in the lower left corner or 15 in the upper right corner. Because when the target is greater than, less than or equal to the value of the current array element, there is no ambiguity.
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
// Criticality check
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
// Get the number of rows
int rows = matrix.length;
// Get the number of columns
int cols = matrix[0].length;
// Define row pointer
int row = 0;
// Define column pointer (search from the top right corner)
int col = cols - 1;
// Circular search
while ((row >= 0 && row < rows) && (col >= 0 && col < cols)) {
if (target > matrix[row][col]) {
row++;
} else if (target < matrix[row][col]) {
col--;
} else {
return true;
}
}
// Can't find
return false;
}
}
26. Delete duplicates in ordered array
Topic introduction
Delete each element of the array and return it to you only once after deleting the new element.
Do not use additional array space. You must modify the input array in place and complete it with O(1) additional space.
explain:
Why is the returned value an integer, but the output answer is an array?
Note that the input array is passed by reference, which means that modifying the input array in the function is visible to the caller.
You can imagine the internal operation as follows:
// nums is passed by reference. That is, no copy of the arguments is made
int len = removeDuplicates(nums);
// Modifying the input array in the function is visible to the caller.
// According to the length returned by your function, it will print out all elements within that length range in the array.
for (int i = 0; i < len; i++) {
print(nums[i]);
}
Example 1:
Input: nums = [1,1,2] Output: 2, nums = [1,2] Explanation: the function should return a new length of 2 and the original array nums The first two elements of are modified to 1, 2 . There is no need to consider the elements in the array that exceed the new length.
Example 2:
Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5, nums = [0,1,2,3,4] Explanation: the function should return a new length of 5 and the original array nums The first five elements of are modified to 0, 1, 2, 3, 4 . The length of the following elements in the array does not need to be considered.
Tips:
- 0 <= nums.length <= 3 * 104
- -104 <= nums[i] <= 104
- nums is arranged in ascending order
Source: LeetCode
Link: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
Topic realization
Two pointers are defined. One pointer is used to scan from left to right in turn. We call it fast pointer, and the other pointer is used to store non repeated numbers. Due to the slow movement, we call it slow pointer. At the beginning of the definition, slow should start from 0, but fast doesn't have to start from 0. It's unwise to compare yourself with yourself, as shown in the following figure:
Start the first round of comparison. If the element pointed by the fast pointer is equal to the element pointed by the slow pointer, the fast pointer can be moved back directly.
Start comparing again. If the element pointed by the fast pointer is different from the element pointed by the slow pointer, add the slow pointer, and then put the element pointed by the fast pointer into the position pointed by the slow pointer, and the fast pointer can move back directly.
Scan backward according to the above mode until all the fast pointers are scanned, and the final result will come out. However, when we return, because the slow pointer is a subscript and does not represent the length of the new array, we need to add and return again and again.
class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int slow = 0;
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[slow]) {
nums[++slow] = nums[fast];
}
}
return slow + 1;
}
}
27. Remove elements
Topic introduction
Give you an array num and a value val. you need to remove all elements with a value equal to Val in place and return the new length of the array after removal.
Instead of using extra array space, you must use only O(1) extra space and modify the input array in place.
The order of elements can be changed. You don't need to consider the elements in the array that exceed the new length.
explain:
Why is the returned value an integer, but the output answer is an array?
Note that the input array is passed by reference, which means that modifying the input array in the function is visible to the caller.
You can imagine the internal operation as follows:
// nums is passed by reference. That is, no copy of the arguments is made
int len = removeElement(nums, val);
// Modifying the input array in the function is visible to the caller.
// According to the length returned by your function, it will print out all elements within that length range in the array.
for (int i = 0; i < len; i++) {
print(nums[i]);
}
Example 1:
Input: nums = [3,2,2,3], val = 3 Output: 2, nums = [2,2] Explanation: the function should return a new length of 2, also nums The first two elements in are both 2. You don't need to consider the elements in the array that exceed the new length. For example, the new length returned by the function is 2, and nums = [2,2,3,3] or nums = [2,2,0,0]，It will also be regarded as the correct answer.
Example 2:
Input: nums = [0,1,2,2,3,0,4,2], val = 2 Output: 5, nums = [0,1,4,0,3] Explanation: the function should return a new length of 5, also nums The first five elements in are 0, 1, 3, 0, 4. Note that these five elements can be in any order. You don't need to consider the elements in the array that exceed the new length.
Tips:
- 0 <= nums.length <= 100
- 0 <= nums[i] <= 50
- 0 <= val <= 100
Source: LeetCode
Link: https://leetcode-cn.com/problems/remove-element
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
Topic realization
Two pointers are defined. One pointer is used to scan from left to right. We call it fast pointer, and the other pointer is used to store numbers different from val. due to its slow movement, we call it slow pointer. At the beginning of definition, slow should start from 0, and fast must also start from 0, as shown in the following figure:
If val = 2, start the first cycle, and the element pointed to by the fast pointer is not equal to val, copy the element corresponding to the fast pointer to the position corresponding to the slow pointer, and then add the fast pointer and add the slow pointer.
Similarly, if the element pointed to by the fast pointer is not equal to val, the element corresponding to the fast pointer should be copied to the position corresponding to the slow pointer, and then the fast pointer and the slow pointer should be added.
At this time, if the element pointed to by the fast pointer is equal to val, the fast pointer can be added directly.
At this time, if the element pointed to by the fast pointer is equal to val, the fast pointer can be added directly.
The pointer should be added to the position corresponding to the copied element, and then the pointer should be added to the position corresponding to the slower and faster element, and then the pointer should be added to the position corresponding to the slower and faster element.
According to the above mode, the fast pointer scans backward until all scans are completed, and the final result comes out. The slow pointer corresponds to the size of the new array.
class Solution {
public int removeElement(int[] nums, int val) {
if (nums.length == 0) return 0;
int slow = 0;
for (int fast = 0; fast < nums.length; fast++) {
if (nums[fast] != val) {
nums[slow++] = nums[fast];
}
}
return slow;
}
}
75. Color classification
Topic introduction
Given an array of n elements including red, white and blue, sort them in place so that the elements of the same color are adjacent and arranged in the order of red, white and blue. In this question, we use integers 0, 1 and 2 to represent red, white and blue respectively.
Example 1:
Input: nums = [2,0,2,1,1,0] Output:[0,0,1,1,2,2]
Example 2:
Input: nums = [2,0,1] Output:[0,1,2]
Example 3:
Input: nums = [0] Output:[0]
Example 4:
Input: nums = [1] Output:[1]
Tips:
- n == nums.length
- 1 <= n <= 300
- Num [i] is 0, 1, or 2
Advanced:
- Can you solve this problem without using the sorting function in the code base?
- Can you think of a one pass scan algorithm that uses only constant space?
Source: LeetCode
Link: https://leetcode-cn.com/problems/sort-colors
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
Topic realization
To solve this problem, scan it again. Just put 0 on the left of the array and 2 on the right of the array. Therefore, we need to define at least two pointers. One pointer is used to store 0 and the other pointer is used to store 2. In addition to these two pointers, we also need a pointer to scan from left to right, so it is three pointers.
Scan from left to right. When the element is 2, exchange the value pointed by the black and blue pointer, and then subtract the blue pointer.
However, it should be noted here that it is possible that the position pointed by the blue pointer is also a 2. After changing the position, we need to make another judgment.
Before exchange (changed a picture):
After exchange (after exchange in the figure above):
We need to judge again according to the situation in the above figure. If the black pointer still points to 2, let it exchange with the value pointed to by the blue pointer, and then subtract the blue pointer and add the black pointer.
If 0 is encountered during scanning, exchange the value pointed by the black pointer with the value pointed by the green pointer, and then add the green pointer and add the black pointer.
At this time, if the black pointer scanning still encounters 2, it will be exchanged with the value pointed by the blue pointer, then the blue pointer will be subtracted, and then the second judgment will be made.
During the second judgment, it is found that the value pointed by the black pointer is 1. 1 does not need to be placed on the left or right of the array, so skip directly, that is, add the black pointer.
At this time, we find that the elements in the array are already in order, and the end condition is to exit the loop when the black pointer is greater than the blue pointer.
class Solution {
public void sortColors(int[] nums) {
int i = 0; //scanning
int l = 0; //Zero
int r = nums.length - 1; //Put two
while (i <= r) {
if (nums[i] == 0) {
swap(nums, l++, i++);
} else if (nums[i] == 1) {
i++;
} else {
swap(nums, r--, i);
}
}
}
/**
* Swap elements in array
*
* @param nums array
* @param i1 Index 1
* @param i2 Index 2
*/
public void swap(int[] nums, int i1, int i2) {
int tmp = nums[i1];
nums[i1] = nums[i2];
nums[i2] = tmp;
}
}
977. Square of ordered array
Topic introduction
Give you an integer array nums sorted in non decreasing order, and return a new array composed of the square of each number. It is also required to sort in non decreasing order.
Example 1:
Input: nums = [-4,-1,0,3,10]
Output:[0,1,9,16,100]
Explanation: after squaring, the array becomes [16,1,0,9,100]
After sorting, the array becomes [0,1,9,16,100]
Example 2:
Input: nums = [-7,-3,2,3,11] Output:[4,9,9,49,121]
Tips:
- 1 <= nums.length <= 104
- -104 <= nums[i] <= 104
- nums is sorted in non decreasing order
Advanced:
- Please design an algorithm with time complexity O(n) to solve this problem.
Source: LeetCode
Link: https://leetcode-cn.com/problems/squares-of-a-sorted-array
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
Topic realization
The main idea to solve this problem is to define two pointers, pointing to the first element and the last element after square, and then define a new array.
Judge which element the two pointers point to is larger, store the large value in the new array, and then move the pointer pointing to one side of the large element to subtract the pointer of the new array.
class Solution {
public int[] sortedSquares(int[] nums) {
// Create a new array
int[] tmps = new int[nums.length];
// Define three pointers
int i = nums.length - 1;
int l = 0;
int r = nums.length - 1;
while (l <= r) {
if (nums[l] * nums[l] >= nums[r] * nums[r]) {
tmps[i--] = nums[l] * nums[l++];
} else {
tmps[i--] = nums[r] * nums[r--];
}
}
// Return the final result
return tmps;
}
}
Sword finger Offer 03 Duplicate number in array
Topic introduction
Find duplicate numbers in the array.
All numbers in an array num of length n are in the range of 0 ~ n-1. Some numbers in the array are repeated, but I don't know how many numbers are repeated, or how many times each number is repeated. Please find any duplicate number in the array.
Example 1:
Input: [2, 3, 1, 0, 2, 5, 3] Output: 2 or 3
Restrictions:
- 2 <= n <= 100000
Source: LeetCode
Link: https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
Topic realization
We can take advantage of the feature that set set elements cannot be repeated, cycle through the array elements and add them to the set set in turn. If the addition fails, it means that the number is repeated.
class Solution {
public int findRepeatNumber(int[] nums) {
HashSet<Integer> hashSet = new HashSet<>();
for (int num : nums) {
if (!hashSet.add(num)) {
return num;
}
}
return -1;
}
}
10.01. Merge sorted arrays
Topic introduction
Given two sorted arrays A and B, there is enough buffer space at the end of A to accommodate B. Write A method to merge B into A and sort.
The number of elements initializing A and B is m and n, respectively.
Example:
input: A = [1,2,3,0,0,0], m = 3 B = [2,5,6], n = 3 output: [1,2,2,3,5,6]
explain:
- A.length == n + m
Same title:
Source: LeetCode
Link: https://leetcode-cn.com/problems/sorted-merge-lcci
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
Topic realization
Define three pointers, one pointer to the last element of valid data of array A, one pointer to the last element of array B, and one pointer to the last element of array A. The specific implementation idea is to compare the size of the data corresponding to the green pointer and the orange pointer, take out A larger value and put it where the black pointer points, and then subtract the pointer.
In this process, the end condition of the orange pointer is bi > = 0, and the green pointer should also meet AI > = 0. The final code is as follows:
class Solution {
public void merge(int[] A, int m, int[] B, int n) {
int ai = m - 1;
int bi = n - 1;
int cur = A.length - 1;
while (bi >= 0) {
if (ai >= 0 && A[ai] > B[bi]) {
A[cur--] = A[ai--];
} else {
A[cur--] = B[bi--];
}
}
}
}
16.16. Partial sorting
Topic introduction
Given an integer array, write a function to find the indexes m and N. as long as the elements of the index interval [m,n] are arranged in order, the whole array is ordered. Note: n-m should be minimized, that is, find the shortest sequence that meets the conditions. The return value of the function is [m,n]. If there are no such m and n (for example, the whole array is ordered), please return [- 1, - 1].
Example:
Input: [1,2,4,7,10,11,7,12,6,7,16,18,19] Output: [3,9]
Tips:
- 0 <= len(array) <= 1000000
Source: LeetCode
Link: https://leetcode-cn.com/problems/sub-sort-lcci
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
Topic realization
First, we scan from left to right. If we encounter a value larger than max, we will directly record it, indicating that it is in ascending order from left to right. If we encounter a value smaller than max, it indicates that this position needs to be sorted. After scanning from left to right according to this mode, we can find the value of interval n.
Then we scan from right to left in turn. When we encounter a value smaller than min, we directly record it, indicating that it is in descending order from right to left. If we encounter a value larger than min, it indicates that this position needs to be sorted. After scanning from right to left according to this mode, we can find the value of interval m.
In addition to the above problem-solving ideas, it should also be noted that the length of the array may be 0. Therefore, we need to judge the length of the array.
class Solution {
public int[] subSort(int[] array) {
if (array.length == 0) return new int[]{-1, -1};
// Scan the right subscript of the reverse order pair from left to right (positive order, from small to large)
int max = array[0];
int r = -1;
for (int i = 1; i < array.length; i++) {
if (array[i] >= max) {
max = array[i];
} else {
r = i;
}
}
// If you scan from left to right and find no position to sort, return
if (r == -1) return new int[]{-1, -1};
// Scan the left subscript of the reverse order pair from right to left (reverse order, from large to small)
int min = array[array.length - 1];
int l = -1;
for (int i = array.length - 2; i >= 0; i--) {
if (array[i] <= min) {
min = array[i];
} else {
l = i;
}
}
return new int[]{l, r};
}
}