代码随想录算法训练营第二天 |
您所在的位置：网站首页 › 矩阵画法 › 代码随想录算法训练营第二天 |
代码随想录算法训练营第二天
|
977.有序数组的平方
题目链接：力扣 文章讲解：代码随想录 视频讲解： 双指针法经典题目 | LeetCode：977.有序数组的平方_哔哩哔哩_bilibili 思路①：暴力法 package day2; import java.util.Arrays; public class Test1 { public static void main(String[] args) { int[] arr={-4,-1,0,3,10}; int[] squares = sortedSquares(arr); for (int i = 0; i < squares.length; i++) { System.out.println(squares[i]); } } public static int[] sortedSquares(int[] nums) { for (int i = 0; i < nums.length; i++) { nums[i]=nums[i]*nums[i]; } Arrays.sort(nums); return nums; } } 思路②：双指针法数组平方的最大值就在数组的两端，不是最左端就是最右端（分情况）
题目链接：力扣 文章讲解：代码随想录 视频讲解：拿下滑动窗口！ | LeetCode 209 长度最小的子数组_哔哩哔哩_bilibili 思路①：暴力法（会超出时间限制）设置两层for循环，一层for设置滑动窗口的其实位置，一层设置滑动窗口终止位置，用两个for循环完成一个不断搜索区间的过程 package day2; public class Test3 { public static void main(String[] args) { int[] arr={2,3,1,2,4,3}; int result = minSubArrayLen(7, arr); System.out.println(result); } public static int minSubArrayLen(int target, int[] nums) { int result=Integer.MAX_VALUE;//整型上限 int sum=0;//子序列的数值之和 int subLength=0;//子序列的长度 for (int i = 0; i < nums.length; i++) {//设置子序列起点为i sum=0; for (int j =i; j < nums.length; j++) {//设置子序列终止位置为j sum+=nums[j]; if(sum >= target){//一旦发现子序列和超过了target,更新result subLength=j-i+1;//取子序列的长度 result= result=s的长度最小的 连续子数组 如何确定窗口的起始位置如果当前窗口的值大于s了，窗口就要向前移动了 如何确定窗口的终止位置遍历数组的指针，也就是for循环的索引 package day2; public class Test4 { public static void main(String[] args) { int[] arr={2,3,1,2,4,3}; int minSubArrayLen = minSubArrayLen(7, arr); System.out.println(minSubArrayLen); } public static int minSubArrayLen(int target, int[] nums){ int result=Integer.MAX_VALUE; int sum=0; int subLength=0; int left=0; for (int right = 0; right < nums.length; right++) { sum+=nums[right]; while (sum>=target){ subLength=(right-left+1); result=Math.min(result,subLength); //不断变更i,子序列的起始位置 sum-=nums[left++]; } } return result==Integer.MAX_VALUE?0: result; } } 时间复杂度O(n)?主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素被操作两次，所以时间复杂度2*n也就是O（n） 59.螺旋矩阵题目链接：力扣 文章讲解：代码随想录 视频讲解：https://www.bilibili.com/video/BV1SL4y1N7mV/ 思路：在二分搜索中提到的区间定义 原则：循环不变量原则，模拟顺时针画矩阵的过程 填充上行从左至右 填充右列从上至下 填充下行从右至左 填充左列从下至上
每画一条边都要坚持一致的左闭右开，或者左开右闭的原则，这样一圈才能按照统一的规则画下来。拐角处理规则，拐角处让给新的一条边继续画。
if(n%2 == 1){ res[start][start]=count; } 意义？ eg:错误
✔：
package day2; import java.util.Scanner; public class Test5 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt();//行 int count=0; int[][] matrix = generateMatrix(n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { System.out.print(matrix[i][j]+" "); } System.out.println(); } } public static int[][] generateMatrix(int n) { int loop=0;//控制循环次数 int[][] res=new int[n][n]; int start=0;//每次循环的开始点，每一圈都要变 int count=1;//定义填充数字 int i,j; // while循环转几圈结束，如果是奇数的话，中间那个值不能被填充 while (loop++ < n/2){//判断边界后，loop从1开始 // 模拟上侧从左至右 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是奇数的话 if(n%2 == 1){ res[start][start]=count; } return res; } } 总结： 文章链接：代码随想录 |
【本文地址】