本文主要是介绍【代码随想录02】977.有序数组的平方 209.长度最小的子数组 59.螺旋矩阵II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
977. 有序数组的平方
题目描述
给你一个按 非递减顺序 排序的整数数组 nums
,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
做题思路
由于原数组存在负数,所以平方后最大值可能出现在两端。因此可以采用双指针法,在数组首尾各放置一个指针,比较指针元素平方后的值。较大者放入结果数组末端,同时该指针向中间移动,继续比较。
参考代码
class Solution {public int[] sortedSquares(int[] nums) {int left=0;//左指针int right=nums.length-1;//右指针int[] result=new int[nums.length];//结果数组int index=result.length-1;//结果数组的指针要放在末端while(left<=right){//注意等号if(nums[left]*nums[left]>nums[right]*nums[right]){//左指针元素平方比右指针大result[index--]=nums[left]*nums[left];//左指针元素平方放入结果数组++left;//左指针移动}else{result[index--]=nums[right]*nums[right];//右指针元素平方放入结果数组--right;//右指针移动}}return result;}
}
209. 长度最小的子数组
题目描述
给定一个含有 n
个正整数的数组和一个正整数 target
。
找出该数组中满足其和 ≥ target
的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr]
,并返回其长度**。**如果不存在符合条件的子数组,返回 0
。
做题思路
由于本题的目标是连续子数组,所以可以想到使用滑动窗口法,也就是双指针法。
将右指针设定为子数组的右端,左指针为左端。首先左指针不动,右指针右移,滑动窗口不断增长,和不断增加,当和 ≥ target
时,此时的长度满足条件,但题目要求长度最小,因此需要与之前成立的长度进行比较,更新最小长度。同时左指针右移,更新滑动窗口。
参考代码
class Solution {public int minSubArrayLen(int target, int[] nums) {int left=0;//左指针int result=Integer.MAX_VALUE;int sum=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++];//左指针右移,开始新一轮窗口}}return result==Integer.MAX_VALUE?0:result;}
}
59. 螺旋矩阵 II
题目描述
给你一个正整数 n
,生成一个包含 1
到 n^2
所有元素,且元素按顺时针顺序螺旋排列的 n x n
正方形矩阵 matrix
。
做题思路
本题的关键点是区间左右的开闭和n 奇偶的分别处理,将一圈分为上下左右 4 个左开右闭的区间。
参考代码
//采取左闭右开区间
class Solution {public int[][] generateMatrix(int n) {int loop=0;//循环数int[][] res=new int [n][n];int start=0;//每次循环从(start,start)开始int count=1;//填入的数int i,j;while(loop++<n/2){//注意没有等号,因为第1圈是第0次循环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){//如果n是奇数,中心要单独赋值res[n/2][n/2]=count;}return res;}
}
这篇关于【代码随想录02】977.有序数组的平方 209.长度最小的子数组 59.螺旋矩阵II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!