网站下载软件入口,邯郸网站开发公司,wordpress微信小程序源码,wordpress文章推送到微信977.有序数组平方 题目链接#xff1a; 977. 有序数组的平方 - 力扣#xff08;LeetCode#xff09; 文章讲解#xff1a;代码随想录 视频讲解#xff1a; 双指针法经典题目 | LeetCode#xff1a;977.有序数组的平方_哔哩哔哩_bilibili 第一想法
暴力算法肯定是先将元素…977.有序数组平方 题目链接 977. 有序数组的平方 - 力扣LeetCode 文章讲解代码随想录 视频讲解 双指针法经典题目 | LeetCode977.有序数组的平方_哔哩哔哩_bilibili 第一想法
暴力算法肯定是先将元素平方然后Arrays.sort()时间复杂度取决于快排O(n logn)
代码随想录
有序数组 [ -5 -3 1 3 5] 按从小到大排列其平方之后两边一定是最大的中间一定是最小的所以定义双头指针每次筛选出最大值从新数组result的最大索引处填入。这样更新一轮下来新数组就会从大到小填好。
定义双头指针比较出最大的元素有些像快速排序算法。
遇到问题
若先将元素更新为平方然后再用于比较那么这个元素如果这次尚未选中下轮就会继续平方。所以这个判断逻辑应放到比较条件里。
代码
class Solution1 {public int[] sortedSquares(int[] nums) {int[] result new int[nums.length];//定义新数组大小应与原数组相同int left 0;int right nums.length - 1;//定义原数组双头指针int index nums.length - 1;//定义填充新数组的索引指针for(;leftright;){//leftright有意义应当进入循环if(nums[left]*nums[left]nums[right]*nums[right]){result[index--] nums[left]*nums[left];//若左边元素大则复制给新数组左边索引1left;}else{result[index--] nums[right] * nums[right];//若右边元素大则复制给新数组右边索引-1或者两边相同则选谁填充都无所谓right--;}}return result;}
}
209.长度最小的子数组 题目链接 209. 长度最小的子数组 - 力扣LeetCode 文章讲解代码随想录 视频讲解拿下滑动窗口 | LeetCode 209 长度最小的子数组_哔哩哔哩_bilibili 第一想法
首先一定是暴力想法逐个数组遍历若总和满足target则记录数组长度与上次符合要求的子数组结果作比较若长度更小则更新子数组。
代码随想录想法
用一个循环解决问题那么j指的是子数组的终止位置其起始位置的确定就在于滑动窗口的策略实现。如果指的是起始位置那么只有一个一个向后遍历才能返回子数组思路和暴力解法一致。
移动起始位置的条件是一旦当数组子数组之和target之后起始指针就向后持续移动缩小数组。所以关键在于while循环而非if的单次判断。 一些录友会疑惑为什么时间复杂度是O(n)。 不要以为for里放一个while就以为是O(n^2)啊 主要是看每一个元素被操作的次数每个元素在滑动窗后进来操作一次出去操作一次每个元素都是被操作两次所以时间复杂度是 2 × n 也就是O(n) 代码
class Solution1 {public int minSubArrayLen(int target, int[] nums) {int subLength Integer.MAX_VALUE;int sum 0;int beginIndex 0;int endIndex 0;for(;endIndexnums.length;endIndex){sumnums[endIndex];//终点指针持续向后移动while (sumtarget){subLength Math.min(subLength, endIndex - beginIndex 1);//更新最小长度sum - nums[beginIndex];//起始指针后移}}return subLength Integer.MAX_VALUE ? 0 : subLength;//若未赋值则返回0}
}
59.螺旋矩阵 题目链接 59. 螺旋矩阵 II - 力扣LeetCode 文章讲解代码随想录 视频讲解一入循环深似海 | LeetCode59.螺旋矩阵II_哔哩哔哩_bilibili 第一想法
没思路一碰到循环和二维数组就寄
代码随想录思路
确定圈数n/2因为每转一圈边长-2 n%21有余数的话最后一圈只要一个元素
每条边的处理都遵循左闭右开的原则第一个节点留给此边处理最后一个结点留给下一条边处理。 别人优化思路
1.关于中心元素处理其实可以在初始化res矩阵的时候就直接把全部元素初始化为n*n这样即使n是奇数也无需处理中间的元素
2.startx,starty,offset可以优化成一个变量处理。
代码
画了一下四个边角的坐标数组的边界处理这个offset变量还是很难把握
class Solution {public int[][] generateMatrix(int n) {int[][] result new int[n][n];//新建二维数组int loop 0;int startX 0, startY 0, offset 1;//起始X坐标起始Y坐标偏移量int count 1;while (loopn/2){int i startX, j startY;//先处理上边界for (j startY; j n - offset; j) {//j的最大值应该是倒数第二个元素jn-1-offset,即jn-offsetresult[startX][j] count;}//处理右边界for (i startX; i n - offset; i) {//此时j等于n-offsetresult[i][j]count;}//处理下边界for(;jstartY;j--){result[i][j]count;}//处理左边界for(;istartX;i--){result[i][j]count;}startX;startY;offset;loop;}if(n%21){result[startX][startY]count;}return result;}
}
