Classification brush algorithm, adhere to, progress!
Brush the route reference: github.com/chefyuan/al…
Github.com/youngyangya…
Hello, everyone, I am the third, a brush problem difficult, next we start the array type algorithm brush problem journey!
An array of basic
Arrays are basically the most familiar data structure. You can write “Hello World” soon, and then you can do exercises like “Yang Hui triangle”.
Basic array structure
- An array is a collection of data of the same type stored in contiguously spaced memory Spaces
The figure above shows an example of a character array.
Because the memory space is contiguous, the corresponding element can be obtained directly by subscript.
But deletion is a little bit more complicated, it’s like filling in a hole, where one element is removed, and the hole that’s left, needs to be filled in by other elements.
In Java, the storage of multidimensional arrays is essentially a row-first, one-dimensional array.
Arrays are passed by reference
As we all know, “=” in Java is pass-by-value for basic data types and pass-by-reference for reference data types.
This section can be expanded to write an article, let’s just look at a simple example:
public class ArrayTest {
public static void main(String[] args) {
int[] array = {1.2.3};
int[] newArray = array;
newArray[1] = 0;
// Result: 1 0 3
printArray(array);
// Result: 1 0 3
printArray(newArray);
}
static void printArray(int[] data) {
for (int d : data) {
System.out.print(d + ""); } System.out.println(); }}Copy the codeAs you can see, the array changes as the newArray changes.
Why is that?
In Java, an array is a reference array type. Array and newArray are stack stored references that point to the actual array objects stored in the heap.
So when YOU change newArray, you actually change the array that newArray points to.
And this is something that we need to be aware of, because copying an array requires you to copy it one by one in a loop.
Ok, now, let’s have fun and start brushing!
Binary search
LeetCode704. Binary search
ā Subject: 704. Binary Search (leetcode-cn.com/problems/bi…)
ā Difficulty: Easy
š description:
Given an ordered (ascending) integer array of n elements, nums, and a target value, write a function that searches for the target in NUMs, returning a subindex if the target value exists, or -1 otherwise.
š” ideas:
Binary search is something we’re all familiar with.
Since the array is ordered, we define three Pointers, low, high, and mid, each comparing to the element nums[mid] pointed to by the middle pointer.
-
Equal, hit
-
Larger than nums[mid], the target element is in the interval (mid,high];
-
Smaller than NUMs [mid], the target element is in the [low,mid) range
/** * 704@param nums
* @param target
* @return* /
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (target == nums[mid]) {
return mid;
} else if (target > nums[mid]) {
// Target is in the range of (mid,high]
/ / moves to the right
left = mid + 1;
} else if (target < nums[mid]) {
// Target is in the range of [low,mid]
/ / shift to the left
right = mid - 1; }}return -1;
}
Copy the codeBut there is one problem with this code, and what is it?
int mid = (left + right) / 2;
Int mid = left + ((right-left) >> 1); int mid = left + ((right-left) >> 1);
After modification, the code is as follows:
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid=left+((right-left)>>1);
if (target == nums[mid]) {
return mid;
} else if (target > nums[mid]) {
// Target is in the range of (mid,high]
/ / moves to the right
left = mid + 1;
} else if (target < nums[mid]) {
// Target is in the range of [low,mid]
/ / shift to the left
right = mid - 1; }}return -1;
}
Copy the codeā° Time complexity: O(logn)
LeetCode35. Search for insertion location
ā Title: 35. Search insertion location (leetcode-cn.com/problems/se…)
ā Difficulty: Easy
š description:
Given a sort 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 order in which it will be inserted.
You must use order log n algorithms.
š” ideas:
Binary search is easy, but it takes a little bit of work to get it right, so let’s do another problem that’s basically the same.
This question is basically the same, there are four possible positions for insertion:
- Target
- Target >nums[length-1] : Inserts the right end
- Target =nums[I] : insert at the same position as the element in the array
- Nums [I]
The code is as follows:
/** * 35. Search for insert position **@param nums
* @param target
* @return* /
public int searchInsert(int[] nums, int target) {
int left = 0, right = nums.length - 1;
// Target is less than or greater than the right-most element
if (target < nums[left]) {
return 0;
}
if (target > nums[right]) {
return right + 1;
}
while (left <= right) {
int mid=left+((right-left)>>1);
if (target == nums[mid]) {
// Is equal to the array element
return mid;
} else if (target > nums[mid]) {
/ / on the right side
left = mid + 1;
} else if ((target < nums[mid])) {
/ / on the left side of the
right = mid - 1; }}// Insert after an element
// Return left or right because the exit condition is left==right
return left;
}
Copy the codeā° Time complexity: O(logn)
LeetCode34. Finds the first and last position of an element in the sorted array
ā Title: 34. Find the first and last position of an element in a sorted array (leetcode-cn.com/problems/fi…)
ā Difficulty: medium
š description:
Given an array of ascending integers, nums, and a target value. Find the start and end positions in the array for the given target value.
Return [-1, -1] if there is no target value in the array.
Advanced:
- Can you design and implement order log n algorithms to solve this problem?
š” ideas:
Log n time, ordered array, we know that binary search is coming in.
But this one is a little different, because it has to find the boundary.
So what do we do?
This introduces binary search to find boundaries.
So what’s the idea here?
We use binary search to find the left and right boundaries, respectively.
General binary search:
if (nums[mid] == target) {
return mid;
}else if (nums[mid] < target) {
left = mid + 1;
}else if (nums[mid] > target) {
right = mid - 1;
}
Copy the codeNote that our return condition here is nums[mid] == target, but this is not the case when looking for boundaries, because we cannot be sure that mid is our boundary.
For example, if target <= nums[mid], we then move to the left.
Similarly for the right edge.
The code is as follows:
public int[] searchRange(int[] nums, int target) {
/ / the left border
int leftBound = leftBound(nums, target);
/ / right border
int rightBound = rightBound(nums, target);
// No situation exists
if (rightBound < leftBound) {
return new int[] {-1, -1};
}
return new int[]{leftBound, rightBound};
}
/ * * *@return int
* @Description: Find the left boundary */
int leftBound(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
// Move to the left
if (target <= nums[mid]) {
right = mid - 1;
} else if (target > nums[mid]) {
// Move to the right
left = mid + 1; }}return left;
}
/ * * *@return int
* @Description: Find the right boundary */
int rightBound(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + ((right - left) >> 1);
// Move to the right
if (target >= nums[mid]) {
left = mid + 1;
} else if (target < nums[mid]) {
// Move to the left
right = mid - 1; }}return right;
}
Copy the codeā° Time complexity: O(logn)
Double pointer
LeetCode27. Remove element
ā Title: 27. Remove elements (leetcode-cn.com/problems/re…)
ā Difficulty: Easy
š description:
Given an array nums and a value val, you need to remove all elements equal to val in place and return the new length of the removed array.
Instead of using extra array space, you must only use O(1) extra space and modify the input array in place.
The order of the elements can be changed. You don’t have to worry about elements beyond the new length of the array.
Description:
Why is the return value an integer, but the output answer an array?
Note that the input array is passed as a “reference,” which means that changes to the input array in the function are visible to the caller.
You can imagine the internal operation as follows:
// Nums is passed by reference. That is, no copies are made of the arguments
int len = removeElement(nums, val);
// Modifying the input array in the function is visible to the caller.
// Depending on the length your function returns, it prints out all the elements in the array within that length range.
for (int i = 0; i < len; i++) {
print(nums[i]);
}
Copy the codeš” ideas
Violent solution
There’s nothing to say about the violent solution, just like the last problem, find the element you want to delete, and move everything after it one bit forward.
There are two things to note:
-
We need to define the variable length to get the length of the array, because the length of the array we return will change
-
Whenever a value to be deleted is found, I — is required to prevent multiple values to be deleted together, and then the deletion is missed
The code is as follows:
public int removeElement(int[] nums, int val) {
int length = nums.length;
int i = 0;
for (; i < length; i++) {
if (nums[i] == val) {
for (int j = i; j < length - 1; j++) {
nums[j] = nums[j + 1];
}
// Prevent deletion from leaking
i--;
// Subtract one from the length of the arraylength--; }}return length;
}
Copy the codeā° Time complexity: O(nĀ²).
Double pointer method
Double pointer method is a very common method in array and linked list.
How can we solve this problem using the double pointer method?
Define two Pointers, one before and one after. When the target is not found, front and after move together. When the target is found, after stops, front moves next, assigning the value pointed to by front to the value pointed to by after.
In this way, the double pointer does what the double loop does in one loop.
The code is as follows:
public int removeElement(int[] nums, int val) {
// Define the front and back Pointers
int front = 0;
int after = 0;
for (; front < nums.length; front++) {
if (val != nums[front]) {
nums[after] = nums[front];
after++;
}
}
return after;
}
Copy the codeā° Time complexity: O(n).
LeetCode26. Remove duplicates from ordered arrays
ā Title: 27. Remove elements (leetcode-cn.com/problems/re…)
ā Difficulty: Easy
š description:
Given an ordered array nums, remove the repeated elements in place so that each element appears only once and return the new length of the deleted array.
Instead of using extra array space, you must modify the input array in place and do so using O(1) extra space.
Description:
Why is the return value an integer, but the output answer an array?
Note that the input array is passed as a “reference,” which means that changes to the input array in the function are visible to the caller.
You can imagine the internal operation as follows:
// Nums is passed by reference. Int len = removeDuplicates(nums) // Modifying the input array in the function is visible to the caller. // Depending on the length your function returns, it prints out all the elements in the array within that length range. for (int i = 0; i < len; i++) { print(nums[i]); }Copy the code
š” ideas
While the strength of the last problem did not slow down, hurriedly do a basic consolidation of the same.
Go directly to the code:
public int removeDuplicates(int[] nums) {
int front = 1;
int after = 1;
for (; front < nums.length; front++) {
if(nums[front] ! = nums[front -1]) { nums[after] = nums[front]; after++; }}return after;
}
Copy the codeā° Time complexity: O(n).
LeetCode283. Move the zero
ā title: 283. Move zero (leetcode-cn.com/problems/mo…)
ā Difficulty: Easy
š description:
Given an array nums, write a function to move all zeros to the end of the array while preserving the relative order of the non-zero elements.
Example:
Input: [0,1,0,3,12] output: [1,3,12,0,0]Copy the codeDescription:
- You must operate on the original array; you cannot copy additional arrays.
- Minimize the number of operations
š” ideas
Continue along the lines of the last problem.
- Step 1: We can delete the zero element first, how to delete it? That’s how the two Pointers to LeetCode26 are deleted
- Step 2: But we are moving zero to the end, so what do we do? We will remove the hole at the end of the array by moving, and we will fill it with zeros.
The code is as follows:
/ * * *@return void
* @Description: 283. Move zero *@authorThree points *@date2021/7/30 7:44 * /
public void moveZeroes(int[] nums) {
int after = 0;
int front = 0;
// Move the element
for (; front < nums.length; front++) {
if(nums[front] ! =0) { nums[after] = nums[front]; after++; }}// Set the last element to 0
for (; after < nums.length; after++) {
nums[after] = 0; }}Copy the codeā° Time complexity: O(n).
LeetCode977. The square of ordered arrays
ā Title: 977. The square of ordered Arrays (leetcode-cn.com/problems/sq…)
ā Difficulty: Easy
š description:
Given an array of integers, nums, sorted in non-decrement order, return a new array of squares for each number, and ask for non-decrement order as well.
š” ideas
Order of violence
So what’s the most intuitive way to do this?
Find the array of numbers squared, and then sort the new array.
The code is easy to write:
/ * * *@return int[]
* @DescriptionSquares of ordered arrays - violent method *@authorThree points *@date2021/7/30 8:03 * /
public int[] sortedSquares(int[] nums) {
for (int i = 0; i < nums.length; i++) {
nums[i] *= nums[i];
}
// quicksort, time complexity O(nlogn)
Arrays.sort(nums);
return nums;
}
Copy the codeā° Time complexity: traversal time complexity O(n), quickset time complexity O(nlogn), so time complexity O(n+nlogn).
š” ideas
Double pointer method
We wrote a couple of double pointer, this problem can use double pointer implementation?
Let’s see, this array is ordered before we square it, so the largest absolute value of it must be at both ends.
So we can define two Pointers, one to the left and one to the right, compare the size of their squares, put the large square into the result array, and move the pointer.
The code is as follows:
/ * * *@return int[]
* @DescriptionSquare - double pointer method for ordered arrays@authorThree points *@date 2021/7/30 8:29
*/
public int[] sortedSquares(int[] nums) {
int left = 0;
int right = nums.length - 1;
int[] result = new int[nums.length];
int r = nums.length - 1;
while (left <= right) {
int leftRes = nums[left] * nums[left];
int rightRes = nums[right] * nums[right];
/ / on the right
if (leftRes <= rightRes) {
result[r] = rightRes;
right--;
} else {
/ / to the left
result[r] = leftRes;
left++;
}
r--;
}
return result;
}
Copy the codeā° Time complexity: O(n).
The sum of two Numbers
LeetCode1. The sum of two numbers
ā 1. The sum of two numbers (leetcode-cn.com/problems/tw…)
ā Difficulty: Easy
š Description: given an integer array nums and an integer target, find the two integers in the array and return their array indices.
You can assume that there is only one answer for each input. However, the same element in the array must not appear repeatedly in the answer.
You can return the answers in any order.
š” ideas:
Violent solution
So let’s start with the simplest violent solution, which I think you all know about bubble sort, sort of a two-level cycle.
The code is simple to write:
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
result[0] = i;
result[1] = j;
returnresult; }}}return result;
}
Copy the codeā° Time complexity: when you see this double loop, you know the time complexity O(nĀ²).
Hashing AIDS
O(n ^ 2) is a little bit too much, but the point of this problem is the sum of two elements.
We can store elements in a Hash set so that we can iterate through them once, for example, target and 9, current element 2, and just check whether there is element 7 in the set.
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>(16);
int[] result = new int[2];
for (int i = 0; i < nums.length; i++) {
// The target element
int goal = target - nums[i];
if (map.containsKey(goal)) {
result[0] = map.get(goal);
result[1] = i;
return result;
}
// Take the array value as the key and the subscript as the value
map.put(nums[i], i);
}
return result;
}
Copy the codeā° Time complexity: The time complexity of the Hash query and the value is O(1). Therefore, the overall time complexity is O(1).
LeetCode15. The sum of three numbers
ā title: 15. The sum of three numbers (leetcode-cn.com/problems/3s…)
ā Difficulty: Easy
š description:
Given an array of n integers, nums, determine if there are three elements a, b, and c in NUMs such that a + b + c = 0? Find all triples that sum 0 and are not repeated.
Note: Answers may not contain duplicate triples.
š” ideas:
Hash method
So the first thing that comes to mind after we add up these two numbers is the hash method.
Two layers, a, b, and then 0 minus a plus b to determine c.
But there is a problem. The answer must not contain duplicate triples.
So, we have to figure out how to get rid of the Hash elements.
You can add a constraint that the index of the third term is greater than the index of the second term.
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>(16);
if (nums.length < 3) {
return result;
}
/ / sorting
Arrays.sort(nums);
HashMap<Integer, Integer> map = new HashMap<>();
// Store the element to the hash table
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
Integer c;
int target = 0;
for (int a = 0; a < nums.length; a++) {
target = -nums[a];
/ / to heavy
if (a > 0 && nums[a] == nums[a - 1]) {
continue;
}
for (int b = a + 1; b < nums.length; b++) {
/ / to heavy
if (b > a + 1 && nums[b] == nums[b - 1]) {
continue;
}
// Get c from the hash table
if((c = map.get(target - nums[b])) ! =null) {
// C must be greater than B
if (c > b) {
result.add(new ArrayList<>(Arrays.asList(nums[a], nums[b], nums[c])));
} else {
break; }}}}return result;
}
Copy the codeā° Time complexity: double loop, O(nĀ²).
This is done, but, to be honest, it’s hard to write code that doesn’t have problems.
We’ve written so many double Pointers, is it possible to use double Pointers?
Double pointer method
First sort the array, then iterate through the array.
Then take the left and right Pointers after the current node, determine whether the values of the left and right Pointers are equal to 0-nums[I], and then move the left and right respectively.
How do you get rid of it?
If the condition is met, the left pointer is equal to the previous position, and the right pointer is equal to the value of the next position.
The code is as follows:
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>(16);
if (nums.length < 3) {
return result;
}
/ / sorting
Arrays.sort(nums);
/ / traverse
for (int i = 0; i < nums.length-2; i++) {
// If the current element is greater than 0, the sum of the three must be greater than 0
if (nums[i] > 0) {
break;
}
int left = i + 1;
int right = nums.length - 1;
int count = 0 - nums[i];
/ / to heavy
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(new ArrayList<>(Arrays.asList(nums[i], nums[left], nums[right])));
// Deduplicate. Note that the deduplicate logic should be placed after the first triplet is found
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
// Find the result, double pointer move simultaneously
left++;
right--;
} else if (sum < 0) {
// Move the left pointer to the right
left++;
} else if (sum > 0) {
// Move the right pointer to the leftright--; }}}return result;
}
Copy the codeā° Time complexity: O(nĀ²)
Leetcode18.the sum of four numbers
ā title: 18. The sum of four numbers (leetcode-cn.com/problems/4s…)
ā Difficulty: Easy
š description:
Given an array of n integers, nums, and a target, determine if there are four elements a, b, c, and d in NUMS such that a + b + c + d is equal to target. Find all the quads that satisfy the condition and are not duplicate.
Note: Answers may not contain duplicate quads.
š” ideas:
Let’s continue with the idea of the sum of three numbers, and put another layer around the sum of three numbers.
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>(16);
if (nums.length < 4) {
return result;
}
/ / sorting
Arrays.sort(nums);
for (int i = 0; i < nums.length - 3; i++) {
/ / to heavy
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < nums.length - 2; j++) {
/ / to heavy
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
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) {
result.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[left], nums[right])));
/ / to heavy
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
} else if (sum > target) {
right--;
} else if(sum < target) { left++; }}}}return result;
}
Copy the codeā° Time complexity: O(nĀ³)
The sliding window
LeetCode209. Minimum length subarray
ā Title: 209.Minimum length subarray (leetcode-cn.com/problems/mi…)
ā Difficulty: medium
š description:
Given an array of n positive integers and a positive integer target.
Find the contiguic subarray [numsl, numsl+1,…, numSR-1, numsr] with the smallest length in the array that is equal to or equal to target, and return its length. If no subarray exists, return 0.
š” ideas
This problem is a classic sliding window problem [4].
- The start and end Pointers are used to indicate the start and end positions of the sliding window
- Move the end pointer, expanding the window until the subarray reaches the target value
- Move the start pointer and narrow the window until the subarray no longer satisfies >=target
The code is as follows:
public int minSubArrayLen(int target, int[] nums) {
int result = Integer.MAX_VALUE;
// Start and stop Pointers
int start = 0, end = 0;
/ / the sum
int sum = 0;
while (end < nums.length) {
// add sum, end to right
sum += nums[end++];
while (sum >= target && start < end) {
// The sequence length is end-start because end++
result = Math.min(result, end - start);
/ / move the startsum -= nums[start++]; }}return result == Integer.MAX_VALUE ? 0 : result;
}
Copy the codeā° time complexity: O(n), although the loop inside the loop, but starrt and end have been moved n times, so the time complexity is O(n).
LeetCode219. Duplicate element II exists
ā Title: 219. Duplicate element II exists (leetcode-cn.com/problems/co…)
ā Difficulty: Easy
š description:
Given an array of integers and an integer k, determine whether there are two different indexes I and j in the array such that nums [I] = nums [j] and the absolute value of the difference between I and j is at most k.
š” ideas:
So we did a sliding window problem, and we’re going to do another problem that we can also do with sliding Windows.
This is a slightly different sliding window, the previous window was active, this is a fixed sliding window, maintaining a fixed window of length k, if the window contains a target value, return. If the window enters a new element, the header element needs to be removed to maintain the length of the window.
The code is as follows:
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (set.contains(nums[i])) {
return true;
}
set.add(nums[i]);
if(set.size() > k) { set.remove(nums[i - k]); }}return false;
}
Copy the codeā° Time complexity: O(n).
LeetCode1052. An angry bookstore owner
ā Title: 1052. The Angry Bookstore owner (leetcode-cn.com/problems/gr…)
ā Difficulty: medium
š description:
Today, the bookstore owner planned a soft opening for one of his stores. Customers [I] enter the store every minute, and all of them leave at the end of that minute.
At some point, bookstore owners get angry. If the bookstore owner is grumpy at the I ‘th minute, then Grumpy [I] = 1, otherwise grumpy[I] = 0. When the bookstore owner is angry, the minute the customer is dissatisfied, they are satisfied if they are not angry.
The bookshop owner knows a secret technique to suppress his emotions. It can keep him from getting angry for X minutes, but he can only use it once.
Please return to this day after business, the most how many customers can be satisfied.
Example:
Input: customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1,0,1], X = 3 Maximum number of satisfied customers = 1 + 1 + 1 + 1 + 7 + 5 = 16.Copy the codeš” ideas:
This problem is a fixed window problem.
The whole idea is to treat the customers as fixed Windows that don’t get angry, which divide them into three parts, and then maximize the sum of the three parts.
public int maxSatisfied(int[] customers, int[] grumpy, int minutes) {
// Total window values
int winSum = 0;
// Sum of the left interval
int leftSum = 0;
// Sum of right interval
int rightSum = 0;
int len = customers.length;
// The window is at the starting point
for (int i = 0; i < minutes; i++) {
winSum += customers[i];
}
// The value of the right interval when the window is at the starting point
for (int i = minutes; i < len; i++) {
/ / not angry
if (grumpy[i] == 0) { rightSum += customers[i]; }}// Window left and right - Start moving the window
int left = 1;
int right = minutes;
int maxSum = winSum + leftSum + rightSum;
/ / move
while (right < len) {
// Recalculate the value of the left interval
if (grumpy[left - 1] = =0) {
leftSum += customers[left - 1];
}
// Recalculate the value of the right interval
if (grumpy[right] == 0) {
rightSum -= customers[right];
}
/ / window value
winSum = winSum - customers[left - 1] + customers[right];
// Maximum sum
maxSum = Math.max(maxSum, leftSum + winSum + rightSum);
// Move the fixed window
left++;
right++;
}
return maxSum;
}
Copy the codeā° Time complexity: O(n).
š Space complexity: O(1).
In situ permutation
3. Repeated numbers in arrays
ā Topic: Interview Question 3. Repeated numbers in arrays (leetcode-cn.com/problems/sh…)
ā Difficulty: complex
š description:
Find duplicate numbers in the array.
All numbers in an array of length n, nums, are in the range 0 to n-1. Some of the numbers in the array are repeated, but it is not known how many of them 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 3Copy the codeš” ideas:
Hash method
The first thing that comes to mind is finding duplicate numbers, storing elements with a Hash, and then comparing them.
The code implementation is also simple:
public int findRepeatNumber(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (set.contains(nums[i])) {
return nums[i];
}
set.add(nums[i]);
}
return 0;
}
Copy the codeā° Time complexity: O(n).
š Space complexity: O(n)
But today’s main character is not it, but š
In-situ replacement method
We notice a condition where all the numbers are in the range 0 to n minus 1, so to operate on that, we can place the element at the index corresponding to its value.
For example, if num[2]=1, let’s put it at index 1.
The element then traverses and finds that the pit it should be in is already occupied by its twin, and it knows that it’s the redundant one.
The code is as follows:
public int findRepeatNumber(int[] nums) {
if (nums.length == 0) {
return -1;
}
for (int i = 0; i < nums.length; i++) {
while(nums[i] ! = i) {// Check whether the location is occupied
int index = nums[i];
if (nums[index] == nums[i]) {
return nums[i];
}
// Switch positions
inttemp = nums[i]; nums[i] = nums[index]; nums[index] = temp; }}return -1;
}
Copy the codeā° Time complexity: O(n).
š Space complexity: O(1)
LeetCode41. The first positive number missing
ā Title: 41. Missing first positive number (leetcode-cn.com/problems/fi…)
ā Difficulty: complex
š description:
Given an unsorted array of integers, nums, ask you to find the smallest positive integer that is not present in it.
Implement a solution of O(n) time complexity that uses only constant levels of extra space.
š” ideas
Auxiliary array
This problem has a very clever way! [1]
You can introduce a secondary array, starting at 1, and store the elements of the original array at their corresponding locations. If num[0]=1, then this element should be stored in helper array [1].
We then iterate through the auxiliary array, and the first hole we find is the first missing positive number.
The code is as follows:
public int firstMissingPositive(int[] nums) {
if (nums.length == 0) {
return 1;
}
// Auxiliary array
int[] helper = new int[nums.length + 1];
// Store the positive elements of the array into the auxiliary array
for (int n : nums) {
if (n > 0&& n < helper.length) { helper[n] = n; }}// Iterates to find different elements
for (int i = 1; i < helper.length; i++) {
if(helper[i] ! = i) {returni; }}return helper.length;
}
Copy the codeā° Time complexity: O(n).
š Space complexity: O(n).
In-situ replacement method
We solved one problem with the in-situ substitution method above, which reduced the space complexity. Can we do the same here?
We can’t put nums[I] into the array, we can’t put nums[I] into the array, we can move to the left, num[i-1] into the array.
Code implementation is as follows:
public int firstMissingPositive(int[] nums) {
if (nums.length == 0) {
return 1;
}
// Replace in place
for (int i = 0; i < nums.length; i++) {
// Put the positive numbers in the corresponding positions
// We need to consider the pointer movement, greater than 0, less than len+1, not equal to I +1, and prevent infinite loop when two exchanged numbers are equal
while (nums[i] > 0 && nums[i] < nums.length + 1&& nums[i] ! = i +1&& nums[i] ! = nums[nums[i] -1]) {
/ / the subscript
int index = nums[i] - 1;
/ / exchange
inttemp = nums[index]; nums[index] = nums[i]; nums[i] = temp; }}// Iterate over the array after the replacement
for (int j = 0; j < nums.length; j++) {
if(nums[j] ! = j +1) {
return j + 1; }}return nums.length + 1;
}
Copy the codeā° Time complexity: O(n).
š Space complexity: O(1).
Spiral matrix
LeetCode54. Spiral matrix
ā Title: 54. Spiral matrix (leetcode-cn.com/problems/sp…)
ā Difficulty: medium
š description:
Given a matrix with m rows and N columns, return all the elements of the matrix in a clockwise spiral order.
š” ideas
This problem, the train of thought is relatively easy to think, is up right down left four directions clockwise traversal group.
But the devil is in the details.
There are two kinds of traversal, one is completed, up, down, left and right position movement, traversal is left closed right open [conditions].
We use the second one, every time we go through an edge, we move it, and that’s the condition that we close left and close right.
There are some details is it is worth noting that may occur in the process of traverse a top > bottom | | left > right, including a couple border cross each other.
This means that at this point all items are traversed, and if not broken in time, the traversal will be repeated.
The code is as follows:
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> result = new ArrayList<>(16);
/ / boundary
int left = 0, right = matrix[0].length - 1;
int top = 0, bottom = matrix.length - 1;
int size = matrix.length * matrix[0].length;
/ / traverse
while(result.size() ! = size) {// Upper traversal
for (int i = left; i <= right; i++) {
result.add(matrix[top][i]);
}
top++;
if (top > bottom) break;
// Right layer traversal
for (int i = top; i <= bottom; i++) {
result.add(matrix[i][right]);
}
right--;
if (left > right) break;
// Lower level traversal
for (int i = right; i >= left; i--) {
result.add(matrix[bottom][i]);
}
bottom--;
if (top > bottom) break;
// Left layer traversal
for (int i = bottom; i >= top; i--) {
result.add(matrix[i][left]);
}
left++;
if (left > right) break;
}
return result;
}
Copy the codeš Time complexity: O(mn), where m and n are the number of rows and columns of the input matrix respectively.
LeetCode59. Spiral matrix II
ā Title: 59. Spiral Matrix II (leetcode-cn.com/problems/sp…)
ā Difficulty: medium
š description:
I give you a positive integer n, and I generate an n x N square matrix consisting of all the elements from 1 to N2, with the elements spiraling clockwise.
š” ideas
It’s basically the same problem as the one above, so we just plug it in.
The code is as follows:
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int left = 0, right = n - 1;
int top = 0, bottom = n - 1;
int x = 1;
while (x <= n * n) {
/ /
for (int i = left; i <= right; i++) {
res[top][i] = x;
x++;
}
top++;
if (top > bottom) break;
/ / right
for (int i = top; i <= bottom; i++) {
res[i][right] = x;
x++;
}
right--;
if (left > right) break;
/ /
for (int i = right; i >= left; i--) {
res[bottom][i] = x;
x++;
}
bottom--;
if (left > right) break;
/ / left
for (int i = bottom; i >= top; i--) {
res[i][left] = x;
x++;
}
left++;
if (left > right) break;
}
return res;
}
Copy the codeš Time complexity: O(nĀ²)
Print the matrix clockwise is a similar problem.
conclusion
Wrote a rhyming note to sum it up:
Do simple things repeatedly, repeat things seriously, seriously do things creatively!
I am three points of evil, a full stack of civil and military development.
We’ll see you next time!
Reference:
[1]. Github.com/chefyuan/al…
[2]. Github.com/youngyangya…
[3]. www.zhihu.com/question/31.
[4]. Leetcode-cn.com/problems/sq…
[5]. Leetcode-cn.com/problems/mi…
[6]. Leetcode-cn.com/problems/si…
[7]. Leetcode-cn.com/problems/sp…