代码随想录算法训练营第二天 | 977.有序数组的平方 ，209.长度最小的子数组 ，59.螺旋矩阵II，54. 螺旋矩阵

977.有序数组的平方

题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/

方法一 双指针

1 方法思想

利用双指针从输入数组的两端开始对比，看谁的绝对值大，将绝对值大的一端从后向前依次插入结果数组中（同时将指针向中间移动）。

2 代码实现

class Solution {
public int[] sortedSquares(int[] nums) {
		int lenNums = nums.length;
		int leftIndex = 0;
		int rightIndex = lenNums - 1;
		int[] result = new int[lenNums];
		int k = lenNums - 1;
		while (leftIndex <= rightIndex){
			int tempL = Math.abs(nums[leftIndex]);
			int tempR = Math.abs(nums[rightIndex]);
			if (tempL > tempR){
				result[k--] = (int) Math.pow(tempL, 2);
				leftIndex ++;
			}else {
				result[k--] = (int) Math.pow(tempR, 2);
				rightIndex --;
			}
		}
		return result;
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3 复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)

4 涉及到知识点

双指针

方法二 暴力解法

1 方法思想

先依次对数组中的元素计算平方，再进行快速排序

2 代码实现

略
1

3 复杂度分析

时间复杂度：O(n + nlogn)
空间复杂度：O(1)

4 涉及到知识点

快速排序

收获和总结

1.遇到的困难？

对于双指针法，第一反应是先找到绝对值最小的元素，从中间向两端进行遍历，虽然时间复杂上相差不多近似O(n)，但是当两端的指针之一到达边界后，需要另外的判断条件，步骤上相对来说有较多的冗余。

public int[] sortedSquares(int[] nums) {
		int leftIndex = 0;
		int rightIndex = 1;
		int lenNums = nums.length;
		int[] result = new int[lenNums];
		int k = 0;
		if (lenNums == 1) return new int[]{(int) Math.pow(nums[0], 2)};
		while (rightIndex < lenNums && Math.abs(nums[leftIndex]) >= Math.abs(nums[rightIndex])) {
			leftIndex++;
			rightIndex++;
		}
		while (leftIndex >= 0 && rightIndex < lenNums){
			if (Math.abs(nums[leftIndex]) <= Math.abs(nums[rightIndex])) {
				result[k++] = (int) Math.pow(nums[leftIndex--], 2);
			} else {
				result[k++] = (int) Math.pow(nums[rightIndex++], 2);
			}
		}
		if (leftIndex == -1 && rightIndex < lenNums) {
			while (rightIndex < lenNums) {
				result[k++] = (int) Math.pow(nums[rightIndex++], 2);
			}
		}else if (leftIndex > -1 && rightIndex == lenNums){
			while (leftIndex > -1) {
				result[k++] = (int) Math.pow(nums[leftIndex--], 2);
			}
		}
		return result;
	}
	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

2 收获

快速排序待掌握
1

学习链接

https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E6%80%9D%E8%B7%AF

209.长度最小的子数组

题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/

方法一 双指针

1 方法思想

滑动窗口，主要重点在于子串需要是连续的。

2 代码实现

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int minLen = Integer.MAX_VALUE;
		int left = 0;
		int right = 0;
		int sum = 0;
		while (right < nums.length) {
			sum += nums[right++];
			while (sum >= target) {
				int len = right - left;
				if (len < minLen) {
					minLen = len;
				}
				sum -= nums[left++];
			}
		}
		return minLen == Integer.MAX_VALUE ? 0 : minLen;
		
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3 复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

4 涉及到知识点

快速排序

总结

1.没有审题完整，还以为是子串和要严格等于目标值，题目中给的是大于等于即可。

学习链接

https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E6%80%9D%E8%B7%AF

59.螺旋矩阵II

题目链接：https://leetcode.cn/problems/spiral-matrix-ii/

方法一 模拟

1 方法思想

模拟法，主要思想是以一圈一圈的遍历给定的矩阵，题目中给的是长宽相同的矩阵，可以忽略部分因素。
如果是长度和高度不同的矩阵该如何处理？参考题目leetcode54。

2 代码实现

class Solution {
    public int[][] generateMatrix(int n) {
     	int[][] result = new int[n][n];
		int startX = 0;
		int startY = 0;
		int num = 1;
		int loop = n / 2;
		
		while (loop-- > 0) {

			for (int i = startY; i < n - startY - 1; i++) {
				result[startX][i] = num++;
			}
			for (int i = startX; i < n - startX - 1; i++) {
				result[i][n - startY - 1] = num++;
			}
			for (int i = n - startY - 1; i > startY; i--) {
				result[n - startX - 1][i] = num++;
			}
			for (int i = n - startX - 1; i > startX; i--) {
				result[i][startY] = num++;
			}
			startX++;
			startY++;
		}
		if (n % 2 == 1) {
			int mid = n / 2;
			result[mid][mid] = n * n;
		}
		return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

3 复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)

4 涉及到知识点

快速排序

总结

1.该题目只是解出来了，但是该类的题目还没有解决。

学习链接

https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E6%80%9D%E8%B7%AF

54. 螺旋矩阵

题目链接：https://leetcode.cn/problems/spiral-matrix-ii/

方法一 模拟

1 方法思想

和59题相比，一个是写出一个是写入，大同小异。

2 代码实现

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
       	List<Integer> result = new ArrayList<>();
		int right = matrix[0].length - 1;
		int left = 0;
		int top = 0;
		int bottom = matrix.length - 1;
		while (left <= right && top <= bottom) {
			
			for (int column = left; column <= right; column++) {
				result.add(matrix[top][column]);
			}
			for (int row = top+1; row<= bottom; row++){
				result.add(matrix[row][right]);
			}
			if (left < right && top < bottom) {
				for (int column = right - 1; column > left; column --){
					result.add(matrix[bottom][column]);
				}
				for (int row = bottom; row > top; row --){
					result.add(matrix[row][left]);
				}
			}
			left ++;
			right --;
			top ++;
			bottom --;
		}
		return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

3 复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)

4 涉及到知识点

学习链接

https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E6%80%9D%E8%B7%AF