北京网站外包公司,无锡高端网站制作,商标网商标注册查询,室内设计培训多久977. 有序数组的平方 题目链接#xff1a;977. 有序数组的平方 文档讲解#xff1a;代码随想录 状态#xff1a;so easy 刚开始看到题目第一反应就是平方之后进行排序#xff0c;数据量在 1 0 4 10^4 104#xff0c;可以使用O(nlogn)的排序。但是更好的方式是使用双指针977. 有序数组的平方 文档讲解代码随想录 状态so easy 刚开始看到题目第一反应就是平方之后进行排序数据量在 1 0 4 10^4 104可以使用O(nlogn)的排序。但是更好的方式是使用双指针详见题解。
题解
双指针题解
public int[] sortedSquares(int[] nums) {// 初始化指向数组头和尾的指针int front 0, rear nums.length - 1;// 初始化结果数组的最后一个索引int index nums.length - 1;// 创建一个与输入数组长度相同的结果数组int[] res new int[nums.length];// 当头指针没有超过尾指针时继续循环while (front rear) {// 比较头指针和尾指针指向的数的平方大小if (nums[front] * nums[front] nums[rear] * nums[rear]) {// 如果头指针指向的数的平方较大则将其放入结果数组的当前索引位置res[index] nums[front] * nums[front];// 头指针向右移动一位front;} else {// 如果尾指针指向的数的平方较大或相等则将其放入结果数组的当前索引位置res[index] nums[rear] * nums[rear];// 尾指针向左移动一位rear--;}// 将结果数组的索引向左移动一位index--;}// 返回排序后的平方数组return res;
}
209. 长度最小的子数组 题目链接209. 长度最小的子数组 文档讲解代码随想录 状态so easy 思路因为是连续子数组所以可以考虑滑动窗口求和然后左右放缩找满足条件的最小长度。
题解
双指针题解
public int minSubArrayLen(int target, int[] nums) {// 初始化当前子数组的和int sum 0;// 初始化最小长度为一个很大的值int minLen Integer.MAX_VALUE;// 初始化两个指针i和ji为当前遍历到的数组位置j为子数组的起始位置for (int i 0, j 0; i nums.length; i) {// 将当前元素加入到子数组的和中sum nums[i];// 当子数组的和大于等于目标值时执行下面的循环while (sum target) {// 更新最小长度为当前子数组的长度minLen Math.min(minLen, i - j 1);// 将子数组起始位置的元素从和中减去然后将子数组的起始位置向右移动一位sum - nums[j];}}// 如果最小长度仍然为初始值说明没有找到满足条件的子数组返回0// 否则返回最小长度return minLen Integer.MAX_VALUE ? 0 : minLen;
}
59. 螺旋矩阵 II 题目链接59. 螺旋矩阵 II 文档讲解代码随想录 状态还行刚开始卡了一小会儿。 思路这个算法的目标是生成一个 n x n 的螺旋矩阵其中矩阵元素按顺时针方向依次递增。我们可以利用四个边界变量top、left、right、bottom来逐步收缩矩阵的边界并在每一步按顺时针方向填充矩阵。
题解
public int[][] generateMatrix(int n) {// 创建一个n x n的矩阵int[][] matrix new int[n][n];// 初始化填入矩阵的数字int num 1;// 初始化边界变量int top 0, left 0, right n - 1, bottom n - 1;// 当矩阵的上下边界和左右边界没有重叠时继续填充矩阵while (top bottom left right) {// 从左向右填充当前上边界所在行for (int i left; i right; i) {matrix[top][i] num;}// 上边界向下移动top;// 从上到下填充当前右边界所在列for (int i top; i bottom; i) {matrix[i][right] num;}// 右边界向左移动right--;// 确保当前下边界在上边界下方然后从右向左填充当前下边界所在行如果是m*n的矩阵这个不能少if (top bottom) {for (int i right; i left; i--) {matrix[bottom][i] num;}// 下边界向上移动bottom--;}// 确保当前左边界在右边界左方然后从下到上填充当前左边界所在列if (left right) {for (int i bottom; i top; i--) {matrix[i][left] num;}// 左边界向右移动left;}}// 返回填充好的矩阵return matrix;
}
拓展
类似螺旋矩阵题的核心思路是利用边界变量来逐步收缩图形的边界。解题步骤如下
初始化边界按要求进行模拟最外层的while循环 控制边界收缩的范围里面的for循环和边界变量的加加减减 模拟收缩过程 边界控制如果是m*n的矩阵还要注意边界变量的变化不能超出边界收缩的范围。
