您现在的位置是:首页 >学无止境 >代码随想录算法训练营day02_ 977. 有序数组的平方、209.长度最小的子数组 、59.螺旋矩阵II网站首页学无止境
代码随想录算法训练营day02_ 977. 有序数组的平方、209.长度最小的子数组 、59.螺旋矩阵II
977.有序数组的平方
一刷:在一刷的时候,我的思路是暴力,直接遍历数组,然后将每个数组的元素平方放入新的数组,最后进行Arrays.sort()
排序。
二刷:在看到有序数组的条件后,第一时间想到了双指针。因为在有负数的情况下,平方后会变大。
方法一:暴力解法
思路:遍历 -> 排序
时间复杂度:O(nlogn)
空间复杂度:O(n)
class Solution {
public int[] sortedSquares(int[] nums) {
int[] res = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
res[i] = nums[i] * nums[i];
}
Arrays.sort(res);
return res;
}
}
方法二:双指针
思路:因为数组有序,如果有负数,最大的值肯定在数组的两端,只需要依次比较两端的数平方后的大小;如果没有负数,也同理。
时间复杂度:O(n)
空间复杂度:O(n)
遇到的问题:
1.注意left <= right
,不然会丢失当left = right
时的一个结果。
class Solution {
public int[] sortedSquares(int[] nums) {
int len = nums.length;
int left = 0;
int right = nums.length - 1;
int i = len - 1;
int[] res = new int[len];
while (left <= right) {
if (nums[left] * nums[left] <= nums[right] * nums[right]) {
res[i] = nums[right] * nums[right];
right--;
i--;
} else {
res[i] = nums[left] * nums[left];
left++;
i--;
}
}
return res;
}
}
209.长度最小的子数组
一刷:在不知道滑动窗口概念的时候,想着用暴力的解法,两层for循环来解,遍历所有子数组,来计算结果,但是超时了。看题解了解初识了滑动窗口算法
二刷:滑动窗口
方法一:暴力解法
思路:遍历所有子数组,内层for
循环从i开始往后遍历,超时了
时间复杂度:O(n2)
空间复杂度:O(1)
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length;
int res = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += nums[j];
if (sum >= target) {
res = Math.min(res, j - i + 1);
break;
}
}
}
return res == Integer.MAX_VALUE ? 0 : res;
}
}
方法二:滑动窗口
思路:维护left
和right
两个变量,right
向后遍历,往sum
中累加元素,当>=target
值后,left
右移来将窗口中的元素从最左开始往外移除
时间复杂度:O(n)
空间复杂度:O(1)
遇到的问题:
1.使用while
循环而不是if
判断,比如target
为5,当前数组为[2,2,4],如果使用if
只会将2移除,但是此时sum
还是大于target
的,所以要继续移除。
2.返回时需要和Integer.MAX_VALUE
去对比,因为可能没有找到答案。
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int sum = 0;
int res = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
res = Math.min(res, right - left + 1);
sum -= nums[left++];
}
}
return res == Integer.MAX_VALUE ? 0 : res;
}
}
59.螺旋矩阵II
一刷:没思路,看了题解,主要就是要做一个边界收缩的问题。
二刷:直接秒
class Solution {
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int start = 0;
int count = 1;
int loop = 0;
int i, j;
while (loop++ < n / 2) {
for (j = start; j < n - loop; j++) {
res[start][j] = count++;
}
for (i = start; i < n - loop; i++) {
res[i][j] = count++;
}
for (; j >= loop; j--) {
res[i][j] = count++;
}
for (; i >= loop; i--) {
res[i][j] = count++;
}
start++;
}
if (n % 2 != 0) {
res[start][start] = count++;
}
return res;
}
}
拓展
54.螺旋矩阵
思路:相比于螺旋矩阵II更加的复杂,因为螺旋矩阵是一个正方形,行和列长度相同,这样控制的圈数条件会更简单,而本题由于行和列随机,需要拿出来单独讨论会更复杂,这种模拟题感觉还是很需要逻辑清楚的,自己写很难把方方面面考虑得完全到位。会出现各种各样的小bug。
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
// 初始化结果列表
List<Integer> res = new ArrayList<>();
// 如果矩阵为空,返回空列表
if (matrix.length == 0 || matrix[0].length == 0)
return res;
// 获取矩阵的行数和列数
int rows = matrix.length, columns = matrix[0].length;
// 计算矩阵中的元素总数
int total = rows * columns;
// 初始化起始行和列
int startx = 0, starty = 0;
// 计算需要遍历的圈数,每遍历一圈行和列都会减少2
int loop = Math.min(rows, columns) / 2;
// 计算矩阵中心位置
int mid = Math.min(rows, columns) / 2;
// 记录已经遍历过的元素个数
int count = 0;
// 初始化偏移量,用于跳过已经遍历过的元素
int offset = 1;
int i, j;
// 开始按照螺旋顺序遍历矩阵
while (loop-- > 0) {
// 从左到右遍历矩阵上边
i = startx;
j = starty;
for (j = starty; j < starty + columns - offset; j++) {
res.add(matrix[startx][j]);
count++;
}
// 从上到下遍历矩阵右边
for (i = startx; i < startx + rows - offset; i++) {
res.add(matrix[i][j]);
count++;
}
// 从右到左遍历矩阵下边
for (; j > starty; j--) {
res.add(matrix[i][j]);
count++;
}
// 从下到上遍历矩阵左边
for (; i > startx; i--) {
res.add(matrix[i][starty]);
count++;
}
// 更新起始行和列
startx++;
starty++;
// 更新偏移量
offset += 2;
}
// 如果矩阵的行数和列数不相等,需要遍历剩余的一行或一列
if (Math.min(rows, columns) % 2 == 1) {
if (rows > columns) {
for (i = mid; i < mid + rows - columns + 1; i++) {
res.add(matrix[i][mid]);
count++;
}
} else {
for (j = mid; j < mid + columns - rows + 1; j++) {
res.add(matrix[mid][j]);
count++;
}
}
}
// 返回结果列表
return res;
}
}