977.有序数组的平方[https://leetcode.cn/problems/squares-of-a-sorted-array/]
思路：因为数组是非递减，数组有正有负，找到第一个非负数设为i，i将数组划分为前部分的负数组，后部分的非负数组，使用辅助数组将原数组平方部分存储，后部分使用正序存储，前部分使用逆序存储，然后再使用类似归并排序思路【双指针】，left =0，right =i，将较小者依次存入nums数组。
时间复杂度：O(N+N)
class Solution {
int abs(int x) {
return x * x;
}
public int[] sortedSquares(int[] nums) {
int i = 0;
int[] ans = new int[nums.length];
while (i != nums.length && nums[i] < 0) {
i++;
}
for (int j = 0; j < i; j++) {
ans[j] = abs(nums[i - 1 - j]);
}
for (int j = i; j < nums.length; j++) {
ans[j] = abs(nums[j]);
}
int right = i;
int left = 0;
int k = 0;
while (left < i && right < nums.length) {
if (ans[left] <= ans[right]) {
nums[k] = ans[left];
k++;
left++;
} else {
nums[k] = ans[right];
k++;
right++;
}
}
while (left < i) {
nums[k] = ans[left];
k++;
left++;
}
while (right < nums.length) {
nums[k] = ans[right];
right++;
k++;
}
return nums;
}
}
上部分为本能思路，写法过于啰嗦，整理借鉴后。
简洁思路：负数数组越靠左，平方越大，非负数数组越靠右，平方越大。数组两边左右指针，依次取平方较大者，从高位向低位输入辅助数组。
【创造正序数组时，不仅可以从低位向高位依次存入小值，也可以从高位到低位依次输入大值】
时间复杂度：O(N)
class Solution {
int abs(int x) {return x * x; }
public int[] sortedSquares(int[] nums) {
int i = 0;
int[] ans = new int[nums.length];
int right = nums.length-1;
int left = 0;
int k=right;
while(left<=right){
if(abs(nums[right])>=abs(nums[left])){
ans[k]=abs(nums[right]);
k--;
right--;
}else{
ans[k]=abs(nums[left]);
k--;
left++;
}
}
return ans;
}
}
------------------分割线-------------------
209. 长度最小的子数组https://leetcode.cn/problems/minimum-size-subarray-sum/description/
思路：使用双指针【滑动窗口】，right和left，right-left+1 是最小子数组的长度，sum用于保存当前窗口内和，若sum>target，窗口缩小，若sum<target，窗口扩大。
class Solution {
public int minSubArrayLen(int s, 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 >= s) {
result = Math.min(result, right - left + 1);
sum -= nums[left++];
}
}
return result == Integer.MAX_VALUE ? 0 : result;
}
}
------------------分割线-------------------
59.螺旋矩阵Ⅱhttps://leetcode.cn/problems/spiral-matrix-ii/description/
思路：没什么好说的?
class Solution {
public int[][] generateMatrix(int n) {
int[][] ans = new int[n][n];
int loop = n / 2;
int count = 1;
int i = 0;
while (i < loop) {
for (int j = i; j < n - i - 1; j++) {
ans[i][j] = count++;
}
for (int j = i; j < n - i - 1; j++) {
ans[j][n - i - 1] = count++;
}
for (int j = n - i - 1; j > i; j--) {
ans[n - i - 1][j] = count++;
}
for (int j = n - i - 1; j > i; j--) {
ans[j][i] = count++;
}
i++;
}
if (n % 2 != 0) {
ans[n / 2][n / 2] = count++;
}
return ans;
}
}
使用IDEA，一边输出一边调试，左开右闭！