开源网站模板cms,网站建设与运营,坪山模板网站建设公司,郑州网站建设工资文章目录 有序数组的平方写在前面题目思路解析暴力解法双指针法 我的代码暴力解法双指针法 参考答案解法暴力方法双指针法 长度最小的子数组原题思路解析暴力法滑动窗口法 我的代码官方题解滑动窗口法 有序数组的平方
写在前面
本人是一名在java后端寻路的小白#xff0c;希… 文章目录 有序数组的平方写在前面题目思路解析暴力解法双指针法 我的代码暴力解法双指针法 参考答案解法暴力方法双指针法 长度最小的子数组原题思路解析暴力法滑动窗口法 我的代码官方题解滑动窗口法 有序数组的平方
写在前面
本人是一名在java后端寻路的小白希望记录此博客来帮助自己理解和日后复习希望也能够帮助到你。
题目
力扣题目链接
给你一个按 非递减顺序 排序的整数数组 nums返回 每个数字的平方 组成的新数组要求也按 非递减顺序 排序。
示例 1
输入nums [-4,-1,0,3,10]输出[0,1,9,16,100]解释平方后数组变为 [16,1,0,9,100]排序后数组变为 [0,1,9,16,100]
示例 2
输入nums [-7,-3,2,3,11]输出[4,9,9,49,121]
思路解析
暴力解法
这道题目给了一个数组当中的元素是非递减的非递减表示元素可能递增也可能当中有重复值不算严格的递增要求把元素进行平方并且也进行非递减排序。
最容易想到的方法也就是暴力解法就是将每个元素进行平方然后对平方后得到的数组使用Arrays类当中的sort方法直接进行排序。
但是一瞬间竟不知如何返回数组的平方。。菜狗如我
双指针法
采用双指针是因为数组平方之后最大值最有可能出现在数组两端最不可能出现在数组中间。因为数组是非递减的而且存在负数所以在平方之后最大值肯定出现在两端。根据这个想法我们可以采用双指针一个指针start指向起始索引一个指针end指向末尾索引然后判断这两个指针指向的数哪一个的平方更大指针指向的元素的平方更大的一者用倒序添加的方式添加到新数组的末尾然后该指针向中间移动一位另一个指针不动继续进行下一次比较。
我的代码
暴力解法
class Solution {public int[] sortedSquares(int[] nums) {//先创建新的数组长度等同于旧数组int[] newArr new int[nums.length];//对旧数组中的元素进行平方然后赋值给新数组的对应位置上的元素for(int i 0; i nums.length; i){newArr[i] nums[i]*nums[i];}//直接调用类Arrays中的sort方法对新数组进行排序Arrays.sort(newArr);//返回新数组return newArr;}
}双指针法
class Solution {public int[] sortedSquares(int[] nums) {//双指针法一个指针i指向数组的起始索引一个指针j指向数组的末尾索引length-1int i 0;int j nums.length - 1;int k nums.length - 1;//定义一个新数组长度等于老数组int[] newArr new int[nums.length];//指针移动的循环结束条件两者相遇表示最后一个元素此时这个元素是需要写入新数组中的while(i j){//比较两个指针指向的元素的平方//假如i指针指向元素的平方更大那么将其写进新数组的末尾元素i指针向后移动j指针不动if(nums[i]*nums[i] nums[j]*nums[j]){newArr[k] nums[i]*nums[i];i;k--;}//假如j指针指向元素的平方更大或者相等那么将其写进新数组的末尾元素j指针向前移动i指针不动else{newArr[k] nums[j]*nums[j];j--;k--;}}return newArr;}
}参考答案解法
暴力方法
class Solution {public int[] sortedSquares(int[] nums) {int[] ans new int[nums.length];for (int i 0; i nums.length; i) {ans[i] nums[i] * nums[i];}Arrays.sort(ans);return ans;}
}
双指针法
class Solution {public int[] sortedSquares(int[] nums) {int n nums.length;int[] ans new int[n];for (int i 0, j n - 1, pos n - 1; i j;) {if (nums[i] * nums[i] nums[j] * nums[j]) {ans[pos] nums[i] * nums[i];i;} else {ans[pos] nums[j] * nums[j];--j;}--pos;}return ans;}
}
长度最小的子数组
原题
力扣题目链接
给你一个按 非递减顺序 排序的整数数组 nums返回 每个数字的平方 组成的新数组要求也按 非递减顺序 排序。
示例 1
输入nums [-4,-1,0,3,10]输出[0,1,9,16,100]解释平方后数组变为 [16,1,0,9,100]排序后数组变为 [0,1,9,16,100]
示例 2
输入nums [-7,-3,2,3,11]输出[4,9,9,49,121]
思路解析
暴力法
这题我没有采用暴力法直接采用了滑动窗口感觉滑动窗口的思想反而更直观一些。暴力法是用两次for循环初始化子数组的最小长度为无穷大第一个for循环遍历数组 nums 中的每个下标作为子数组的开始下标对于每个开始下标 i需要找到大于或等于 i 的最小下标 j使得从 nums[i] 到 nums[j]的元素和大于或等于 s并更新子数组的最小长度此时子数组的长度是 j−i1
滑动窗口法
滑动窗口其实就是双指针的变种。窗口其实就是一个连续的子数组定义两个指针一个指针start指向窗口的开始索引一个指针end指向窗口的末尾索引这两个指针最开始都指向数组的0索引。
滑动窗口法的过程就是end指针通过一个for循环遍历逐步扩大窗口start指针保持不动end每扩大一次就判断start~end窗口当中的元素总和是否大于目标值target。如果窗口的总和大于目标值那么start指针就往前移动一位目的是寻找是否存在潜在的长度更小的而且符合要求的子数组。
怎么求窗口的元素和这里也是我当时临时想出来的。就是在一开始定义一个变量sum表示窗口元素的总和。在end指针往前走、而start指针保持不动的时候每当end向前走一位、窗口扩大一格的时候窗口元素的总和就往前追加而每次start往前走一位窗口元素的总和就减去原来start指针指向的那个元素。
我的代码
我忘记考虑了数组长度为0的情况这时候需要直接返回0。
class Solution {public int minSubArrayLen(int target, int[] nums) {//滑动窗口解法定义窗口的起始指针和末尾指针int i 0;int j 0;//定义一个变量来存储窗口的和int sum 0;//定义一个变量记录最小的窗口长度int shortest nums.length 1;//用一个for循环中的i指针表示窗口的末尾索引用j指针表示窗口的起始索引for(i 0; i nums.length; i){sum sum nums[i];//判断窗口当中所有元素的和是否大于等于目标值while(sum target){//窗口元素和大于目标值//判断如果窗口的长度1说明此时是最小长度直接返回1if(i-j1 1){return 1;}//如果子数组的长度不是1说明还可能存在潜在的最小窗口长度此时jelse{//如果此时窗口长度小于最小窗口长度则将此时窗口的长度赋值给最小长度if(i-j1 shortest){shortest i-j1;}sum sum - nums[j];j;}}//如果窗口之和不符合条件则i继续然后给窗口之和加上i指向的最新的值随后继续判断}if(shortest nums.length 1){return 0;}return shortest; }
}官方题解
滑动窗口法
class Solution {public int minSubArrayLen(int s, int[] nums) {int n nums.length;if (n 0) {return 0;}int ans Integer.MAX_VALUE;int start 0, end 0;int sum 0;while (end n) {sum nums[end];while (sum s) {ans Math.min(ans, end - start 1);sum - nums[start];start;}end;}return ans Integer.MAX_VALUE ? 0 : ans;}
}
