潍坊网站建设公司排名,企业网站 生成html,在线文档网站源码,聊城汽车网站建设算法题
Leetcode 977.有序数组的平方
题目链接: 977.有序数组的平方
大佬视频讲解#xff1a;977.有序数组的平方 个人思路
第一时间就只想到暴力解法#xff0c;双重循环一个循环比较一个循环赋值#xff1b;但这样可能会超时#xff0c;所以还能用双指针#xff0… 算法题
Leetcode 977.有序数组的平方
题目链接: 977.有序数组的平方
大佬视频讲解977.有序数组的平方 个人思路
第一时间就只想到暴力解法双重循环一个循环比较一个循环赋值但这样可能会超时所以还能用双指针因为这个数组是递增数组也就是说平方后最大的值只能在两边那么前后各一个指针比较其值再根据大小放进新的数组中就能解决这也是空间换时间的方法 解法
暴力解法
循环赋值然后排序
class Solution {public int[] sortedSquares(int[] nums) {for(int i0;inums.length;i){//暴力循环求值nums[i]*nums[i];}Arrays.sort(nums);//排序return nums;}
}
时间复杂度:O(nlog n)一个for循环为n再加上排序的nlogn和为nnlogn 取最大的时间复杂度即为nlogn
空间复杂度:O(1);没有使用多余空间 双指针
left指向起始位置right指向终止位置。定义一个新数组newNums和A数组一样的大小根据平方的大小来从数组newNums后往前赋值。
class Solution {public int[] sortedSquares(int[] nums) {int lennums.length;//数组的长度int left0; int rightlen-1;//双指针int[] newNumsnew int[len];//新数组int indexlen-1;//新数组赋值的指针while(leftright){if (nums[left] * nums[left] nums[right] * nums[right]) {newNums[index]nums[left]*nums[left];//新数组赋值index--;//新数组指针往前移left;//起始指针往前移}else{newNums[index]nums[right]*nums[right];//新数组赋值index--;--right;//结尾指针往后移}}return newNums;}
}
时间复杂度:O(n)最糟糕的可能就是把数组全遍历一遍因此为On
空间复杂度:O(n);使用多一个数组存值 Leetcode 209.长度最小的子数组
题目链接:209.长度最小的子数组
大佬视频讲解209.长度最小的子数组视频讲解 个人思路
一开始又想到暴力解法但这样明显会超时然后...就没思路了。之前刷过好几次滑动窗口还是想不起来菜得多练呀/无奈 解法
滑动窗口
滑动窗口就是不断的调节子序列的起始位置和终止位置
其中主要确定如下三点
窗口的定义窗口就是 满足其和 ≥ target 的长度最小的 连续 子数组。窗口的起始位置如何移动如果当前窗口的值大于target 了窗口就要向前移动了也就是该缩小了。窗口的结束位置如何移动窗口的结束位置就是遍历数组的指针也就是for循环里的索引。
如果还是比较抽象建议看看视频209.长度最小的子数组视频讲解
class Solution {public int minSubArrayLen(int target, int[] nums) {//暴力解法从头开始遍历计算达到目标值的张最小连续数组即可这样会超时int start0;//滑动窗口的起始位置int sum0;//滑动窗口的和int answerInteger.MAX_VALUE;//结果数组长度for(int end0;endnums.length;end){//滑动窗口的结束位置sumnums[end];while(sumtarget){answerMath.min(answer,end-start1);//用当前滑动窗口的长度与之前长度对比sum-nums[start];//不断变更start子序列的起始位置}}return answerInteger.MAX_VALUE ? 0:answer;// 如果说明没有符合条件的子序列,即answer没有被赋值的话就返回0}
}
时间复杂度:O(n)一个 for循环加上一个while没有嵌套所以是nn2n
空间复杂度:O(1);没有使用多余空间 Leetcode 59.螺旋矩阵II
题目链接:59.螺旋矩阵II
大佬视频讲解59.螺旋矩阵II视频讲解 个人思路
这道题之前做过没怎么搞懂只记得是找规律那先画图看看画一个n为4和5的数组螺旋循环后发现规律如下有四个方向赋值这四个方向的赋值数量刚刚开始都是n-1如果n为奇数则会剩下中间的值没有赋值循环次数正好是n/2根据这些规律怎么写代码也是个难题还得多练 解法
找规律
顺时针画矩阵的过程:
上行从左到右填充数据右列从上到下填充数据下行从右到左填充数据左列从下到上填充数据
由外向内一圈一圈这么画下去。可以发现这里的边界条件非常多在一个循环中如此多的边界条件得按照固定规则来遍历每画一条边都要坚持一致的左闭右开或者左开右闭的原则这样这一圈才能按照统一的规则画下来。
下面的是按照左闭右开规则
class Solution {public int[][] generateMatrix(int n) {int loop 0; // 控制循环次数int start 0; // 每次循环的开始点(start, start)int count 1; // 定义填充数字int[][] res new int[n][n];//结果数组int i, j;while (loop n / 2) { // 先判断边界后再自增1以此循环(n-loop)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[start][start] count;}return res;}
}
时间复杂度:O(n^2)模拟遍历二维矩阵的时间
空间复杂度:O(1);没有使用多余空间 以上是个人的思考反思与总结若只想根据系列题刷参考卡哥的网址代码随想录算法官网
