您现在的位置是:首页 >学无止境 >代码随想录算法训练营day02_ 977. 有序数组的平方、209.长度最小的子数组 、59.螺旋矩阵II网站首页学无止境

代码随想录算法训练营day02_ 977. 有序数组的平方、209.长度最小的子数组 、59.螺旋矩阵II

小C卷Java 2024-06-17 06:01:02
简介代码随想录算法训练营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;
	}
}

方法二:滑动窗口

思路:维护leftright两个变量,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;
    }
}
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。