[数据结构与算法]随想 day2

随想 day2
题目一 有序数组的平方 按照不递减的顺序排列

出错原因：sort的用法不熟悉 正确格式 --> Arrays.sort(参数)； line6:不需要在加 int 修饰符。
另外：要学会分析时间复杂度问题
法一：暴力解法

import java.util.*;
class Solution {
    //思路：先遍历数组，并计算平方
    //进行排序
    public int[] sortedSquares(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            nums[i] = nums[i] * nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }
}

法二：双指针法
出错原因：for循环 和 while 循环的选择不明确
if 循环只可以判断一次即跳出循环 ；而while循环可以判断多次
for循环的条件语句，java语法判断和c++有所区别

创建的新的数组长度要与原始数组保持一致

class Solution {
    // 有序数组的平方  双指针法
    //思路：定义一个新的数组，用来存放新的平方项元素
    public int[] sortedSquares(int[] nums) {
        int i = 0;
        int j = nums.length - 1;
        int k = nums.length - 1;               //索引要 - 1
        int [] result = new int[nums.length]; //定义新的数组 长度为nums.length    不需要 - 1
        while (i <= j) {
            if (nums[i] * nums[i] > nums[j] * nums[j]) {
                result[k] = nums[i] * nums[i];
                k--;
                i++;
            } else {
                result[k] = nums[j] * nums[j];
                j--;
                k--;
            }
        }
        return result;   
    }
}

题目二：长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
法一：暴力解法
思路重述：… []

class Solution {
//暴力搜索空间    双for 双指针  计算复杂度为O(n**2)
    public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE;
        int sum = 0;
        int sub = 0;
        for (int i = 0; i < nums.length; i++) {//左指针
            sum = 0;
            for (int j = i; j < nums.length; j++) {//右指针
                sum += nums[j];//注意此处是j 而不是i
                if (sum > target) {
                    sub = j - i + 1;
                    result = result < sub ? result : sub;
                    break;
                }
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

思想：用两个for循环，第一个
法二：滑动窗口
思想：一个指向终端位置，一个指向起点，

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int result = Integer.MAX_VALUE;
        int sum = 0;
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {//满足条件，则更新窗口的起始位置
                result = Math.min(result, right - left + 1);
                //通过上一步获得子窗口长度后，再进行下一步索引更新
                sum -= nums[left];
                left++;
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

注意：sum -= nums[left];
left++; 的前后顺序细节问题

题目三 螺旋矩阵

思路整理[]
问题？为什么奇数时，中间的数需要单独处理？[x]
偶数时候正好可以处理完整的圈
奇数时中间的孤立的会处理不到

class Solution {
    public int[][] generateMatrix(int n) {
        int loop = 0;
        int[][] res = new int[n][n];
        int start = 0;//每次循环的开始点
        int count = 1;//定义填充数字
        int i, j;


        while (loop++ < n / 2) {//判断边界后，loop从1开始
            //模拟上侧从左到右
            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 == 1) {
            res[start][start] = count;
        }
        return res;
    }
}