day2 | LeetCode977. Square of ordered arrays, 209. Subarray with the smallest length, 59. Spiral matrix II
Created: October 13, 2022 3:29 PM
1. Today's tasks
- 977. Square of ordered arrays
- 209. The subarray with the smallest length
- 59. Spiral Matrix II
Second, the specific implementation
977. Square of ordered arrays
Learning link:
Ideas:
This question may have negative numbers, otherwise it would be meaningless to ask this question. The order of the array given by the title is non-decreasing, so after squaring the data in the array, the largest number can only be on both sides of the array, and the middle cannot be the largest. Then you can use the double pointer method to solve the problem. The pointers on both sides of the array move to the middle in turn, until the array is traversed.
The numbers on the left and right pointers are squared at the same time, whichever side has the largest number after squared, put it at the end of the new array, and the pointer with the largest number moves forward one place until the pointers on both sides move to the same position, End the loop.
class Solution {
public int[] sortedSquares(int[] nums) {
int left = 0;
int right = nums.length - 1;
int [] result = new int[nums.length];
int index = nums.length - 1;
while (left <= right) {
if(nums[left] * nums[left] < nums[right] * nums[right]){
result[index--] = nums[right] * nums[right];
right--;
}else{
result[index--] = nums[left] * nums[left];
left++;
}
}
return result;
}
}
209. The subarray with the smallest length
Learning link:
Ideas:
Because the problem requires to find a continuous sub-array that meets the conditions, then the sliding window method can be used to solve it.
The essence of the sliding window is to continuously move the first and last pointers of the sliding window, and filter out the eligible windows. In fact, it is also the idea of two pointers, but the operation here is more like sliding a window. All called sliding windows.
Because the right pointer here needs to traverse the array, all directly use the length of the array, while the left pointer starts from 0. As long as there are consecutive sub-arrays that meet the conditions, enter the sub-loop, and each time determine whether the length of the sub-array is the smallest, and then subtract the value of the left pointer from the sum, because the left pointer needs to move forward one place.
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int sum = 0;
int result = Integer.MAX_VALUE;
for(int right = 0; right < nums.length; right++){
sum += nums[right];
while(sum >= target) {
result = Math.min(result, right - left + 1);
sum -= nums[left++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
59. Spiral Matrix II
Learning link:
Ideas:
The key to the problem of turning a circle is the loop invariant. All sides of each circle follow a principle, whether it is left open and right closed or left closed and right open.
start is used to record the initial position of each circle, and the circle starts from this initial position, and the offset records the number of circles.
class Solution {
public int[][] generateMatrix(int n) {
int start = 0;
int offset = 1;
int count = 1;
int loop = n / 2;
int[][] nums = new int[n][n];
while (loop-- > 0){
int i = start;
int j = start;
for (j = start; j < n-offset; j++) {
nums[start][j] = count++;
}
for(i = start; i < n-offset; i++){
nums[i][j] = count++;
}
for(; j > start; j--){
nums[i][j] = count++;
}
for(; i > start; i--) {
nums[i][j] = count++;
}
start++;
offset++;
}
if (n % 2 != 0){
nums[n/2][n/2] = count;
}
return nums;
}
}
3. Harvest today
- Today is the second day of learning, and it is considered to have completed several basic problems of arrays. I hope that I can continue to persevere after the difficulty increases.
- Through the first and second questions, I have a new understanding of double pointers. Double pointers can be used in many ways.
- The key to the spiral matrix is the cycle invariant, each edge of each cycle must obey a cycle principle.