北京哪里制作网站,谷歌三件套,室内设计小白怎么入行,网站推广代运营LCR 146.螺旋遍历二维数组 给定一个二维数组 array#xff0c;请返回「螺旋遍历」该数组的结果。 螺旋遍历#xff1a;从左上角开始#xff0c;按照 向右、向下、向左、向上 的顺序 依次 提取元素#xff0c;然后再进入内部一层重复相同的步骤#xff0c;直到提取完所有元…LCR 146.螺旋遍历二维数组 给定一个二维数组 array请返回「螺旋遍历」该数组的结果。 螺旋遍历从左上角开始按照 向右、向下、向左、向上 的顺序 依次 提取元素然后再进入内部一层重复相同的步骤直到提取完所有元素。 示例 1 输入array [[1,2,3],[8,9,4],[7,6,5]]
输出[1,2,3,4,5,6,7,8,9]示例 2 输入array [[1,2,3,4],[12,13,14,5],[11,16,15,6],[10,9,8,7]]
输出[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]限制 0 array.length 1000 array[i].length 100 原理 初始化边界 north, south, east, west 分别表示二维数组的上、下、右、左边界。开始时north 0, south array.length - 1, east array[0].length - 1, west 0即全覆盖数组的外边界。 螺旋遍历 螺旋遍历从左上角north, west开始顺时针按“右、下、左、上”的顺序遍历二维数组。 第一步 从左到右遍历即遍历当前的北边界行。 第二步 从上到下遍历即遍历当前的东边界列。 第三步 从右到左遍历即遍历当前的南边界行。 第四步 从下到上遍历即遍历当前的西边界列。 每一轮螺旋遍历后都会减少遍历区域的边界 north上边界下移west左边界右移south--下边界上移east--右边界左移这样每完成一圈遍历内层的元素逐步被收录直到所有元素都被遍历完。 终止条件 当 sum剩余未遍历元素的数量为 0 时表示所有元素都已被访问完跳出循环。 返回结果 最终list 数组包含了螺旋遍历的所有元素按顺序返回。 时间复杂度 假设数组的维度是 m x n遍历所有元素的时间复杂度是 O(m * n)因为每个元素都只会被访问一次。 空间复杂度 空间复杂度为 O(m * n)因为需要一个大小为 m * n 的数组来存储遍历的结果。 代码
class Solution {public int[] spiralArray(int[][] array) {// 获取二维数组的行数即南边界int south array.length - 1; // 如果数组没有行直接返回空数组if (south -1) {return new int[0];}// 获取二维数组的列数即东边界int east array[0].length - 1; // 如果数组没有列直接返回空数组if (east -1) {return new int[0];}// 计算二维数组中的总元素个数决定返回数组的大小int sum (south 1) * (east 1); // 初始化边界int north 0, west 0;// 创建存储结果的数组int[] list new int[sum];// count 用来记录当前插入的位置int count 0;// 开始螺旋遍历while (sum 0) {// 从左到右遍历沿着北边界for (int i west; i east; i) {list[count] array[north][i]; // 将当前元素加入结果数组sum--; // 每遍历一个元素减去一个}// 如果所有元素已经遍历完跳出循环if (sum 0) {break;}// 从上到下遍历沿着东边界for (int i north 1; i south; i) {list[count] array[i][east]; // 将当前元素加入结果数组sum--; // 每遍历一个元素减去一个}// 如果所有元素已经遍历完跳出循环if (sum 0) {break;}// 从右到左遍历沿着南边界for (int i east - 1; i west; i--) {list[count] array[south][i]; // 将当前元素加入结果数组sum--; // 每遍历一个元素减去一个}// 如果所有元素已经遍历完跳出循环if (sum 0) {break;}// 从下到上遍历沿着西边界for (int i south - 1; i north; i--) {list[count] array[i][west]; // 将当前元素加入结果数组sum--; // 每遍历一个元素减去一个}// 更新边界进入内层north;west;south--;east--;}// 返回螺旋遍历的结果return list;}
}54.螺旋矩阵 给你一个 m 行 n 列的矩阵 matrix 请按照 顺时针螺旋顺序 返回矩阵中的所有元素。 示例 1 输入matrix [[1,2,3],[4,5,6],[7,8,9]]
输出[1,2,3,6,9,8,7,4,5]示例 2 输入matrix [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出[1,2,3,4,8,12,11,10,9,5,6,7]提示 m matrix.lengthn matrix[i].length1 m, n 10-100 matrix[i][j] 100 原理 初始化边界 north, south, east, west 分别表示二维数组的上、下、右、左边界。开始时north 0, south matrix.length - 1, east matrix[0].length - 1, west 0即全覆盖矩阵的外边界。 螺旋遍历 螺旋遍历从左上角north, west开始顺时针按“右、下、左、上”的顺序遍历二维矩阵中的元素。 第一步 从左到右遍历即遍历当前的北边界行。 第二步 从上到下遍历即遍历当前的东边界列。 第三步 从右到左遍历即遍历当前的南边界行。 第四步 从下到上遍历即遍历当前的西边界列。 每完成一圈螺旋遍历后都会更新边界 north上边界下移west左边界右移south--下边界上移east--右边界左移这样每完成一圈遍历内层的元素逐步被收录直到所有元素都被遍历完。 终止条件 当 sum剩余未遍历元素的数量为 0 时表示所有元素都已被访问完跳出循环。 返回结果 最终list 列表包含了矩阵的螺旋顺序遍历结果按顺序返回。 时间复杂度 假设矩阵的维度是 m x n遍历所有元素的时间复杂度是 O(m * n)因为每个元素只会被访问一次。 空间复杂度 空间复杂度为 O(m * n)因为需要一个大小为 m * n 的列表来存储遍历的结果。 代码
class Solution {public ListInteger spiralOrder(int[][] matrix) {// 获取矩阵的南边界即最后一行的索引int south matrix.length - 1;// 获取矩阵的东边界即最后一列的索引int east matrix[0].length - 1;// 计算矩阵中元素的总数int sum (south 1) * (east 1);// 初始化边界north 是上边界west 是左边界int north 0, west 0;// 用一个列表来存储螺旋遍历的结果ListInteger list new ArrayList(south * east);// 螺旋遍历开始直到所有元素都被访问while (sum 0) {// 1. 从左向右遍历沿着北边界for (int i west; i east; i) {list.add(matrix[north][i]); // 将当前元素加入结果列表sum--; // 减少未访问的元素数目}// 如果所有元素已经遍历完退出循环if (sum 0) {break;}// 2. 从上到下遍历沿着东边界for (int i north 1; i south; i) {list.add(matrix[i][east]); // 将当前元素加入结果列表sum--; // 减少未访问的元素数目}// 如果所有元素已经遍历完退出循环if (sum 0) {break;}// 3. 从右向左遍历沿着南边界for (int i east - 1; i west; i--) {list.add(matrix[south][i]); // 将当前元素加入结果列表sum--; // 减少未访问的元素数目}// 如果所有元素已经遍历完退出循环if (sum 0) {break;}// 4. 从下到上遍历沿着西边界for (int i south - 1; i north; i--) {list.add(matrix[i][west]); // 将当前元素加入结果列表sum--; // 减少未访问的元素数目}// 更新边界进入内层north; // 上边界下移west; // 左边界右移south--; // 下边界上移east--; // 右边界左移}// 返回螺旋遍历的结果return list;}
}59.螺旋矩阵II 给你一个正整数 n 生成一个包含 1 到 n2 所有元素且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 示例 1 输入n 3
输出[[1,2,3],[8,9,4],[7,6,5]]示例 2 输入n 1
输出[[1]]提示 1 n 20 原理 初始化 我们首先创建一个大小为 n x n 的矩阵 ans。用 sum 变量记录当前要填充的数字从 1 开始递增。使用 row 和 column 变量来指示当前的矩阵填充位置。 螺旋顺序填充 每一圈的填充包括四个方向向右、向下、向左、向上依次填充矩阵的边界。向右 从当前的 (row, column) 开始向右填充 n 个位置。向下 在完成右边的填充后向下填充 n-1 个位置。向左 完成下边的填充后向左填充 n-2 个位置。向上 完成左边的填充后向上填充 n-3 个位置。每次一圈填充后更新边界将 n 减少 2以保证下一圈填充在内层矩阵中进行。 边界收缩 每次完成一圈的填充后column 将列向右移动准备进行下次填充。同时 n - 2表示当前有效矩阵的边长减少 2从而让填充继续进行到内层。 终止条件 当 n 0 时表示已经填充完所有的元素退出循环并返回结果矩阵。 时间复杂度 假设矩阵的大小为 n x n所有元素都需要被遍历一次并填充。因此时间复杂度为 O(n²)。 空间复杂度 需要一个 n x n 的矩阵来存储结果因此空间复杂度为 O(n²)。 代码
class Solution {public int[][] generateMatrix(int n) {// 初始化一个 n x n 的矩阵int[][] ans new int[n][n];// sum 用来记录当前填充的数字初始为 1int sum 1;// row 和 column 用来记录当前要填充的位置的行和列int row 0, column 0;// 只要 n 0就继续填充while (n 0) {// 1. 从左到右填充当前的北边界for (int i 0; i n; i) {ans[row][column] sum; // 填充当前元素并将列加 1}// 向左回退一列因为 column 会使列超出范围column - 1;// 2. 从上到下填充当前的东边界for (int i 0; i n - 1; i) {ans[row][column] sum; // 填充当前元素并将行加 1}// 3. 从右到左填充当前的南边界for (int i n - 2; i 0; i--) {ans[row][--column] sum; // 填充当前元素并将列减 1}// 4. 从下到上填充当前的西边界for (int i n - 2; i 0; i--) {ans[--row][column] sum; // 填充当前元素并将行减 1}// 回到上边界的下一列并且减少矩阵的规模边界收缩column;n - 2; // 每一圈填充完成后矩阵的有效边长减少 2}// 返回生成的矩阵return ans;}
}
