算法训练营（day02）

数组理论基础

• 数组是存放在连续内存空间上的相同类型数据的集合。

• 数组可以方便的通过下标索引的方式获取到下标对应的数据。

  • 数组下标都是从0开始的。
  • 数组内存空间的地址是连续的

• 因为数组的在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，只能覆盖原有地址的元素进行修改

977.有序数组的平方

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

给你一个按非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

解题思路

解题过程：

1. 设定左右指针left，right
2. 定义新数组 res[] 用于存放排序后的数组
3. 比较 nums[left] * nums[left] 和 nums[right] * nums[right] 的大小
4. 从后往前，依次排列

详细代码

class Solution {
    public int[] sortedSquares(int[] nums) {
        int index = nums.length - 1;
        int left = 0, right = nums.length - 1;
        int[] res = new int[nums.length];

        while(left <= right){
            if(nums[left] * nums[left] < nums[right] * nums[right]){
                res[index] = nums[right] * nums[right];
                index--;
                right--;
            }else{
                res[index] = nums[left] * nums[left];
                index--;
                left++;
            }
        }
        return res;
    }
}

209.长度最小的子数组

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

给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回 0 。

解题思路

解题过程：

1. 设定左右指针left，right
2. 设定累加值 sum += nums[right]，比较 sum 和 target 的大小
   • sum >= target 则 sum -= nums[left]， left 指针右移
   • sum < target 则继续累加
3. 遍历全局结束，定义res ，取最小值
4. 如果不存在符合条件的子数组，res 返回 0

详细代码

暴力解法：

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = 0, len = nums.length;
        int sum = 0;
        int res = Integer.MAX_VALUE;

        for(; right < len; right++){
            sum += nums[right];
            while(sum >= target){
                res = Math.min(res, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

59.螺旋矩阵II

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

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

解题思路

模拟矩阵的生成：初始位置设为矩阵的左上角，初始方向设为向右。若下一步的位置超出矩阵边界，或者是之前访问过的位置，则顺时针旋转，进入下一个方向。

详细代码

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        int index = 1;
        int left = 0, right = n - 1, up = 0, down = n - 1;

        while(index <= n * n){
            for(int i = left; i <= right; ++i){
                res[up][i] = index++;
            }
            up++;
            for(int i = up; i <= down; ++i){
                res[i][right] = index++;
            }
            right--;
            for(int i = right; i >= left; --i){
                res[down][i] = index++;
            }
            down--;
            for(int i = down; i >= up; --i){
                res[i][left] = index++;
            }
            left++;
        }
        return res;
    }
}