代码随想录算法训练营第二天

第二天"/>

代码随想录算法训练营第二天

数组相关

977. 有序数组的平方

参考文章
题目连接

思路

1. 暴力法：先将数组进行平方运算，然后排序
2. 使用双指针：因为题目提供的数组为递增数组所以分为无负数（直接进行平方计算求解）和有负数两种，但不管那种平方后最大的必然出现在数组头或者数组尾，所以通过头尾双指针比较大小然后逆序插入新数组的方式进行解题。

个人题解

1 暴力法

class Solution {public int[] sortedSquares(int[] nums) {int l = 0;int r = nums.length-1;for (int i = 0; i < nums.length; i++) {nums[i] = nums[i] * nums[i];}quickSort(nums, 0, r);return nums;}private void quickSort(int[] nums, int strat, int end) {if (strat > end) {return;}int midIndex = pointSwap(nums, strat, end);quickSort(nums, strat, midIndex - 1);quickSort(nums, midIndex + 1, end);}private int pointSwap(int[] nums, int start, int end) {int pivot = nums[start];int leftPoint = start;int rightPoint = end;while (leftPoint < rightPoint) {while (leftPoint < rightPoint&& nums[rightPoint] > pivot) {rightPoint--;}while (leftPoint < rightPoint&& nums[leftPoint] <= pivot) {leftPoint++;}if (leftPoint < rightPoint) {int temp = nums[leftPoint];nums[leftPoint] = nums[rightPoint];nums[rightPoint] = temp;}}nums[start] = nums[rightPoint];nums[rightPoint] = pivot;return rightPoint;}
}

2 双指针

class Solution {public int[] sortedSquares(int[] nums) {int n = nums.length - 1;int l = 0;int r = n;int[] res = new int[nums.length];while (l <= r) {if (Math.abs(nums[l]) > Math.abs(nums[r])) {res[n] = nums[l] * nums[l];l++;} else {res[n] = nums[r] * nums[r];r--;}n--;}return res;}
}

209. 长度最小的子数组

参考文章
题目连接

思路

通过滑动窗口减小双循环的时间复杂度

个人题解

滑动窗口

class Solution {public int minSubArrayLen(int target, int[] nums) {int size = Integer.MAX_VALUE;int total = 0;int start = 0, end = 0;for (int i = 0; i < nums.length; i++) {total += nums[i];while (total >= target) {size = Math.min(size, end - start + 1);total -= nums[start];start++;}end++;}return Integer.MAX_VALUE == size ? 0 : size;}
}

59.螺旋矩阵II

参考文章
题目连接

思路

通过控制上(s)下(x)左(z)右(y)边界来遍历螺旋数组

个人题解

class Solution {public int[][] generateMatrix(int n) {int s = 0, x = n - 1, z = 0, y = n - 1;int[][] res = new int[n][n];int cur = 1;int num = n * n;while (cur <= num) {for (int i = z; i <= y; i++) {res[s][i] = cur++;}s++;for (int i = s; i <= x; i++) {res[i][y] = cur++;}y--;for (int i = y; i >= z; i--) {res[x][i] = cur++;}x--;for (int i = x; i >= s; i--) {res[i][z] = cur++;}z++;}return res;}
}