代码随想录算法训练营第二天-977有序数组的平方、209长度最小的子数组、59螺旋矩阵II
-
前言
状态：977、209 通过。59 没有思路
-
更新
1
2
| 24.04.18 初始记录
24.04.21 补充螺旋矩阵的题解
|
初步题解
977 有序数组的平方
题目链接：https://leetcode.cn/problems/squares-of-a-sorted-array/
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
33
| public class LE977 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
int[] nums = Arrays.stream(s.substring(1, s.length() - 1).split(","))
.mapToInt(Integer::parseInt)
.toArray();
System.out.println(Arrays.toString(sortedSquares(nums)));
}
public static int[] sortedSquares(int[] nums) {
int i = 0;
int j = nums.length - 1;
int k = nums.length - 1;
int[] ints = new int[nums.length];
while (i <= j) {
int i2 = nums[i] * nums[i];
int j2 = nums[j] * nums[j];
ints[k] = Math.max(i2, j2);
k--;
if (i2 >= j2) {
i++;
} else {
j--;
}
}
return ints;
}
}
|
209 长度最小的子数组
题目链接：https://leetcode.cn/problems/minimum-size-subarray-sum/
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
33
34
35
36
37
38
39
40
41
| public class LE209 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int target = Integer.parseInt(scanner.nextLine());
String s = scanner.nextLine();
int[] nums = Arrays.stream(s.substring(1, s.length() - 1).split(","))
.mapToInt(Integer::parseInt)
.toArray();
System.out.println(minSubArrayLen(target, nums));
}
public static int minSubArrayLen(int target, int[] nums) {
int min = 0;
for (int i = 0, j = 0; i < nums.length && j < nums.length; ) {
int subArraySum = getSum(nums, i, j);
if (target == subArraySum) {
min = Math.min(min, j - i + 1);
i++;
j = i;
if (min == 1) {
break;
}
} else if (target < subArraySum) {
i++;
j = i;
} else {
j++;
}
}
return min;
}
private static int getSum(int[] nums, int i, int j) {
int sum = 0;
for (int k = i; k <= j; k++) {
sum += nums[k];
}
return sum;
}
}
|
59 螺旋矩阵 II
题目链接：https://leetcode.cn/problems/spiral-matrix-ii/
看讲解
977 有序数组的平方
文章讲解：https://programmercarl.com/0977.%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E7%9A%84%E5%B9%B3%E6%96%B9.html
视频讲解： https://www.bilibili.com/video/BV1QB4y1D7ep
209 长度最小的子数组
文章讲解：https://programmercarl.com/0209.%E9%95%BF%E5%BA%A6%E6%9C%80%E5%B0%8F%E7%9A%84%E5%AD%90%E6%95%B0%E7%BB%84.html
视频讲解：https://www.bilibili.com/video/BV1tZ4y1q7XE
还有一个进阶的解法，打算明天再看看，不能再熬夜了。
59 螺旋矩阵 II
文章讲解：https://programmercarl.com/0059.%E8%9E%BA%E6%97%8B%E7%9F%A9%E9%98%B5II.html
视频讲解：https://www.bilibili.com/video/BV1SL4y1N7mV/
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
|
public class LE59 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = Integer.parseInt(scanner.nextLine());
System.out.println(Arrays.deepToString(generateMatrix(n)));
}
public static int[][] generateMatrix(int n) {
int[][] ints = new int[n][n];
int startX = 0;
int startY = 0;
int k = 1;
int loop = 1;
int i, j;
while (k <= n * n && loop <= n / 2) {
for (i = startX; i < n - loop; i++) {
ints[i][startY] = k++;
}
for (j = startY; j < n - loop; j++) {
ints[i][j] = k++;
}
for (; i > startX; i--) {
ints[i][j] = k++;
}
for (; j > startY ; j--) {
ints[i][j] = k++;
}
startX++;
startY++;
loop++;
}
if (n % 2 == 1) {
ints[startX][startY] = k;
}
return ints;
}
}
public static int[][] generateMatrix(int n) {
int[][] ints = new int[n][n];
int startX = 0;
int startY = 0;
int k = 1;
int loop = 1;
int i, j;
while (k <= n * n && loop <= n / 2) {
for (j = startY; j < n - loop; j++) {
ints[startX][j] = k++;
}
for (i = startX; i < n - loop; i++) {
ints[i][j] = k++;
}
for (; j > startY ; j--) {
ints[i][j] = k++;
}
for (; i > startX; i--) {
ints[i][j] = k++;
}
startX++;
startY++;
loop++;
}
if (n % 2 == 1) {
ints[startX][startY] = k;
}
return ints;
}
|