©2020-2024 ioDraw All rights reserved,
Privacy Policy
977.有序数组的平方
给你一个按 非递减顺序排序的整数数组 nums，返回 每个数字的平方组成的新数组，要求也按 非递减顺序排序。
输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100] 排序后，数组变为
[0,1,9,16,100]
思路1：平方后排序，排序的话第一反应考虑最简单的冒泡排序
class Solution { public int[] sortedSquares(int[] nums) { int[] NewArry=new
int[nums.length]; for(int i=0;i<nums.length;i++){ NewArry[i]=nums[i]*nums[i]; }
//冒泡排序 for(int i=0;i<NewArry.length;i++){ for(int j=i+1;j<NewArry.length;j++){
if(NewArry[i]>NewArry[j]){ int temp=NewArry[j]; NewArry[j]=NewArry[i];
NewArry[i]=temp; } } } return NewArry; } }
平方的过程很简单，遍历数组，给数据进行平方
冒泡排序的基本原理：
* 比较相邻的元素，如果前一个元素比后一个元素大，则交换位置
* 对每一对相邻元素做同样的工作，从开始第一对元素到结尾第一对元素，最终最后位置即为最大值。
该思路的缺点，冒泡排序需要双层1for循环，算法时间复杂度为O(N^2)，适用于排序数量过少的时候，所以较浪费时间。
思路2：使用双指针
Day1进行过双指针的训练，但是看到这道题还是没有想起如何运用，看了部分解析之后明白了输入数组是有序的，平方之后也可以找到一定的规律，从左边和右边分别出发对比提高效率。
class Solution { public int[] sortedSquares(int[] nums) { int[] NewArry=new
int[nums.length]; int j=nums.length-1; int i=0; int index=nums.length-1;
while(i<=j){ if(nums[i]*nums[i]<=nums[j]*nums[j]){
NewArry[index--]=nums[j]*nums[j]; j--; }else{ NewArry[index--]=nums[i]*nums[i];
i++; } } return NewArry; } }
定义一个新数组NewArry，和nums数组一样的大小，让index指向NewArry数组终止位置。
如果nums[i]*nums[i]<=nums[j]*nums[j] 那么NewArry[index--]=nums[j]*nums[j]，并且让j--
如果nums[i]*nums[i]>nums[j]*nums[j] 那么NewArry[index--]=nums[i]*nums[i]，并且让i++
该算法的的时间复杂度为O(n)
209.长度最小的子数组
给定一个含有 n ****个正整数的数组和一个正整数 target **。**找出该数组中满足其和 ****≥ target **的长度最小的 连续子数组
[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。**如果不存在符合条件的子数组，返回 0 。
输入：target = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
该题的思路也是双指针的一个扩展，刚开始做没办法确定结束的指针怎么处理，于是看了解析才有了思路。
滑动窗口：不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
1、设置左右两个指针
2、又指针遍历数组，并将遍历到的数据相加
若while(sum≥target)（等号的必要性是为了确定最短子序列），移动左指针，并将左指针遍历到的数据减去在进行循环判断
3、最终找到最短子序列
class Solution { public int minSubArrayLen(int target, int[] nums) { int
left=0; int sum=0; int reslut=Integer.MAX_VALUE; for(int
right=0;right<nums.length;right++){ sum+=nums[right]; while(sum>=target){
reslut=Math.min(reslut,right-left+1); sum-=nums[left]; left++; } } return
reslut==Integer.MAX_VALUE?0:reslut; } }
刚开始不理解reslut=Integer.MAX_VALUE的必要性，到了后续才知道都是为了后续的比较，使用Math.min
59. 螺旋矩阵 II
给你一个正整数 n，生成一个包含 1到 n2所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
输入：n = 3 输出：[[1,2,3],[8,9,4],[7,6,5]]
这道题看似复杂，但并不需要复杂的推导只需要按照循环逐步去解决
* 上侧的从左到右 处理行（start，n-loop）；列++
* 右侧的从上到下 处理列（start，n-loop）; 行++
* 下侧的从右到左 处理行（接上侧最后的一列，loop）；列—
* 左侧的从下到上 处理行（loop，2中最后处理的一行）；行— class Solution { public int[][]
generateMatrix(int n) { int loop=0; //循环次数 int start=0; int[][] NewArray=new
int[n][n]; int i,j; int count=1; while(loop++<n/2){ //1.上面从左到右
for(j=start;j<n-loop;j++){ NewArray[start][j]=count++; } //2.右侧从上到下
for(i=start;i<n-loop;i++){ NewArray[i][j]=count++; } //3.下面从右到左
for(;j>=loop;j--){ NewArray[i][j]=count++; } //4.左边从下到上 for(;i>=loop;i--){
NewArray[i][j]=count++; } start++; } if(n%2==1){ NewArray[start][start]=count;
} return NewArray; } }
很多小细节点：
①这里循环次数是0所以一开始就要++
②当n是奇数的时候，最中间会出现一个最终累加的count需要记得添加
③行和列的变化不要搞错，可以画图让自己理清楚
④在循环之外定义了i,j所以1,2步循环结束后i,j是可以保存继续使用到3,4步骤
今日总结：难度比昨天的大了一些，但都是双指针的变形，切记将问题考虑复杂，需要简单化理解和处理，接下来不仅要完成每日题目，还要提高训练速度。