Common data structures
1. Sets
2. Sorting
3.Binary
-Template
/**
* Raw/Binary Search: In an ordered array, the existence of the search element target, the existence of a return index, and the absence of a Return-1
*/
public static int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
return mid;
}
}
return -1;
}
/**
* Binary search: in an ordered array, find the element target, the leftmost boundary that appears, have a return index, do not have a Return-1
*/
public static int binarySearchLeft(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
right = mid - 1; // Continue to determine the leftmost boundary
}
}
if (left >= nums.length || nums[left] != target) {
return -1;
}
return left;
}
/**
* Binary lookup: in an ordered array, look for the element target, the rightmost boundary that appears, there is a return index, there is no Return-1
*/
public static int binarySearchRight(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
left = mid + 1; // Continue to determine the rightmost boundary
}
}
if (right < 0 || nums[right] != target) {
return -1;
}
return right;
}
33. Search Rotated Sort Array
The integer array nums is arranged in ascending order, and the values in the array are different from each other.
Nums rotates an array to [nums[k], nums[k+1],..., nums[n-1], nums[0], nums[1],..., nums[1],..., nums[k-1] (subscript counts from zero) before passing it to the function. For example, [0,1,2,4,5,6,7] may become [4,5,6,7,0,1,2] after being rotated at subscript 3.
Give you a rotated array of nums and an integer target, which returns its subscript if the target exists in nums, or -1 if it does not.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1
Example 3:
Input: nums = [1], target = 0 output: -1
Example:
[4,5,6,7,8,1,2,3], target = 8 output:4
/**
* Method 2: Binary search
* Method 2: Direct dichotomy
* There are several possibilities to use the dichotomy directly to determine that dichotomy.
* 1. Directly equal to target
* 2. Incremental Zone on Left
* a. target Between left and mid
* b. Not Between
* 3. Incremental area on the right
* a. target Between mid and right
* b. Not Between
*/
public static int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[left] <= nums[mid]) { // Incremental to the left
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
if (left >= nums.length || nums[left] != target) {
return -1;
}
return left;
}
34. Find the first and last positions of elements in a sorted array
Given an array of integers nums in ascending order, and a target value. Find the starting and ending positions of a given target value in the array.
Returns [-1, -1] if the target value does not exist in the array.
Example 1:
Input: nums = [5,7,7,8,10], target = 8 output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6 Output: [-1,-1]
Example 3:
Input: nums = [], target = 0 output: [-1, -1]
/**
* Binary search: in an ordered array, find the element target, the leftmost boundary that appears, have a return index, do not have a Return-1
*/
public static int searchLeft(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
right = mid - 1;
}
}
if (left >= nums.length || nums[left] != target) {
return -1;
}
return left;
}
/**
* Binary lookup: in an ordered array, look for the element target, the rightmost boundary that appears, there is a return index, there is no Return-1
*/
public static int searchRight(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
if (right < 0 || nums[right] != target) {
return -1;
}
return right;
}
public static int[] searchRange(int[] nums, int target) {
int[] res = new int[2];
res[0] = searchLeft(nums, target);
res[1] = searchRight(nums, target);
return res;
}
35. Search insertion location
Given a sorted array and a target value, find the target value in the array and return its index. If the target value does not exist in the array, return the position where it will be inserted sequentially.
You must use an algorithm with O(log n) time complexity.
Example 1:
Input: nums = [1,3,5,6], target = 5 Output: 2
Example 2:
Input: nums = [1,3,5,6], target = 2 Output: 1
Example 3:
Input: nums = [1,3,5,6], target = 7 Output: 4
Example 4:
Input: nums = [1,3,5,6], target = 0 Output: Example 5:
Input: nums = [1], target = 0 Output: 0
public static int searchInsert(int[] nums, int target) {
if (target < nums[0]) {
return 0;
}
if (target > nums[nums.length - 1]) {
return nums.length;
}
int left = 0;
int right = nums.length - 1;
while (left < right) { // Note that this cannot be equal to
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid; // Notice the gap (just simulate it for example)
}
}
return left;
}
[Offer 11.Minimum number of rotated arrays] (#Offer 11.Minimum number of rotated arrays)
Moves the first elements of an array to the end of the array, which we call the rotation of the array. Enter a rotation of an incrementally ordered array and output the smallest element of the rotation array. For example, the array [3,4,5,1,2] is a rotation of [1,2,3,4,5], and the minimum value of the array is 1.
Example 1:
Input: [3,4,5,1,2]
Output: 1
Example 2:
Input: [2,2,2,0,1]
Output: 0
/**
* Method 1: Traverse directly
*/
public static int minArray(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1]) {
return nums[i + 1];
}
}
return nums[0];
}
/**
* Method 2: Dichotomy
* Ideas using binary search:
* mid = left + (right - left) / 2
* There are three cases to consider:
* (1)array[mid] > array[right]:
* This happens in array s like [3,4,5,6,0,1,2], where the minimum number must be on the right side of mid.
* left = mid + 1
* (2)array[mid] == array[right]:
* When this happens, array s are like [1,0,1,1,1] or [1,1,1,0,1], at which point the minimum number is not good to determine whether it's on the left or right side of the mid, so there's only one try, right--, because it's in ascending order
* right = right - 1
* (3)array[mid] < array[right]:
* This happens in arrays like [2,2,3,4,5,6,6], where the minimum number must be array[mid] or to the left of mid. Because the right side must be increasing.
* right = mid
* Note that there is a hole here: if there are only two numbers left in the range to be queried, then mid must point to the number at the top of the subscript
* For example, array = [4,6]
* array[left] = 4; array[mid] = 4; array[right] = 6;
* If right = mid-1, an error occurs, so right = mid
* But in case (1), left = mid + 1 is not an error
*/
public static int minArrayII(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
if (mid + 1 < right && nums[mid] > nums[mid + 1]) {
return nums[mid + 1];
}
left = mid + 1;
} else if (nums[mid] < nums[right]) {
right = mid;
} else {
right = right - 1;
}
}
return nums[left];
}
153. Find the minimum value in a rotated sort array
An array with a known length of n is pre-sorted in ascending order and rotated 1 to N times to obtain an input array. For example, the original array nums = [0,1,2,4,5,6,7] may be changed to obtain [4,5,6,7,0,1,2] if rotated four times, then [0,1,2,4,6,7] if rotated seven times, then [0,2,5,6,7] Note that the result of one rotation of the array [a[0], a[1], a[2],..., a[n-1]] is a n array [a[n-1], a[1], a[2],..., a[n-2].
You are given an array of nums elements with different values, which was originally an ascending array and rotated several times as described above. Please find and return the smallest element in the array.
Example 1:
Input: nums = [3,4,5,1,2] Output: 1 Interpretation: The original array is [1,2,3,4,5], rotate three times to get the input array.
Example 2:
Input: nums = [4,5,6,7,0,1,2] Output: 0 Interpretation: The original array is [0,1,2,4,5,6,7], rotate 4 times to get the input array.
Example 3:
Input: nums = [11,13,15,17] Output: 11 Interpretation: The original array is [11,13,15,17], rotate four times to get the input array.
/** It's actually Offer11: The smallest number of rotating arrays**/
/**
* Method 2: Dichotomy
* Swordfinger Offer11: Search for the minimum value of a rotated array
*/
public static int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
if (mid + 1 < right && nums[mid] > nums[mid + 1]) { // Examples: 3, 4, 5, 1, 2
return nums[mid + 1];
}
left = mid + 1;
} else if (nums[mid] < nums[right]) {
right = mid;
} else {
right = right - 1;
}
}
return nums[left];
}
/**
* Method 1: Traverse directly
*/
public static int findMin(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1]) {
return nums[i + 1];
}
}
return nums[0];
}
154. Find the minimum value II in a rotated sort array
An array with a known length of n is pre-sorted in ascending order and rotated 1 to N times to obtain an input array. For example, the original array nums = [0,1,4,4,5,6,7] may be changed to get [4,5,6,7,0,1,4] if rotated four times, then [0,1,4,5,6,7] if rotated seven times, you can get [0,1,4,6,7]. Note that the result of one rotation of the array [a[0], a[1], a[2],..., a[n-1]] is a n array [a[n-1], a[1], a[2],..., a[n-2].
Give you an array nums that may have duplicate element values, which was originally an ascending array and rotated several times as described above. Please find and return the smallest element in the array.
Example 1:
Input: nums = [1,3,5] Output: 1
Example 2:
Input: nums = [2,2,2,0,1] Output:0
/** It's actually Offer11: the smallest number of rotating arrays (the same as the above solution)**/
/**
* Method 2: Dichotomy
* Swordfinger Offer11: Search for the minimum value of a rotated array
*/
public static int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
if (mid + 1 < right && nums[mid] > nums[mid + 1]) { // Examples: 3, 4, 5, 1, 2
return nums[mid + 1];
}
left = mid + 1;
} else if (nums[mid] < nums[right]) {
right = mid;
} else {
right = right - 1;
}
}
return nums[left];
}
/**
* Method 1: Traverse directly
*/
public static int findMin(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1]) {
return nums[i + 1];
}
}
return nums[0];
}
162. Find Peaks
Peak elements are those whose values are strictly greater than their left and right neighbors.
Give you an array of integers, nums, find the peak element and return its index. The array may contain multiple peaks, in which case it is sufficient to return to any peak location.
You can assume that nums[-1] = nums[n] = -u.
You must implement an algorithm with O(log n) time complexity to solve this problem.
Example 1:
Input: nums = [1,2,3,1] Output: 2 Interpretation: 3 is the peak element and your function should return its index 2.
Example 2:
Input: nums = [1,2,1,3,5,6,4] Output: 1 or 5 Explanation: Your function can return index 1 with a peak element of 2; Or return index 5 with a peak element of 6.
/**
* Method 2: Dichotomy
* First of all, we should pay attention to the condition of the title. nums[-1] = nums[n] = -u appears in the title description.
* This means that as long as one element in the array is larger than its neighbors, a peak can be found along it
* Based on this conclusion, we can use the binary search to find the peak value
* When searching, the left pointer l and the right pointer r, which keep the left and right order, are cyclic conditions
* Calculate the middle position m based on the left and right pointers and compare m with m+1.
* If m is large, there is a peak on the left, r = m,
* If m + 1 is large, there is a peak on the right, l = m + 1
* Reference resources: https://leetcode-cn.com/problems/find-peak-element/solution/hua-jie-suan-fa-162-xun-zhao-feng-zhi-by-guanpengc/
*/
public static int findPeakElementII(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
right = mid; // Notice the difference here
} else {
left = mid + 1;
}
}
return left;
}
/**
* Method 1: Traverse directly
*/
public static int findPeakElement(int[] nums) {
int len = nums.length;
if (len == 1) {
return 0;
}
if (len == 2) {
return nums[0] > nums[1] ? 0 : 1;
}
for (int i = 1; i < len - 1; i++) {
if (nums[i - 1] < nums[i] && nums[i] > nums[i + 1]) {
return i;
}
}
return nums[0] > nums[len - 1] ? 0 : len - 1;
}
215. The K largest element in the array
Given the integer array nums and integer k, return the kth largest element in the array.
Notice that you are looking for the kth largest element after the array is sorted, not the kth different element.
Example 1:
Inputs: [3,2,1,5,6,4] and k = 2 Outputs: 5
Example 2:
Inputs: [3,2,3,1,2,4,5,5,6] and k = 4 Outputs: 4
/**
* Partition in Quick Sort, Descending Sort
*/
int Partition(vector<int> &a, int l, int r) {
int i = l, j = r, key;
if (l < r) {
key = a[l];
while (i < j) {
while (i < j && a[j] < key) j--;
if (i < j)
a[i++] = a[j];
while (i < j && a[i] > key) i++;
if (i < j)
a[j--] = a[i];
}
a[i] = key;
}
return i;
}
/**
* Find the k th largest element
*/
int findKthLargest(vector<int>& nums, int k) {
int len = nums.size();
if (len <= 0) return 0;
int l = 0, r = len - 1, target = -1;
int pos = Partition(nums, l, r);
while (pos != k-1) {
if (pos > k-1) {
r = pos - 1;
pos = Partition(nums, l, r);
} else {
l = pos + 1;
pos = Partition(nums, l, r);
}
}
target = nums[pos];
return target;
}
475. Heater
Winter has come. Your task is to design a heater with a fixed heating radius to heat all the houses.
Each house can be heated within the heater's heating radius.
Now, given the location of the houses and heaters on a horizontal line, find out and return the minimum heating radius that can cover all the houses.
Description: All heaters follow your radius standard and the same radius is used for heating.
Example 1:
input: houses = [1,2,3], heaters = [2] output: 1 explain: There is only one heater on position 2. If we set the heating radius to 1, all houses will be heated.
Example 2:
input: houses = [1,2,3,4], heaters = [1,4] output: 1 explain: At position 1, 4 There are two heaters on it. We need to set the heating radius to 1 so that all the houses can be heated.
Example 3:
Input: houses = [1,5], heaters = [2] Output: 3
/**
* Method 1: (Violence: Direct traversal) Timeout!
* The location of each heater to each room is required, and each heater corresponds to a row to construct a two-dimensional array.
* Then the minimum value of each column is calculated to get a one-dimensional array.
* Then the maximum value of this one-dimensional array is calculated, which is the radius size.
* <p>
* | 1 2 3 4 (house)
* ---------------------
* 1 | 0 1 2 3
* 4 | 3 2 1 0
* 3 | 2 1 0 1
* ---------------------
* 0 1 0 0
* <p>
* Convert it to: First find the distance from the ith house to all the heaters, keeping the minimum res[i]
* Then the maximum of all the minimum values is calculated.
*/
public static int findRadius(int[] houses, int[] heaters) {
int curDis = 0;
int[] res = new int[houses.length];
Arrays.fill(res, Integer.MAX_VALUE);
for (int i = 0; i < houses.length; i++) {
for (int j = 0; j < heaters.length; j++) {
curDis = Math.abs(houses[i] - heaters[j]);
res[i] = Math.min(res[i], curDis);
}
}
Arrays.sort(res);
return res[res.length - 1];
}
/**
* Method 2: Dichotomy
* 1,Find the shortest distance from each house to the heater (that is, find the closest heater to the house).
* 2,Selecting the largest max(res) of all distances is the result.
*/
public static int findRadiusII(int[] houses, int[] heaters) {
// Sort first
Arrays.sort(houses);
Arrays.sort(heaters);
int[] res = new int[houses.length];
// Find the shortest distance from each house to the heater (that is, find the closest heater to the house)
for (int i = 0; i < houses.length; i++) {
int house = houses[i];
// Binary lookup: Find the first subscript greater than or equal to house from heaters
int left = 0;
int right = heaters.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (heaters[mid] < house) {
left = mid + 1;
} else {
right = mid;
}
}
// Heater equals house, distance 0
if (heaters[left] == house) {
res[i] = 0;
} else if (heaters[left] < house) { // Heater coordinates are less than house, indicating that there is no other heater between the coordinates of the heater and the house
res[i] = house - heaters[left];
} else if (left == 0) { // If left == 0, the result of the binary search points to the coordinate of the first heater, indicating the location before the house with heaters[left] coordinates
// Without a heater, subtract directly from the nearest heater in the house
res[i] = heaters[left] - house;
} else { // If the left ft is not equal to 0, the house is between the left and the left-1, and the shortest distance from the house to the heater is the left and the left-1
// Minimum difference between heater and house
res[i] = Math.min(heaters[left] - house, house - heaters[left - 1]);
}
}
Arrays.sort(res);
return res[res.length - 1];
}
3. Quick partition thought
Offer 39.Numbers in arrays that occur more than half the time
There is a number in the array that occurs more than half the length of the array. Find the number.
You can assume that the array is not empty and that there is always a majority of elements in the given array.
Example 1:
Input: [1, 2, 3, 2, 2, 2, 5, 4, 2]
Output: 2
/**
* Method 1: Use map to count the number of occurrences of each character
*/
public static int majorityElement(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
if (map.get(num) > nums.length / 2) {
return num;
}
}
return 0;
}
/**
* Method 2: Sort first, if it exists, the number in the middle must be more than half of the number
*/
public static int majorityElementII(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
/**
* Method 3: Based on the idea of partition in fast ranking, look for the number k = n/2 in the disordered array
* The partition first divides the array into two parts to get the dividing point subscript pos, and then divides it into three cases:
* (1)pos == k-1 Then find the k th largest value, arr[pos]
* (2)pos > k-1 Then the array with the largest k value on the left
* (3)pos < k-1 Then the k th largest value and the right part of the array
*/
public static int majorityElementIII(int[] nums) {
int len = nums.length;
if (len <= 0) {
return 0;
}
int left = 0;
int right = len - 1;
int k = len / 2;
int pos = partition(nums, left, right);
while (k != pos) {
if (pos > k) {
right = pos - 1;
pos = partition(nums, left, right);
} else {
left = pos + 1;
pos = partition(nums, left, right);
}
}
int target = nums[pos];
return checkMoreThanHalf(nums, target);
}
/**
* partition Thought: Examination often!
*/
private static int partition(int[] nums, int left, int right) {
int i = left;
int j = right;
int key;
if (left < right) {
key = nums[left];
while (i < j) {
while (i < j && nums[j] > key) {
j--;
}
if (i < j) {
nums[i++] = nums[j];
}
while (i < j && nums[i] < key) {
i++;
}
if (i < j) {
nums[j--] = nums[i];
}
}
nums[i] = key;
}
return i;
}
private static int checkMoreThanHalf(int[] nums, int target) {
int times = 0;
int threshold = nums.length / 2;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
times++;
}
if (times > threshold) {
return target;
}
}
return -1;
}
4. Stack and Queue
-Data structure
Stack and Queue, mainly using Deque interface, LinkedList implementation class.
4.1 Stack Common Methods
| Stack Method | Deque Method | Explain |
|---|---|---|
| push(e) | addFirst(e) | Insert element to top of stack, fail throw exception |
| nothing | offerFirst(e) | Inserts an element to the top of the stack, and returns false if it fails |
| pop() | removeFirst() | Get and delete top stack element, fail throw exception |
| nothing | poolFirst() | Get and delete top stack element, failure returns null |
| peek() | getFirst() | Get but don't delete top stack elements, fail throws an exception |
| nothing | peekFirst() | Gets but does not delete the top stack element, and returns null if failed |
4.2 Queue Common Methods
Supplement PriorityQueue
Offer 09. Queue implementation with two stacks
Title Description
Implement a queue with two stacks. The queue is declared as follows. Implement its two functions appendTail and deleteHead to insert integers at the end of the queue and delete integers at the head of the queue, respectively. (deleteHead returns -1 if there are no elements in the queue)
Example 1:
Input:
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
Output: [null,null,3,-1]
Example 2:
Input:
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
Output: [null,-1,null,null,5,2]
Deque<Integer> stackIn; // stackIn for stacking
Deque<Integer> stackOut; // stackOut for stacking
public Offer_09_CQueue() {
stackIn = new LinkedList<>();
stackOut = new LinkedList<>();
}
public void appendTail(int value) {
stackIn.push(value); // stackIn for stacking
}
public int deleteHead() {
if (stackOut.isEmpty()) { // StackOut empty, stackIn not empty, stackIn out of stack into stackOut
while (!stackIn.isEmpty()) {
stackOut.push(stackIn.poll());
}
}
if (!stackOut.isEmpty()) { // Stack out when stackOut is not empty
return stackOut.poll();
} else {
return -1;
}
}
Offer 30.Stack containing min function
Define the data structure of the stack, in which you implement a min function that gets the smallest element of the stack, where the time complexity of calling min, push, and pop is O(1).
Use two stacks, one for pushing data and one for keeping the minimum element stack.
Each stack operation, if the stack element is smaller than the current minimum element, it is pushed into the minimum element stack, and the original minimum element becomes the minor element. Similarly, when a stack is equated with the top element of the minimum element stack, the top of the minimum element stack is ejected.
[External chain picture transfer failed, source station may have anti-theft chain mechanism, it is recommended to save the picture and upload it directly (img-yozecu2N-169518763) (E:\1studyuniversityspecialtyblogimagecodeoffer-30.png)]
Deque<Integer> stackData;
Deque<Integer> stackMin;
/** initialize your data structure here. */
public Offer_30_MinStack() {
stackData = new LinkedList<>();
stackMin = new LinkedList<>();
}
public void push(int x) {
stackData.push(x); // Data Stack Pushes Input Data
if (stackMin.isEmpty()) {
stackMin.push(x);
} else {
if (stackMin.peek() > x) { // Auxiliary stack pushes in the smallest element at this time
stackMin.push(x);
} else {
stackMin.push(stackMin.peek()); // Auxiliary stack pushes in the smallest element at this time
}
}
}
public void pop() {
stackData.pop();
stackMin.pop();
}
public int top() {
return stackData.peek();
}
public int min() {
return stackMin.peek();
}
Offer 31.Stack Push-in and Eject Sequences
Enter two integer sequences, the first representing the stack's entry order, and determine if the second sequence is likely to be
The pop-up order of the stack. Assume that all the numbers pushed into the stack are not equal. For example, sequence 1,2,3,4,5 is the compression order of a stack.
Sequence 4,5,3,2,1 is a pop-up sequence corresponding to the stack sequence, but 4,3,5,1,2 cannot be the stack sequence
Pop-up sequence. (Note that the two sequences are of equal length)
[External chain picture transfer failed, source station may have anti-theft chain mechanism, it is recommended to save the picture and upload it directly (img-LWms5uXq-163518765) (E:\1studyuniversityspecialtyblogimagecodeoffer-31.png)]
public static boolean validateStackSequences(int[] pushed, int[] popped) {
if (pushed.length <= 0) {
return true;
}
Deque<Integer> stackPush = new LinkedList<>(); // Auxiliary stack to hold pressed elements
int j = 0; // Element subscript currently popped up on pop-up stack
for (int i = 0; i < pushed.length; i++) {
stackPush.push(pushed[i]); // Push element into auxiliary stack
while (!stackPush.isEmpty() && stackPush.peek() == popped[j]) { // Only if the top element of the auxiliary stack and the current pop-up stack need to be equal, then pop-up the top element of the auxiliary stack
stackPush.pop();
j++;
}
}
return stackPush.isEmpty(); // If the auxiliary stack is not empty, the pop-up order is legal
}
735. Planetary collisions
Given an array of integers, asteroids, represents planets in the same row.
For each element in the array, its absolute value represents the size of the planet, and its positive and negative values indicate the direction in which the planet is moving (positive indicates right movement, negative indicates left movement). Each planet moves at the same speed.
Find all the planets left after the collision. Collision rule: Two planets collide with each other, and smaller planets explode. If two planets are the same size, both will explode. Two planets moving in the same direction will never collide.
Example 1:
Input: asteroids = [5,10,-5]
Output: [5,10]
Interpretation: There are only 10 left after 10 and -5 collisions. 5 and 10 never collide.
Example 2:
Input: asteroids = [8,-8]
Output: []
Interpretation: Both explosions occur after collisions between 8 and -8.
Example 3:
Input: asteroids = [10,2,-5]
Output: [10]
Interpretation: After a collision between 2 and 5, -5 remains. There are 10 left after the collision between 10 and 5.
Example 4:
Input: asteroids = [-2,-1,1,2]
Output: [-2, -1,1,2]
Interpretation: -2 and-1 move to the left, while 1 and 2 move to the right. Because planets moving in the same direction do not collide, no planets eventually collide.
/**
* Method 1: Use stack (be sure to note cyclomatic complexity)
*/
public static int[] asteroidCollision(int[] nums) {
Deque<Integer> stack = new LinkedList<>();
stack.push(nums[0]);
for (int i = 1; i < nums.length; i++) {
if (nums[i] >= 0) { // If the current number is positive, push directly into the stack
stack.push(nums[i]);
} else { // Only negative numbers need to be collided
while (!stack.isEmpty() && stack.peek() > 0 && stack.peek() < Math.abs(nums[i])) {
// The stack is not empty and the top element is positive and less than the absolute value of the current negative number
stack.pop();
}
if (!stack.isEmpty() && stack.peek() > 0 && stack.peek() == Math.abs(nums[i])) {
// The stack is not empty, and the top element is positive and equal to the absolute value of the current negative number. You need to end this cycle
stack.pop();
continue;
}
// The stack is empty; Or if the stack is not empty and the top element is negative, the current element needs to be pushed in
if (stack.isEmpty() || (!stack.isEmpty() && stack.peek() < 0)) {
stack.push(nums[i]);
}
}
}
// Keep pressing out to save the results. Save in reverse order
int[] res = new int[stack.size()];
for (int i = stack.size() - 1; i >= 0 ; i--) {
res[i] = stack.peek();
stack.pop();
}
return res;
}
// 5, 10, -15
// 2, 1, -1, -2
// 5, 10, -2, 8, -9, 20, -11
// 5, 10, -2, 8, -9, 20, -11, -21
5. Monotonic Stack
739. Daily temperature
According to the daily temperature list temperatures, calculate that it takes several days a day to have a higher temperature. If the temperature will not rise after that, replace it with 0 at that location.
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Example 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]
/**
* Method 1: Monotonic stack
*/
public static int[] dailyTemperatures(int[] nums) {
int len = nums.length;
if (len == 1) {
return new int[1];
}
Deque<Integer> stack = new LinkedList<>(); // Maintain a monotonic descending stack
int[] res = new int[len];
for (int i = 0; i < nums.length; i++) {
int curVal = nums[i];
// The top element of the pre stack (the front element) is less than the current element (the number after it)
while (!stack.isEmpty() && nums[stack.peek()] < curVal) {
int preIdx = stack.pop(); // Exit Stack, Remove Top Element
res[preIdx] = i - preIdx; // Save current element, temperature rise distance result
}
stack.push(i); // Subscript stacking of current element
}
return res;
}
1475. Final price after commodity discount
Give you an array prices, where prices[i] is the price of the first item in the store.
There is a promotion going on in the store. If you want to buy the first item, you can get the same discount as prices[j], where j is the minimum subscript that meets J > I and prices[j] <= prices[i]. If J does not meet the criteria, you will get no discount.
Please return to an array in which the first element is the price you ultimately need to pay for the item i after a discount.
Example 1:
Input: prices = [8,4,6,2,3]
Output: [4,2,4,2,3]
Explanation:
If the price of commodity 0 is price[0]=8, you will get a discount of price[1]=4, so the final price is 8 - 4 = 4.
The price of item 1 is price[1]=4, and you will get a discount of price[3]=2, so the final price is 4 - 2 = 2.
The price of item 2 is price[2]=6, and you will get a discount of price[3]=2, so the final price is 6 - 2 = 4.
There are no discounts for items 3 or 4.
Example 2:
Input: prices = [1,2,3,4,5]
Output: [1,2,3,4,5]
Interpretation: In this case, there is no discount on all items.
Example 3:
Input: prices = [10,1,1,6]
Output: [9,0,1,6]
/**
* Method 1: Use monotonic stack according to the theme. Find the first element to the right that is smaller than the current element.
*/
public static int[] finalPrices(int[] nums) {
int len = nums.length;
if (len == 1) {
return nums;
}
Deque<Integer> stack = new LinkedList<>();
int[] res = new int[len];
for (int i = 0; i < len; i++) {
res[i] = nums[i];
}
for (int i = 0; i < len; i++) {
int curVal = nums[i];
while (!stack.isEmpty() && nums[stack.peek()] >= curVal) {
int preIdx = stack.pop();
res[preIdx] = nums[preIdx] - curVal;
}
stack.push(i);
}
return res;
}
496. Next larger element I
Give you two arrays of nums1 and nums2 without duplicate elements, where nums1 is a subset of nums2.
Please find the next higher value of each element in nums1 than in nums2.
The next larger element of the number x in nums1 is the first element larger than x to the right of its corresponding position in nums2. If it does not exist, the corresponding location outputs -1.
Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2].
Output: [-1,3, -1]
Explanation:
For number 4 in num 1, you cannot find the next larger number in the second array, so output -1.
For number 1 in num 1, the next larger number to the right of number 1 in the second array is 3.
For number 2 in num 1, there is no next larger number in the second array, so output -1.
Example 2:
Input: nums1 = [2,4], nums2 = [1,2,3,4].
Output: [3, -1]
Explanation:
For number 2 in num1, the next larger number in the second array is 3.
For number 4 in num 1, there is no next larger number in the second array, so output -1.
/**
* Find each bit of the array, followed by the first greater element
*/
public static int[] nextGreaterCore(int[] nums) {
int len = nums.length;
if (len <= 0) {
return null;
}
if (len == 1) {
return new int[]{-1};
}
// 5 4 3 2 1
Deque<Integer> stack = new LinkedList<>();
int[] res = new int[len];
Arrays.fill(res, -1);
for (int i = 0; i < len; i++) {
int curVal = nums[i];
while (!stack.isEmpty() && nums[stack.peek()] < curVal) {
int preIdx = stack.pop();
res[preIdx] = curVal;
}
stack.push(i);
}
return res;
}
/**
* Method one: Monotonic stack, first find the first element in the latter array, each element larger than it. Then you can find each element in the subset num1, the result in nums
*/
public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
List<Integer> nums2List = Arrays.stream(nums2).boxed().collect(Collectors.toList());
int[] res = nextGreaterCore(nums2);
int[] out = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) {
out[i] = res[nums2List.indexOf(nums1[i])];
}
return out;
}
42. Catch rainwater
84. The largest rectangle in a column chart
85. Maximum Rectangle
6. Pointer Method
15.Sum of Three Numbers
Give you a n array of nums containing n integers, and determine if there are three elements a, b, c in nums so that a + b + c = 0? Please find all triples with sum 0 and no repetition.
Note: The answer cannot contain duplicate tuples.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1, -1,2], [-1,0,1]]
Example 2:
Input: nums = []
Output: []
Example 3:
Input: nums = [0]
Output: []
/**
* Method 2: Use three pointers to process (see more and consolidate several times)
* First sort the array, fix a number nums[i] after sorting, then use the left and right pointers to point to the two ends after nums[i],
* Numbers are nums[L] and nums[R], respectively. Calculate the sum of three numbers to determine if they are zero or add them to the result set if they are satisfied
* If nums[i] is greater than 0, the sum of three numbers must not equal 0, ending the cycle
* If nums[i] == nums[i_1], the number is repeated, causing duplicate results, and should be skipped
* When sum == 0, nums[L] == nums[L+1] results in duplicate results and should be skipped, L++.
* When sum == 0, nums[R] == nums[R_1] results in duplicate results and should be skipped, R--
* Time complexity: O(n^2), n is the length of the array
* Reference: https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/
*/
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
int len = nums.length;
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
break; // If the current number is greater than 0, the sum of the three numbers must be greater than 0, and the loop ends
}
if (i > 0 && nums[i] == nums[i - 1]) { // Duplicate removal
continue;
}
int left = i + 1;
int right = len - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
res.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left + 1 < len && nums[left] == nums[left + 1]) { // Duplicate removal
left++;
}
while (right - 1 >= 0 && nums[right] == nums[right - 1]) { // Duplicate removal
right--;
}
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return res;
}
16. Closest Sum of Three
Given an array nums containing n integers and a target value. Find the three integers in nums so that they are closest to the target. Returns the sum of these three numbers. Assume that only one answer exists for each set of inputs.
Example:
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Interpretation: The closest sum to a target is 2 (-1 + 2 + 1 = 2).
/**
* Method 1: Sort first, then narrow down continuously
* Fix a number nums[i] after sorting, then use the left and right pointers to the two ends after nums[i]
* Numbers are nums[L] and nums[R], calculating the sum of the three numbers and the dist between them and the target
* (1)Return sum directly if dis == 0
* (2)If dis > 0, R--makes the sum larger and the dis smaller
* (3)If dis < 0, L--makes sum smaller and dis larger
* If a smaller abs(dis) is found, we update the final min_sum = sum
*/
public static int threeSumClosest(int[] nums, int target) {
int len = nums.length;
int minDis = Integer.MAX_VALUE;
int minSum = 0;
Arrays.sort(nums);
for (int i = 0; i < len; i++) {
int left = i + 1;
int right = len - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
int curDis = target - sum;
if (Math.abs(curDis) < minDis) {
minDis = Math.abs(curDis);
minSum = sum;
}
if (curDis == 0) {
return target;
} else if (curDis > 0) {
left++;
} else {
right--;
}
}
}
return minSum;
}
18.Sum of Quarters
Give you an array of n integers, nums, and a target value. Please find and return the non-repeating quaternion [nums[a], nums[b], nums[c], nums[d], which meets all of the following conditions:
0 <= a, b, c, d < n
a, b, c and d are different from each other
nums[a] + nums[b] + nums[c] + nums[d] == target
You can return the answers in any order.
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2, -1,1,2], [-2,0,0,2], [-1,0,1]]
Example 2:
Input: nums = [2,2,2,2], target = 8
Output: [[2,2,2,2]]
/**
* Method 1: Sort first, then fix two numbers, then use two pointers in the latter part to continuously reduce the pointer range
* Just pay attention to the weightless part.
* Method 2: Use Set regardless of complexity
*/
public static List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < nums.length - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue; // First weight removal
}
for (int j = i + 1; j < nums.length - 2; j++) {
if (j - i > 1 && nums[j] == nums[j - 1]) {
continue; // Second weight removal
}
int left = j + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
while (left + 1 < right && nums[left] == nums[left + 1]) { // Duplicate removal
left++;
}
while (right - 1 > left && nums[right] == nums[right - 1]) { // Duplicate removal
right--;
}
left++;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return res;
}
454.Quaternion Addition II
Given four list of arrays containing integers A, B, C, D, calculate how many tuples (i, j, k, l)
Make A[i] + B[j] + C[k] + D[l] = 0. To simplify the problem, all A, B, C, D
Has the same length N, and 0 < N < 500. All integers range from -228 to 228 - 1.
The final result will not exceed 231 - 1.
75. Color Classification
Given an array of n elements, red, white, and blue, sort them in place so that the elements of the same color are adjacent and in red, white, and blue order.
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]
/**
* Method 1: Direct sorting is sufficient
*/
public static void sortColors(int[] nums) {
Arrays.sort(nums);
}
/**
* Method 2: Use pointer
* p0: 0 The rightmost boundary
* p2: 2 The leftmost boundary
* cur: Elements currently under consideration (as you can see by manually debugging the following example)
* <p>
* p0 p2
* | |
* nums: [1 0 2 1 1 2]
* |
* cur
* <p>
* Move cur pointer along array
* If nums[cur] == 0, it is exchanged with nums[p0]
* If nums[cur] == 2, interchange with nums[p2]
* <p>
* [Specific algorithm]
* Right-most boundary of initialization 0: p0 = 0. Nums[idx < p0] = 0 during the entire algorithm execution.
* The leftmost boundary of initialization 2: p2 = n - 1. Nums[idx > p2] = 2 during the entire algorithm execution.
* Initialize the element sequence number currently considered: curr = 0.
* While curr <= p2 :
* If nums[curr] = 0: swap the curr first and P 0 elements and move the pointer to the right.
* If nums[curr] = 2: Exchange the curr first and p2 elements and move the p2 pointer to the left.
* If nums[curr] = 1: Move the curr pointer to the right.
*/
public static void sortColorsII(int[] nums) {
// P0 points to the rightmost boundary of 0, for all cur < p0: nums[cur] = 0
int cur = 0;
int p0 = 0;
// P2 points to the leftmost boundary of 2, for all cur > p2: nums[cur] = 2
int p2 = nums.length - 1;
while (cur <= p2) {
if (nums[cur] == 0) {
swap(nums, p0, cur);
p0++;
cur++;
} else if (nums[cur] == 2) {
swap(nums, p2, cur);
p2--;
} else {
cur++;
}
}
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
7. Sliding window
3. Longest substring without repeating characters
Given a string s, find out the length of the longest substring that does not contain duplicate characters.
Example 1:
Input: s = "abcabcbb"
Output: 3
Interpretation: Since the longest substring without duplicate characters is "abc", its length is 3.
Example 2:
Input: s = bbbbb
Output: 1
Interpretation: Since the longest substring without duplicate characters is "b", its length is 1.
Example 3:
Input: s = "pwkew"
Output: 3
Interpretation: Since the longest substring without duplicate characters is "wke", its length is 3.
Note that your answer must be the length of the substring, "pwke" is a substring, not a substring.
Example 4:
Input: s = ""
Output: 0
/**
* Method 1: Slide window
*/
public static int lengthOfLongestSubstring(String s) {
Map<Character, Integer> map = new HashMap<>();
char[] str = s.toCharArray();
int len = s.length();
int left = 0;
int right = 0;
int count = 0; // Represents: the number of occurrences more than two times. For example aaa, count=3; For example, aaabb, count=4.
int maxLen = 0;
while (right < len) {
// If the character is included and the number of characters is greater than 0, count++; Because if you move the left ft below, the map value will also be subtracted
if (map.containsKey(str[right]) && map.get(str[right]) > 0) {
count++;
}
map.put(str[right], map.getOrDefault(str[right], 0) + 1);
while (count > 0) {
// If the number of characters removing the left pointer occurs two or more times, you need to count--
if (left <= right && map.get(str[left]) > 1) {
count--;
}
map.put(str[left], map.get(str[left]) - 1); // Update map
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
right++;
}
return maxLen;
}
159. The longest substring that contains at most two different characters
Given a string s, find the longest substring t that contains at most two different characters.
Example 1:
Input:'eceba'
Output: 3
Explanation: t is "ece" with a length of 3.
Example 2:
Input:'ccaabbb'
Output: 5
Interpretation: t is "aabbb" with a length of 5.
/**
* Method 1: Slide window
*/
public static int lengthOfLongestSubstringTwoDistinct(String s) {
Map<Character, Integer> map = new HashMap<>();
char[] str = s.toCharArray();
int len = s.length();
int left = 0;
int right = 0;
int count = 0; // Indicates the number of different key s. For example aaa, count=1; For example, aaabc, count=3.
int maxLen = 0;
while (right < len) {
// If the map does not contain this key; Or contains, but the quantity is 0. count++;
if (!map.containsKey(str[right]) || map.get(str[right]) == 0) {
count++;
}
map.put(str[right], map.getOrDefault(str[right], 0) + 1);
while (count > 2) {
// If the number of characters removed from the left pointer equals one occurrence, count--
if (left <= right && map.get(str[left]) == 1) {
count--;
}
// Update map
map.put(str[left], map.get(str[left]) - 1);
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
right++;
}
return maxLen;
}
340.The longest substring containing up to K different characters
Given a string s, find the longest substring t that contains at most K different characters. Returns its length.
/**
* Method 1: Slide window
*/
public static int lengthOfLongestSubstringKDistinct(String s, int k) {
Map<Character, Integer> map = new HashMap<>();
char[] str = s.toCharArray();
int len = s.length();
int left = 0;
int right = 0;
int count = 0; // Indicates the number of different key s. For example aaa, count=1; For example, aaabc, count=3.
int maxLen = 0;
while (right < len) {
// If the map does not contain this key; Or contains, but the quantity is 0. count++;
if (!map.containsKey(str[right]) || map.get(str[right]) == 0) {
count++;
}
map.put(str[right], map.getOrDefault(str[right], 0) + 1);
while (count > k) { // Number of times greater than k
// If the number of characters removed from the left pointer equals one occurrence, count--
if (left <= right && map.get(str[left]) == 1) {
count--;
}
// Update map
map.put(str[left], map.get(str[left]) - 1);
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
right++;
}
return maxLen;
}
76. Minimum override substring
Give you a string s, a string t. Returns the smallest substring in s that covers all the characters of T. If there is no substring in s that covers all the characters of t, an empty string''is returned.
Be careful:
For duplicate characters in t, the number of characters in the substring we are looking for must be no less than the number of characters in t.
If such a substring exists in s, we guarantee that it is the only answer.
Example 1:
Input: s = ADOBECODEBANC, t = ABC
Output:'BANC'
Example 2:
Input: s = a, t = a
Output:'a'
Example 3:
Input: s = a, t = a a
Output: ""
Explanation: Both characters'a'in t should be included in the substring of s.
So there is no qualified substring and an empty string is returned.
/**
* Method 1: Use sliding window, left and right pointers, apply template (corresponding to python version)
* (1)With a double pointer, initialize left = right = 0, and call the index closed interval [left, right] a window
* (2)Increase the right pointer, expand the window [left, right], and record the number of occurrences of each character in the current window.
* Until the string in the window meets the requirements (contains all the characters in T)
* (3)At this point, we stop increasing right, instead we increase the left pointer and shrink the window [left, right],
* Until the string in the window no longer meets the requirements (does not contain all the characters in T). At the same time, each time we add left, we update our results
* (4)Load steps 2 and 3 until right reaches the end of string S
* [The second step is equivalent to finding a feasible solution, then the third step is to optimize the feasible solution and finally find the optimal solution. Pointer moves forward in turn, window size increases or decreases, window keeps sliding to the right)
* ADOBECODEBANC
* ABC
*/
public static String minWindow(String s, String t) {
int left = 0;
int right = 0;
int count = 0; // Records the number of elements in the current window that contain the specified substring
int minLen = Integer.MAX_VALUE;
String res = "";
int[] map = new int[256];
Arrays.fill(map, 0);
for (int i = 0; i < t.length(); i++) {
map[t.charAt(i)]++;
}
while (right < s.length()) {
if (map[s.charAt(right)] > 0) { // count++ if any substrings are not added
count++;
}
map[s.charAt(right)]--; // Update map
while (count == t.length()) {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
res = s.substring(left, right + 1);
}
// If the substring contains a left pointer element and the number of map s with that key is 0; After removal, the number of count s needs to be updated
if (t.contains(String.valueOf(s.charAt(left))) && map[s.charAt(left)] == 0) {
count--;
}
map[s.charAt(left)]++;
left++;
}
right++;
}
return res;
}
239. Maximum Sliding Window
Give you an array of integers, nums, with a sliding window of size k moving from the leftmost side of the array to the rightmost side of the array. You can only see k numbers in the sliding window. Slide the window one bit to the right at a time.
Returns the maximum value in the sliding window.
Example 1:
Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Maximum position of sliding window
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Example 2:
Input: nums = [1], k = 1
Output: [1]
Example 3:
Input: nums = [1,-1], k = 1
Output: [1, -1]
Example 4:
Input: nums = [9,11], k = 2
Output: [11]
Example 5:
Input: nums = [4,-2], k = 2
Output: [4]
/**
* Method 1: Maintain a monotonic queue
*/
public static int[] maxSlidingWindow(int[] nums, int k) {
// Two-way queue, holds the array position of the maximum value of the current window, guarantees that the values of the array position in the queue are sorted from large to small
Deque<Integer> queue = new LinkedList<>();
int[] res = new int[nums.length - k + 1];
int idx = 0;
for (int i = 0; i < nums.length; i++) {
// Guarantee from large to small, if the first few are small, they need to pop up one by one until they meet the requirements
// Maintains a monotonically decreasing queue that holds subscripts to monotonically decreasing queue elements.
while (!queue.isEmpty() && nums[queue.peek()] < nums[i]) {
queue.pop();
}
// Add an array subscript corresponding to the current value
queue.push(i);
// Determine if the current team leader's value is valid
if (queue.getLast() <= i - k) {
queue.removeLast();
}
// When the window length is k (i traverses to k-1), save the maximum of the current window
if (i + 1 >= k) {
res[i + 1 - k] = nums[queue.getLast()];
}
}
return res;
}
/**
* Method 2: Entire violence. overtime
*/
public static int[] maxSlidingWindowII(int[] nums, int k) {
int[] res = new int[nums.length - k + 1];
int idx = 0;
for (int i = k - 1; i < nums.length; i++) {
res[idx++] = getMaxSlidingWindow(nums, i - k + 1, k);
}
return res;
}
private static int getMaxSlidingWindow(int[] nums, int left, int len) {
int[] win = new int[len];
int idx = 0;
for (int i = left; i < left + len; i++) {
win[idx++] = nums[i];
}
Arrays.sort(win);
return win[len - 1];
}
8. Prefixes and
Five-minute algorithm: prefix and series
[External chain picture transfer failed, source station may have anti-theft chain mechanism, it is recommended to save the picture and upload it directly (img-Cen5l3bk-169518767) (E:\1studyuniversityspecialtyblogimagecodeprefix and.png)]
[External chain picture transfer failed, source station may have anti-theft chain mechanism, it is recommended to save pictures and upload them directly (img-YYd5qaAD-163518770) (E:\1studyuniversityspecialtyblogimagecode\prefix and -1.png)]
[External chain picture transfer failed, source station may have anti-theft chain mechanism, it is recommended to save pictures and upload them directly (img-Vf4Nlq18-163565771) (E:\1studyuniversityspecialtyblogimagecodeprefix and-2.png)]
for (int i = 0; i < nums.length; i++) {
preSum[i + 1] = nums[i] + preSum[i];
}
724. Find the central subscript of the array
Give you an integer array nums, calculate the center subscript of the array.
The array center subscript is a subscript of the array whose sum of all elements on the left is equal to the sum of all elements on the right.
If the central subscript is at the leftmost end of the array, the sum of the left numbers is treated as 0 because there are no elements on the left side of the subscript. This also applies if the central subscript is at the rightmost end of the array.
If the array has more than one central subscript, it should return the closest one to the left. Returns -1 if the array does not have a central subscript.
Example 1:
Input: nums = [1, 7, 3, 6, 5, 6]
Output: 3
Explanation:
The center subscript is 3.
Sum of left numbers = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11,
The sum of the right numbers is equal to nums[4] + nums[5] = 5 + 6 = 11.
Example 2:
Input: nums = [1, 2, 3]
Output: -1
Explanation:
There is no central subscript in the array that meets this condition.
Example 3:
Input: nums = [2, 1, -1]
Output: 0
Explanation:
The center subscript is 0.
Sum of left numbers = 0, (subscript 0 has no elements left),
Sum of right side numbers = nums[1] + nums[2] = 1 + -1 = 0.
/**
* Calculate the sum first, then traverse to determine if the current position is left equal to right
*/
public static int pivotIndex(int[] nums) {
int totalSum = 0;
for (int i = 0; i < nums.length; i++) {
totalSum += nums[i];
}
int curSum = 0;
for (int i = 0; i < nums.length; i++) {
curSum += nums[i];
if (curSum - nums[i] == (totalSum - curSum)) { // Left = Right
return i;
}
}
return -1;
}
1. Sum of Two Numbers
Given an array of integers nums and an integer scalar target, find the two integers in the array that are added to the target target value target and return their array subscripts.
You can assume that each input corresponds to only one answer. However, the same element in the array cannot be repeated in the answer.
You can return the answers in any order.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Interpretation: Because nums[0] + nums[1] == 9, returns [0, 1].
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
/**
* Method 3: Traverse through the array using HashMap
* It turns out that we can do it all at once. As we iterate and insert elements into the table, we go back and check that the table has
* A target element corresponding to the current element exists. If it exists, we've found the solution and returned it immediately.
*
* @param nums
* @param target
* @return
*/
private static int[] twoSumIII(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
return new int[]{i, map.get(target - nums[i])};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
560.and is a subarray of K
You are given an array of integers nums and an array of integers k. Please count and return the number of consecutive subarrays in the array that sum to k.
Example 1:
Input: nums = [1,1,1], k = 2
Output: 2
Example 2:
Input: nums = [1,2,3], k = 3
Output: 2
/**
* Method 1: Violence traversal. Double cycle
*/
public static int subarraySum(int[] nums, int k) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
int curSum = 0;
for (int j = i; j < nums.length; j++) {
curSum += nums[j];
if (curSum == k) {
count++;
}
}
}
return count;
}
/**
* Method 2: Prefix sum. Prefixes and arrays are created first.
* Time Complexity: O(n^2)
*/
public static int subarraySumII(int[] nums, int k) {
// Prefixes and Arrays
int[] preSum = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
// Note: The prefix and array here are populated starting with preSum[1]. preSum[0] = 0
preSum[i + 1] = preSum[i] + nums[i];
}
// Number of Statistics
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i; j < nums.length; j++) {
// Notice the subscript offset: nums[2] to nums[4] equals preSum[5] - preSum[2]
// The sum in the interval nums[i, j] can be obtained as follows
if (preSum[j + 1] - preSum[i] == k) {
count++;
}
}
}
return count;
}
Method 3: Prefix and + HashMap
[External chain picture transfer failed, source station may have anti-theft chain mechanism, it is recommended to save the picture and upload it directly (img-N8AcBhXf-169518773) (E:\1studyuniversityspecialtyblogimagecodeprefix and-3.png)]
[External chain picture transfer failed, source station may have anti-theft chain mechanism, it is recommended to save the picture and upload it directly (img-V0tHv0Gd-163565774) (E:\1studyuniversityspecialtyblogimagecode\prefix and-4.png)]
/**
* Method 3: Prefix and + HashMap
*/
public static int subarraySumIII(int[] nums, int k) {
if (nums.length == 0) {
return 0;
}
// map means, prefix and key, have value s
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1); // The prefix and 0 have an initial value of 1.
int count = 0;
int preSum = 0;
for (int i = 0; i < nums.length; i++) {
preSum += nums[i];
// Determine if there is a prefix and a prefix of preSum - k, and then know if there is a prefix and a prefix of K.
if (map.containsKey(preSum - k)) {
count += map.get(preSum - k); // Number of acquisitions
}
// To update
map.put(preSum, map.getOrDefault(preSum, 0) + 1);
}
return count;
}
1248. K odd subarrays
You are given an array of integers nums and an integer k.
If there happens to be k odd numbers in a continuous subarray, we consider it a "graceful subarray".
Please return the number of "beautiful subarrays" in this array.
Example 1:
Input: nums = [1,1,2,1,1], k = 3
Output: 2
Interpretation: Subarrays containing three odd numbers are [1,1,2,1] and [1,2,1,1].
Example 2:
Input: nums = [2,4,6], k = 1
Output: 0
Interpretation: The array does not contain any odd numbers, so there is no beautiful subarray.
Example 3:
Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
Output: 16
[External chain picture transfer failed, source station may have anti-theft chain mechanism, it is recommended to save the picture and upload it directly (img-oHZYZP7t-163565775) (E:\1studyuniversityspecialtyblogimagecode\prefix and-5.png)]
/**
* Method 1: Prefix and + HashMap
* Simply save the odd number of prefix intervals within the interval, but change sum += x to a statement that determines parity
*
*/
public static int numberOfSubarrays(int[] nums, int k) {
if (nums.length == 0) {
return 0;
}
// map means that if the prefix has an odd number of key s, there are value s
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int count = 0;
int preOdd = 0;
for (int i = 0; i < nums.length; i++) {
preOdd += (nums[i] % 2);
if (map.containsKey(preOdd - k)) {
count += map.get(preOdd - k);
}
// To update
map.put(preOdd, map.getOrDefault(preOdd, 0) + 1);
}
return count;
}
974. Subarrays divisible by K
Given an integer array A, returns the number of subarrays in which the sum of elements is divisible by K (continuous, non-empty).
Example:
Input: A = [4,5,0,-2,-3,1], K = 5
Output: 7
Explanation:
Seven subarrays satisfy the sum of their elements and are divisible by K = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
[External chain picture transfer failed, source station may have anti-theft chain mechanism, it is recommended to save the picture and upload it directly (img-Ge5kIipG-169518776) (E:\1studyuniversityspecialtyblogimagecodeprefix and-6.png)]
[External chain picture transfer failed, source station may have anti-theft chain mechanism, it is recommended to save the picture and upload it directly (img-whl0u8hM-163518777) (E:\1studyuniversityspecialtyblogimagecodeprefix and-7.png)]
[External chain picture transfer failed, source station may have anti-theft chain mechanism, it is recommended to save pictures and upload them directly (img-u0o7PhQ2-163518778) (E:\1studyuniversityspecialtyblogimagecodeprefix and-8.png)]
[External chain picture transfer failed, source station may have anti-theft chain mechanism, it is recommended to save the picture and upload it directly (img-St8tOf40-169518779) (E:\1studyuniversityspecialtyblogimagecodeprefix and-9.png)]
/**
* Method 3: Prefix and + HashMap
*/
public static int subarraysDivByK(int[] nums, int k) {
// map means, prefix and key, have value s
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int count = 0;
int preSum = 0;
for (int i = 0; i < nums.length; i++) {
preSum += nums[i];
// Calculate the current preSum to k relationship, the remainder is a few.
// When the dividend is negative, the result is negative and is corrected as follows
int key = (preSum % k + k) % k;
if (map.containsKey(key)) {
count += map.get(key);
}
// To update
map.put(key, map.getOrDefault(key, 0) + 1);
}
return count;
}
// Note: This line of code is above int key = (preSum % k + k) % k;
[External chain picture transfer failed, source station may have anti-theft chain mechanism, it is recommended to save the picture and upload it directly (img-8L8sirCx-169518780) (E:\1studyuniversityspecialtyblogimagecodeprefix and-10.png)]
523. Continuous subarrays and
Give you an array of integers nums and an array of integers k, and write a function to determine if the array contains consecutive subarrays that meet the following conditions:
Subarray size is at least 2, and
The sum of subarray elements is a multiple of k.
Returns true if it exists; Otherwise, return false.
If there is an integer n, and the integer x corresponds to x = n * k, then x is a multiple of K. 0 is always considered a multiple of K.
Example 1:
Input: nums = [23,2,4,6,7], k = 6
Output:true
Interpretation: [2,4] is a subarray of size 2 and sum is 6.
Example 2:
Input: nums = [23,2,6,4,7], k = 6
Output:true
Interpretation: [23, 2, 6, 4, 7] is a subarray of size 5 and sum is 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.
Example 3:
Input: nums = [23,2,6,4,7], k = 13
Output: false
[External chain picture transfer failed, source station may have anti-theft chain mechanism, it is recommended to save pictures and upload them directly (img-pbP9yIfV-163518781) (E:\1studyuniversityspecialtyblogimagecodeprefix and-11.png)]
[External chain picture transfer failed, source station may have anti-theft chain mechanism, it is recommended to save pictures and upload them directly (img-E574TtZ0-163518782) (E:\1studyuniversityspecialtyblogimagecodeprefix and-12.png)]
[External chain picture transfer failed, source may have anti-theft chain mechanism, it is recommended to save the picture and upload it directly (img-aUb94QSV-163518783) (E:\1studyuniversityspecialtyblogimagecodeprefix and-13.png)]
- Video Resolution
/**
* Method 1: Prefix and
*/
public static boolean checkSubarraySum(int[] nums, int k) {
// map store: key stores prefix and%k redundancy results, value stores subscripts that are currently traversed to the data.
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1);
int preSum = 0;
int count = 0;
for (int i = 0; i < nums.length; i++) {
preSum += nums[i];
int key = (preSum % k + k) % k;
if (map.containsKey(key)) {
if (i - map.get(key) >= 2) { // The prefix and k redundancy exist, and the subscript difference between them is greater than or equal to 2. If not, iterate through the next time
return true;
} else {
continue;
}
}
// Update the result of Prefix suffix redundancy, <Result of redundancy, Current Subscript>
map.put(key, i);
}
return false;
}
930. and the same binary subarray
Give you a binary array nums, and an integer goal. Please count and return how many non-empty subarrays are sum to go.
A subarray is a continuous part of an array.
Example 1:
Input: nums = [1,0,1,0,1], goal = 2
Output: 4
Explanation:
There are four subarrays that meet the title requirements: [1,0,1], [1,0,1,0], [0,1,0,1], [1,0,1]
Example 2:
Input: nums = [0,0,0,0], goal = 0
Output: 15
/**
* Method 1: Prefix and, like LeetCode 560: as a subarray of K
*/
public static int numSubarraysWithSum(int[] nums, int k) {
// map means, prefix and key, have value s
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1); // The prefix and 0 have an initial value of 1.
int count = 0;
int preSum = 0;
for (int i = 0; i < nums.length; i++) {
preSum += nums[i];
// Determine if there is a prefix and a prefix of preSum - k, and then know if there is a prefix and a prefix of K.
if (map.containsKey(preSum - k)) {
count += map.get(preSum - k); // Number of acquisitions
}
// To update
map.put(preSum, map.getOrDefault(preSum, 0) + 1);
}
return count;
}
9. And Search
concept
-
union - A union in which multiple elements associated with a merge are the same root node
-
find - find Elements, find Root Nodes
basic operation
-
Initialization: init(), int[] parent = new int[size]
-
Merge element: union(int x, int y, int[] parent)
-
Find the root node of an element: find(int x, int[] parent)
Reference link:
- https://segmentfault.com/a/1190000004023326
- https://www.jianshu.com/p/8c74df1db116
Undirected connectivity graph (counting all connectivity graphs)
- Number of connectivity components in 323 undirected graph
- Number of 200 Islands
- Number of 547 Provinces
Minimum spanning tree (including weights, finding the maximum weights containing all nodes)
- 1135 Minimum cost connects all cities
- Path with highest 1102 score
10.Deep Search+Wide Search+Backtracking
11. Trees
12. Chain List
13. Topological Sorting
14. Dynamic Planning
15. Strings
1041. Robots trapped in rings
On an infinite plane, the robot is initially located at (0, 0) and faces north. The robot can accept one of the following three instructions:
"G": go straight 1 unit
"L": turn left 90 degrees
"R": turn right 90 degrees
The robot executes instructions sequentially and repeats them all the time.
Return true only if there are rings in the plane that make it impossible for the robot to leave. Otherwise, return false.
Example 1:
Input:'GGLLGG'
Output:true
Explanation:
The robot moves from (0,0) to (0,2), rotates 180 degrees, and then returns to (0,0).
Repeat these instructions, and the robot will remain centered on the origin and move in a ring with a radius of 2.
Example 2:
Input:'GG'
Output: false
Explanation:
The robot moves infinitely north.
Example 3:
Input:'GL'
Output:true
Explanation:
The robot moves by pressing (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) ->...
Note: GLGLGGLGL
Output: false
/**
* Method 1: Draw a coordinate and simulate it.
* Note: The title means to walk through everything every time before you decide whether to go back to the origin. If you walk back to 0 in the middle, it is not counted.
*/
public static boolean isRobotBounded(String instructions) {
int[][] dir = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
int len = dir.length;
int idx = 0;
int[] curDir = {0, 1};
int[] curPoint = {0, 0};
String line = "";
for (int i = 0; i < 4; i++) { // Ring appears, walk up to 4 times
for (char key : instructions.toCharArray()) {
if (key == 'L') {
idx = (idx + 1 + 4) % 4;
curDir = dir[idx];
} else if (key == 'R') {
idx = (idx - 1 + 4) % 4;
curDir = dir[idx];
} else {
curPoint[0] += curDir[0];
curPoint[1] += curDir[1];
}
}
if (curPoint[0] == 0 && curPoint[1] == 0) {
return true;
}
}
return false;
}
844 Compare strings with backspaces
Given the s and t strings, when they are entered into a blank text editor, you can determine if they are equal. # Represents a backspace character.
Returns true if equal; Otherwise, return false.
**Note: ** If backspace characters are entered for empty text, the text continues to be empty.
Example 1:
Input: s = "ab#c", t = "ad#c" Output: true Explanation: S and T Will become " ac".
Example 2:
Input: s = "ab##", t = "c#d#" Output: true Explanation: s and t Will become "".
Example 3:
Input: s = "a##c", t = "#a#c" Output: true Explanation: s and t Will become " c".
Example 4:
Input: s = "a#c", t = "b" Output: false Explanation: s Will become " c"，but t Still " b".
/**
* Method 1: Traverse backwards and forwards, counting #number, that is, the number of skips that need to be traversed forward
*/
public static boolean backspaceCompare(String s, String t) {
return getRes(s).equals(getRes(t));
}
private static String getRes(String s) {
String sRes = "";
int count = 0;
for (int i = s.length() - 1; i >= 0; i--) {
if (s.charAt(i) == '#') {
count++;
} else {
if (count > 0) {
count--;
} else {
sRes += s.charAt(i);
}
}
}
return sRes;
}
475. Heater
Winter has come. Your task is to design a heater with a fixed heating radius to heat all the houses.
Each house can be heated within the heater's heating radius.
Now, given the location of the houses and heaters on a horizontal line, find out and return the minimum heating radius that can cover all the houses.
Description: All heaters follow your radius standard and the same radius is used for heating.
Example 1:
input: houses = [1,2,3], heaters = [2] output: 1 explain: There is only one heater on position 2. If we set the heating radius to 1, all houses will be heated.
Example 2:
input: houses = [1,2,3,4], heaters = [1,4] output: 1 explain: At position 1, 4 There are two heaters on it. We need to set the heating radius to 1 so that all the houses can be heated.
Example 3:
Input: houses = [1,5], heaters = [2] Output: 3
/**
* Method 1: (Violence: Direct traversal) Timeout!
* The location of each heater to each room is required, and each heater corresponds to a row to construct a two-dimensional array.
* Then the minimum value of each column is calculated to get a one-dimensional array.
* Then the maximum value of this one-dimensional array is calculated, which is the radius size.
* <p>
* | 1 2 3 4 (house)
* ---------------------
* 1 | 0 1 2 3
* 4 | 3 2 1 0
* 3 | 2 1 0 1
* ---------------------
* 0 1 0 0
* <p>
* Convert it to: First find the distance from the ith house to all the heaters, keeping the minimum res[i]
* Then the maximum of all the minimum values is calculated.
*/
public static int findRadius(int[] houses, int[] heaters) {
int curDis = 0;
int[] res = new int[houses.length];
Arrays.fill(res, Integer.MAX_VALUE);
for (int i = 0; i < houses.length; i++) {
for (int j = 0; j < heaters.length; j++) {
curDis = Math.abs(houses[i] - heaters[j]);
res[i] = Math.min(res[i], curDis);
}
}
Arrays.sort(res);
return res[res.length - 1];
}
/**
* Method 2: Dichotomy
* 1,Find the shortest distance from each house to the heater (that is, find the closest heater to the house).
* 2,Selecting the largest max(res) of all distances is the result.
*/
public static int findRadiusII(int[] houses, int[] heaters) {
// Sort first
Arrays.sort(houses);
Arrays.sort(heaters);
int[] res = new int[houses.length];
// Find the shortest distance from each house to the heater (that is, find the closest heater to the house)
for (int i = 0; i < houses.length; i++) {
int house = houses[i];
// Binary lookup: Find the first subscript greater than or equal to house from heaters
int left = 0;
int right = heaters.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (heaters[mid] < house) {
left = mid + 1;
} else {
right = mid;
}
}
// Heater equals house, distance 0
if (heaters[left] == house) {
res[i] = 0;
} else if (heaters[left] < house) { // Heater coordinates are less than house, indicating that there is no other heater between the coordinates of the heater and the house
res[i] = house - heaters[left];
} else if (left == 0) { // If left == 0, the result of the binary search points to the coordinate of the first heater, indicating the location before the house with heaters[left] coordinates
// Without a heater, subtract directly from the nearest heater in the house
res[i] = heaters[left] - house;
} else { // If the left ft is not equal to 0, the house is between the left and the left-1, and the shortest distance from the house to the heater is the left and the left-1
// Minimum difference between heater and house
res[i] = Math.min(heaters[left] - house, house - heaters[left - 1]);
}
}
Arrays.sort(res);
return res[res.length - 1];
}
Sword Finger Offer
03. Duplicate numbers in arrays
Title Description
All numbers in an array of length n are in the range of 0 to n-1. Some numbers in the array are duplicated.
But I don't know how many numbers are duplicated. I don't know how many times each number is repeated. Find any duplicate number in the array.
For example, if you enter an array {2,3,1,0,2,5,3} with a length of 7, the corresponding output is the first duplicate number 2.
Ideas:
(Method 1): Double loops, each time comparing the first with the subsequent one, until a duplicate is found or the traversal is complete. Time Complexity O(n^2)
(Method 2): Use a Set set, traverse once, and join the Set set if the element is not in the Set set; If so, duplicate characters are found and results are returned.
(Method 3): Because it is from 0 to n-1, if not repeated, then each subscript and its number should be equal, if not,
We will swap the current number to the subscript position where it should be. If the two numbers to be exchanged are equal at this time, there are duplicate numbers.
Otherwise, there will be no duplicate numbers for traversing the entire sequence. Just type it once for yourself: [0 1 2 4 3] and [0 1 2 5 3 4]
Requires time complexity O(N), space complexity O(1). Therefore, you cannot use a sort method or an extra tag array. For this array element i n the [0, n-1] range, the element with the value I can be adjusted to the first position to solve. For example (2, 3, 1, 0, 2, 5), when traversing to location 4, the number at that location is 2, but there is already a value of 2 at the second location, so you can know that 2 repeats:
[External chain picture transfer failed, source station may have anti-theft chain mechanism, it is recommended to save the picture and upload it directly (img-5hayz31v-16359518785) (imagecode49d2adc1-b28a-44bf-babb-d443f4a2e3.gif)]
/**
* Method 3: Because it is from 0 to n-1, if not repeated, then each subscript and its number should be equal, if not,
* We will swap the current number to the subscript position where it should be. If the two numbers to be exchanged are equal at this time, there are duplicate numbers.
* Otherwise, there will be no duplicate numbers for traversing the entire sequence. Just type it once for yourself: [0 1 2 4 3] and [0 1 2 5 3 4]
*/
private static int findRepeatNumberIII(int nums[]) {
int len = nums.length;
// Determine if the array is empty
if (len <= 0) return -1;
// Determine if the array is legal (each number is between 0 ~ n-1)
for (int i = 0; i < len; i++) {
if (nums[i] < 0 || nums[i] > len - 1) {
return -1;
}
}
int temp;
for (int i = 0; i < len; i++) {
while (nums[i] != i) {
if (nums[i] == nums[nums[i]]) {
return nums[i];
}
temp = nums[i];
nums[i] = nums[nums[i]];
nums[temp] = temp;
}
}
return -1;
}
/**
* Method 2: Use a Set set, traverse once, and join the Set set if the element is not in the Set set. If so, duplicate characters are found and results are returned.
*/
private static int findRepeatNumberII(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
if (set.contains(num)) {
return num;
} else {
set.add(num);
}
}
return -1;
}
/**
* Method 1: Double loops, each time comparing the first with the following, until a duplicate is found or the traversal is complete. Time Complexity O(n^2)
* (Be careful to judge the validity of the array!)
*/
private static int findRepeatNumber(int nums[]) {
int len = nums.length;
// Determine if the array is empty
if (len <= 0) return -1;
// Determine if the array is legal (each number is between 0 ~ n-1)
for (int i = 0; i < len; i++) {
if (nums[i] < 0 || nums[i] > len - 1) {
return -1;
}
}
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
if (nums[i] == nums[j]) {
return nums[i];
}
}
}
return -1;
}
public static void main(String[] args) {
int[] nums = new int[]{2, 3, 1, 0, 2, 5, 3};
int length = nums.length;
int[] duplication = new int[1];
System.out.println(findRepeatNumberIII(nums));
}
04. Finding in a two-dimensional array
Title Description
In a two-dimensional array (each one has the same length), each row is left to right
Sort in ascending order, with each column sorted in ascending order from top to bottom. Please complete a function,
Enter such a two-dimensional array and an integer to determine if the array contains the integer.
For example:
1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15
Returns true if the number 7 is found
If you look for the number 5, put back false
Reference:
- https://blog.csdn.net/a819825294/article/details/52088732
- https://blog.csdn.net/duan19920101/article/details/50617190
/**
* Method 1: Traverse through a direct double loop
*/
private static boolean findNumberIn2DArray(int[][] matrix, int target) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == target) {
return true;
}
}
}
return false;
}
/**
* Method 2: The matrix is ordered. From the lower left, the number decreases upwards and increases to the right.
* So start at the bottom left when the number you are looking for is larger than the number at the bottom left. Move Right
* Find a number that is hours hotter than the number in the lower left corner, move up
* Time Complexity: O(n^2)
*/
private static boolean findNumberIn2DArrayII(int[][] matrix, int target) {
int rows = matrix.length;
int cols = matrix[0].length;
int i = rows - 1, j = 0;
while (i >= 0 && j < cols) {
if (target == matrix[i][j]) {
return true;
} else if (target > matrix[i][j]) {
j++;
} else {
i--;
}
}
return false;
}
05. Replace spaces
Title Description
Please implement a function that replaces each space in a string with'%20'. For example, when the string is We Are Happy. The replaced string is We%20Are%20Happy.
/**
* Method 1: Use the replace function directly
*/
private static String replaceSpace(String s) {
return s.replace(" ", "%20");
}
/**
* Method 2: for Loop Traversal Replacement
*/
private static String replaceSpaceII(String s) {
String res = "";
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ' ') {
res += "%20";
} else {
res += String.valueOf(s.charAt(i));
}
}
return res;
}
09. Queue with two stacks
Title Description
Implement a queue with two stacks. The queue is declared as follows. Implement its two functions appendTail and deleteHead to insert integers at the end of the queue and delete integers at the head of the queue, respectively. (deleteHead returns -1 if there are no elements in the queue)
Example 1:
Input:
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
Output: [null,null,3,-1]
Example 2:
Input:
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
Output: [null,-1,null,null,5,2]
Deque<Integer> stackIn; // stackIn for stacking
Deque<Integer> stackOut; // stackOut for stacking
public Offer_09_CQueue() {
stackIn = new LinkedList<>();
stackOut = new LinkedList<>();
}
public void appendTail(int value) {
stackIn.push(value); // stackIn for stacking
}
public int deleteHead() {
if (stackOut.isEmpty()) { // StackOut empty, stackIn not empty, stackIn out of stack into stackOut
while (!stackIn.isEmpty()) {
stackOut.push(stackIn.poll());
}
}
if (!stackOut.isEmpty()) { // Stack out when stackOut is not empty
return stackOut.poll();
} else {
return -1;
}
}
10- I. Fibonacci series
Write a function, enter n, and find the nth term (that is, F(N) of the Fibonacci sequence. The Fibonacci sequence is defined as follows:
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), where N > 1.
The Fibonacci series starts with 0 and 1, and the Fibonacci numbers that follow are the sum of the previous two numbers.
The answer needs to be modeled 1e9+7 (1000000007), if the initial result is 1000000008, return 1.
Example 1:
Input: n = 2
Output: 1
Example 2:
Input: n = 5
Output: 5
public static int fib(int num) {
if (num == 0 || num == 1) {
return num;
}
int a = 0;
int b = 1;
int c = 1;
for (int i = 2; i <= num; i++) {
c = (a + b) % 1000000007;
a = b;
b = c;
}
return b;
}
// 0 1 1 2 3 5 8
10-II. Frog Step Jumping
Title Description
A frog can jump up either one or two steps at a time. Find out how many jumps the frog has taken up an n-step (different results in different order)
Ideas:
When n = 1, there is only one jump:
When n = 2, there are two jumps:
If you jump n steps, you can jump 1 step before n-1 steps. Or jump two steps first, then n-2 steps. The skip method of n-1 and n-2 steps can be viewed as a subproblem, the recursive formula of which is:
public static int numWays(int num) {
num++; // Notice here+.
if (num == 0 || num == 1) {
return num;
}
int a = 1;
int b = 1;
int c;
for (int i = 2; i < num; i++) {
c = (a + b) % 1000000007;
a = b;
b = c;
}
return b;
}
// 1 1 2 3 5 8 13 21
10.3-Allergic Step Jump
Title Description
A frog can jump up one step at a time or two steps at a time. It can also jump up n steps. Find out how many jumps the frog can take up an n-step step.
/**
* Method 1: Summarize the formula mathematically
* Mathematical induction shows that f(n) = 2^{n-1}
* It can be calculated directly with a fast power.
*/
public static int jumpFloorII(int num) {
num--;
int ans = 1;
int base = 2;
while (num != 0) {
if (num % 2 == 1) {
ans *= base;
}
base *= base;
num /= 2;
}
return ans;
}
10.4-Rectangular Cover
Title Description
We can use a small 2x1 rectangle to cover a larger rectangle either horizontally or vertically. How many ways can you cover a large 2xn rectangle with n small 2x1 rectangles without overlap?
Ideas:
When n is 1, there is only one override method:
When n is 2, there are two override methods:
To cover a large rectangle of 2*n, you can cover a rectangle of 2*1 first, then a rectangle of 2*(n-1); Or you can cover a 2*2 rectangle first, then a 2*(n-2) rectangle. Rectangles that cover 2*(n-1) and 2*(n-2) can be viewed as subproblems. The recursive formula for this problem is as follows:
#include <cstdio>
/**
* Thought: Still the Fibolacci Sequence Thought
*/
public static int RectCover(int num) {
num++; // Notice here+.
if (num == 0 || num == 1) {
return num;
}
int a = 1;
int b = 1;
int c;
for (int i = 2; i < num; i++) {
c = (a + b) % 1000000007;
a = b;
b = c;
}
return b;
}
// 1 1 2 3 5 8 13 21
11. Minimum number of rotation arrays
Moves the first elements of an array to the end of the array, which we call the rotation of the array. Enter a rotation of an incrementally ordered array and output the smallest element of the rotation array. For example, the array [3,4,5,1,2] is a rotation of [1,2,3,4,5], and the minimum value of the array is 1.
Example 1:
Input: [3,4,5,1,2]
Output: 1
Example 2:
Input: [2,2,2,0,1]
Output: 0
/**
* Method 1: Traverse directly
*/
public static int minArray(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
if (nums[i] > nums[i + 1]) {
return nums[i + 1];
}
}
return nums[0];
}
/**
* Method 2: Dichotomy
* Ideas using binary search:
* mid = left + (right - left) / 2
* There are three cases to consider:
* (1)array[mid] > array[right]:
* This happens in array s like [3,4,5,6,0,1,2], where the minimum number must be on the right side of mid.
* left = mid + 1
* (2)array[mid] == array[right]:
* When this happens, array s are like [1,0,1,1,1] or [1,1,1,0,1], at which point the minimum number is not good to determine whether it's on the left or right side of the mid, so there's only one try, right--, because it's in ascending order
* right = right - 1
* (3)array[mid] < array[right]:
* This happens in arrays like [2,2,3,4,5,6,6], where the minimum number must be array[mid] or to the left of mid. Because the right side must be increasing.
* right = mid
* Note that there is a hole here: if there are only two numbers left in the range to be queried, then mid must point to the number at the top of the subscript
* For example, array = [4,6]
* array[left] = 4; array[mid] = 4; array[right] = 6;
* If right = mid-1, an error occurs, so right = mid
* But in case (1), left = mid + 1 is not an error
*/
public static int minArrayII(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[right]) {
if (mid + 1 < right && nums[mid] > nums[mid + 1]) {
return nums[mid + 1];
}
left = mid + 1;
} else if (nums[mid] < nums[right]) {
right = mid;
} else {
right = right - 1;
}
}
return nums[left];
}
30. Stack containing min function
Define the data structure of the stack, in which you implement a min function that gets the smallest element of the stack, where the time complexity of calling min, push, and pop is O(1).
Use two stacks, one for pushing data and one for keeping the minimum element stack.
Each stack operation, if the stack element is smaller than the current minimum element, it is pushed into the minimum element stack, and the original minimum element becomes the minor element. Similarly, when a stack is equated with the top element of the minimum element stack, the top of the minimum element stack is ejected.
[External chain picture transfer failed, source station may have anti-theft chain mechanism, it is recommended to save the picture and upload it directly (img-RXaYnJBd-163518786) (E:\1studyuniversityspecialtyblogimagecodeoffer-30.png)]
Deque<Integer> stackData;
Deque<Integer> stackMin;
/** initialize your data structure here. */
public Offer_30_MinStack() {
stackData = new LinkedList<>();
stackMin = new LinkedList<>();
}
public void push(int x) {
stackData.push(x); // Data Stack Pushes Input Data
if (stackMin.isEmpty()) {
stackMin.push(x);
} else {
if (stackMin.peek() > x) { // Auxiliary stack pushes in the smallest element at this time
stackMin.push(x);
} else {
stackMin.push(stackMin.peek()); // Auxiliary stack pushes in the smallest element at this time
}
}
}
public void pop() {
stackData.pop();
stackMin.pop();
}
public int top() {
return stackData.peek();
}
public int min() {
return stackMin.peek();
}
31. Stack's push-in and pop-up sequence
Enter two integer sequences, the first representing the stack's entry order, and determine if the second sequence is likely to be
The pop-up order of the stack. Assume that all the numbers pushed into the stack are not equal. For example, sequence 1,2,3,4,5 is the compression order of a stack.
Sequence 4,5,3,2,1 is a pop-up sequence corresponding to the stack sequence, but 4,3,5,1,2 cannot be the stack sequence
Pop-up sequence. (Note that the two sequences are of equal length)
[External chain picture transfer failed, source station may have anti-theft chain mechanism, it is recommended to save the picture and upload it directly (img-4N3eta3B-163518787) (E:\1studyuniversityspecialtyblogimagecodeoffer-31.png)]
public static boolean validateStackSequences(int[] pushed, int[] popped) {
if (pushed.length <= 0) {
return true;
}
Deque<Integer> stackPush = new LinkedList<>(); // Auxiliary stack to hold pressed elements
int j = 0; // Element subscript currently popped up on pop-up stack
for (int i = 0; i < pushed.length; i++) {
stackPush.push(pushed[i]); // Push element into auxiliary stack
while (!stackPush.isEmpty() && stackPush.peek() == popped[j]) { // Only if the top element of the auxiliary stack and the current pop-up stack need to be equal, then pop-up the top element of the auxiliary stack
stackPush.pop();
j++;
}
}
return stackPush.isEmpty(); // If the auxiliary stack is not empty, the pop-up order is legal
}
39. Numbers in arrays that occur more than half the time
There is a number in the array that occurs more than half the length of the array. Find the number.
You can assume that the array is not empty and that there is always a majority of elements in the given array.
Example 1:
Input: [1, 2, 3, 2, 2, 2, 5, 4, 2]
Output: 2
/**
* Method 1: Use map to count the number of occurrences of each character
*/
public static int majorityElement(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
if (map.get(num) > nums.length / 2) {
return num;
}
}
return 0;
}
/**
* Method 2: Sort first, if it exists, the number in the middle must be more than half of the number
*/
public static int majorityElementII(int[] nums) {
Arrays.sort(nums);
return nums[nums.length / 2];
}
/**
* Method 3: Based on the idea of partition in fast ranking, look for the number k = n/2 in the disordered array
* The partition first divides the array into two parts to get the dividing point subscript pos, and then divides it into three cases:
* (1)pos == k-1 Then find the k th largest value, arr[pos]
* (2)pos > k-1 Then the array with the largest k value on the left
* (3)pos < k-1 Then the k th largest value and the right part of the array
*/
public static int majorityElementIII(int[] nums) {
int len = nums.length;
if (len <= 0) {
return 0;
}
int left = 0;
int right = len - 1;
int k = len / 2;
int pos = partition(nums, left, right);
while (k != pos) {
if (pos > k) {
right = pos - 1;
pos = partition(nums, left, right);
} else {
left = pos + 1;
pos = partition(nums, left, right);
}
}
int target = nums[pos];
return checkMoreThanHalf(nums, target);
}
/**
* partition Thought: Examination often!
*/
private static int partition(int[] nums, int left, int right) {
int i = left;
int j = right;
int key;
if (left < right) {
key = nums[left];
while (i < j) {
while (i < j && nums[j] > key) {
j--;
}
if (i < j) {
nums[i++] = nums[j];
}
while (i < j && nums[i] < key) {
i++;
}
if (i < j) {
nums[j--] = nums[i];
}
}
nums[i] = key;
}
return i;
}
private static int checkMoreThanHalf(int[] nums, int target) {
int times = 0;
int threshold = nums.length / 2;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
times++;
}
if (times > threshold) {
return target;
}
}
return -1;
}
40. Minimum k
Enter an array of integers, arr, to find the smallest k of them. For example, if you enter 8 numbers: 4, 5, 1, 6, 2, 7, 3, 8, the smallest 4 numbers are 1, 2, 3, 4.
Example 1:
Input: arr = [3,2,1], k = 2 Output:[1,2] perhaps [2,1]
Example 2:
Input: arr = [0,1,2,1], k = 1 Output:[0]
/**
* Method 1: Sort directly in ascending order and then take the first k digits
*/
public static int[] getLeastNumbers(int[] nums, int k) {
Arrays.sort(nums);
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = nums[i];
}
return res;
}
/**
* Method 2: Large root heap method (large root heap, minimum element on top of heap)
* Take the first k numbers, build a large root heap res, then compare the following numbers with the heap top in turn, and swap them with the heap top if they are smaller than the heap top
* (The specific exchange method is to rebuild the large root heap by first ejecting the heap out of the heap, then adding a decimal number to it)
* Time complexity: O(nlogk)
*/
public static int[] getLeastNumbersII(int[] nums, int k) {
int[] res = new int[k];
if (k == 0) {
return res;
}
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
// Take the first k elements and construct a big root heap
for (int i = 0; i < k; i++) {
queue.offer(nums[i]);
}
// Then compare the subsequent numbers to the top of the heap, and swap them with the top if they are smaller than the top
// (The specific exchange is to first top the heap out of the heap, then add decimals to reconstruct the big root heap)
for (int i = k; i < nums.length; i++) {
if (queue.peek() > nums[i]) {
queue.poll();
queue.offer(nums[i]);
}
}
for (int i = 0; i < k; i++) {
res[i] = queue.poll();
}
return res;
}