Day02

发布时间:2024年01月14日

今日任务:

  • 977 有序数组的平方
  • 209 长度最小的子数组
  • 59 螺旋矩阵Ⅱ

977?有序数组的平方

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

双指针问题,以及数组本身时有序的;

思路:

  1. 左、右两个指针,比较两边的平方数,将较大的数从后往前放进新生成的数组
  2. 若左边的平方数 大于 右边的平方数,则需要将左边的指针向右移动一格
  3. 若左边的平方数 小于 右边的平方数,则需要将右边的指针向左移动一格
  4. 直到两个指针指向同一个位置,就是最小的那一个,将平方数放进数组后,退出
class Solution {
    public int[] sortedSquares(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int left = 0, right = n - 1;
        while(left <= right) {
            if(nums[left] * nums[left] <= nums[right] * nums[right]) {
                res[--n] = nums[right] * nums[right];
                right--;
            }else {
               res[--n] = nums[left] * nums[left];
                left++;
            }
        }
        return res;
    }
}

209 长度最小的子数组

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

暴力遍历的话,时间超市;

滑动窗口问题,就是不断的调节子序列的起始位置和终止位置

思路:

  1. 如果当前窗口的值大于等于 target 了,窗口的后面就要向前移动了,前面保持不动
  2. 如果当前窗口的值小于 target 了,窗口的后面保持不动,前面向前移动
  3. 每次满足条件的时候都需要进行比较 res 的值,选择较小者
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        if(n == 0) {
            return 0;
        }
        int res = Integer.MAX_VALUE;
        int start = 0, end = 0;
        int sum = 0;
        while(end < n) {
            sum += nums[end];
            while(sum >= target) {
                res = Math.min(res, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

59 螺旋矩阵Ⅱ

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

关键还是在转圈的逻辑,以及四个边界的变化情况

class Solution {
    public int[][] generateMatrix(int n) {
        int l = 0, r = n -1, t = 0, b = n - 1;
        int[][] mat = new int[n][n];

        int num = 1, tar = n * n;
        while(num <= tar) {
            for(int i = l; i <= r; i++) mat[t][i] = num++;
            t++;
            for(int i = t; i <= b; i++) mat[i][r] = num++;
            r--;
            for(int i = r; i >= l; i--) mat[b][i] = num++;
            b--;
            for(int i = b; i >= t; i--) mat[i][l] = num++;
            l++;
        }
        return mat;
    }
}

文章来源:https://blog.csdn.net/lin_xiangxiang/article/details/135589264
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。