Day2 |977.有序数组的平方& 209.长度最小的子数组&59.螺旋矩阵II

977.有序数组的平方

这题太简单了,中间的排序我用的选择排序

贴代码了

public int[] sortedSquares(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i]*nums[i];
        }
        for (int i = 0; i < nums.length; i++) {
            int min = i;
            for (int j = i+1; j < nums.length; j++) {
                if(nums[min]>nums[j]){
                    min = j;
                }
            }
            if(nums[min]!=nums[i]){
                int tmp = nums[i];
                nums[i] = nums[min];
                nums[min] = tmp;
            }
        }
        return nums;
    }

209.长度最小的子数组

思路 : 我刚开始想的解法就是双指针滑动解法,如果使用双指针滑动暴力解法最后在力扣里面会超时,但是自己测试没有问题

但是想通过力扣确实还需要优化成下面所谓的滑动窗口的解法.

@Test
    public void test2() {
        int[] nums = {2, 3, 1, 2, 4, 3};
        int target = 7;
        System.out.println(minSubArrayLen2(target, nums));
    }

    public int minSubArrayLen(int target, int[] nums) {//双指针暴力解法
        int sum;
        int res = Integer.MAX_VALUE;
        if (target == 0) {
            return 0;
        }

        for (int i = 0; i < nums.length; i++) {
            sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum >= target) {
                    if (res > j - i + 1) {
                        res = j - i + 1;
                        break;
                    }
                }
            }
        }
        if (res == Integer.MAX_VALUE) return 0;
        return res;
    }

    public int minSubArrayLen2(int target, int[] nums) {//比较简洁的解法,也就是所谓的滑动窗口解法
        int left = 0;
        int right = 0;
        int res = Integer.MAX_VALUE;
        int sum = nums[0];

        while (true) {
            if (sum >= target) {
                if (res > right - left + 1) {
                    res = right - left + 1;
                }
                sum -= nums[left];
                left++;

            } else {
                right++;
                if (right >= nums.length) {
                    if (res == Integer.MAX_VALUE) return 0;
                    else return res;
                }
                sum += nums[right];

            }
        }

59.螺旋矩阵II

这题我之前做过对角线矩阵和旋转矩阵,我一般的思路都是直接模拟矩阵,然后把矩阵构造出来

至于这种方式在之后的矩阵题目中可不可行,还有待验证.

	@Test
    public void test3() {
        int n = 4;
        int[][] res = generateMatrix(n);
        for (int i = 0; i < res.length; i++) {
            for (int j = 0; j < res.length; j++) {
                System.out.print(res[i][j] + "\t");
            }
            System.out.println();
        }
    }

    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];

        int num = 1;
        int l = 0;
        int r = n - 1;
        int t = 0;
        int b = n - 1;
        while (num <= n * n) {
            for (int i = l; i <= r; i++) {// 从左向右
                matrix[t][i] = num;
                num++;
            }
            t++;
            for (int i = t; i <= b; i++) { // 从上到下
                matrix[i][r] = num;
                num++;
            }
            r--;
            for (int i = r; i >= l; i--) { //从右到左
                matrix[b][i] = num;
                num++;
            }
            b--;
            for (int i = b; i >= t; i--) { // 从下到上
                matrix[i][l] = num;
                num++;
            }
            l++;
        }
        return matrix;

    }

小插曲 关于动态规划

动态规划今天有些顿悟,但还需要验证自己的想法

猜想 :

1. 动态规划是通过转移方程体现动态的

2. 动态规划是通过计算所有情况的状态,存入数组,来实现对某一状态的快速查找

3. 动态规划中很多状态的重复转移导致我们可以把这类情况总结为一个状态转移方程

4. 一般可以写成动态规划的题都有一部分可以使用递归的特征

5. 动态规划有一些状态不在可重复转移的过程中,因此状态转移方程才出现常见的解题思路中的边界条件,其实边界条件理解为另外的状态转移方程比较好.

6. 状态转移方程分为两个:

   • 一般情况下的状态转移方程
   • 边界情况下的状态转移方程

7. 关于使用动态规划思维的题的返回值,通常是状态转移的目标结果.

以上均为我的猜想,目前还没有验证猜想,等后续更新吧.