首页 > 其他分享 >[LeetCode] 885. Spiral Matrix III

[LeetCode] 885. Spiral Matrix III

时间:2024-09-14 14:51:21浏览次数:13  
标签:rows Matrix int cols 网格 grid rStart III LeetCode

You start at the cell (rStart, cStart) of an rows x cols grid facing east. The northwest corner is at the first row and column in the grid, and the southeast corner is at the last row and column.

You will walk in a clockwise spiral shape to visit every position in this grid. Whenever you move outside the grid's boundary, we continue our walk outside the grid (but may return to the grid boundary later.). Eventually, we reach all rows * cols spaces of the grid.

Return an array of coordinates representing the positions of the grid in the order you visited them.

Example 1:
Example 1
Input: rows = 1, cols = 4, rStart = 0, cStart = 0
Output: [[0,0],[0,1],[0,2],[0,3]]

Example 2:
Example 2
Input: rows = 5, cols = 6, rStart = 1, cStart = 4
Output: [[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

Constraints:
1 <= rows, cols <= 100
0 <= rStart < rows
0 <= cStart < cols

螺旋矩阵 III。

在 rows x cols 的网格上,你从单元格 (rStart, cStart) 面朝东面开始。网格的西北角位于第一行第一列,网格的东南角位于最后一行最后一列。

你需要以顺时针按螺旋状行走,访问此网格中的每个位置。每当移动到网格的边界之外时,需要继续在网格之外行走(但稍后可能会返回到网格边界)。

最终,我们到过网格的所有 rows x cols 个空间。

按照访问顺序返回表示网格位置的坐标列表。

思路

这道题题意不难理解,但是有一个不太直观的地方是,我们在螺旋行走的时候,每一个方向到底走几步就可以换方向了。

复杂度

时间O(rc)
空间O(r
c)

代码

Java实现

class Solution {
    public int[][] spiralMatrixIII(int rows, int cols, int rStart, int cStart) {
        int[][] res = new int[rows * cols][2];
        int index = 0;
        res[index++] = new int[] { rStart, cStart };

        // directions, right, down, left, up
        int[][] dirs = new int[][] { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
        // 步长
        int step = 1;

        int r = rStart;
        int c = cStart;
        while (index < rows * cols) {
            for (int i = 0; i < 4; i++) {
                int[] dir = dirs[i];
                for (int j = 0; j < step; j++) {
                    r += dir[0];
                    c += dir[1];
                    // 如果这个坐标在结果集的范围内,则把这个坐标加入结果集
                    if (r >= 0 && r < rows && c >= 0 && c < cols) {
                        res[index++] = new int[] { r, c };
                    }
                }
                // 往左走和往右走的时候,步长要+1
                if (i == 1 || i == 3) {
                    step++;
                }
            }
        }
        return res;
    }
}

标签:rows,Matrix,int,cols,网格,grid,rStart,III,LeetCode
From: https://www.cnblogs.com/cnoodle/p/18413974

相关文章

  • 【LeetCode Hot 100】3. 无重复字符的最长子串
    题目描述本题我最开始的想法就是使用双指针与滑动窗口,滑动过程中维护一个集合,集合内保存滑动窗口内部的所有字符,右边的指针每指向一个新的元素,就判断该元素(字符)是否在集合内,如果已经存在,就说明此时将要出现重复字符,以及无重复字符的子串已经达到了最长的长度,之后我们需要移动左边......
  • LeetCode 2390. 从字符串中移除星号(字符串、栈)
    题目:2390.从字符串中移除星号思路:使用栈就可以,这里string也可以实现栈的效果classSolution{public:stringremoveStars(strings){stringe="";for(autox:s){if(x=='*')e.pop_back();elsee.push_back(x);......
  • 【LeetCode 算法笔记】49. 字母异位词分组
    目录问题描述计数法:计数法(用哈希表):排序法:问题描述给你一个字符串数组,请你将字母异位词组合在一起。可以按任意顺序返回结果列表。字母异位词是由重新排列源单词的所有字母得到的一个新单词。示例1:输入:strs=[“eat”,“tea”,“tan”,“ate”,“nat”......
  • 【随想录day2】LeetCode209长度最小的子数组 | LeetCode59螺旋矩阵
    LeetCode209长度最小的子数组1、题目:给定一个含有n个正整数的数组和一个正整数s,找出该数组中满足其和≥s的长度最小的连续子数组,并返回其长度。如果不存在符合条件的子数组,返回0示例:输入:s=7,nums=[2,3,1,2,4,3]输出:2解释:子数组[4,3]是该条件下的长度最小......
  • (nice!!!)LeetCode 2398. 预算内的最多机器人数目(队列、滑动窗口)
    题目:2398.预算内的最多机器人数目思路:双端队列+滑动窗口。因为需要找连续的机器人,这里就需要用到滑动窗口。细节看注释,时间复杂度0(n)。classSolution{public:intmaximumRobots(vector<int>&chargeTimes,vector<int>&runningCosts,longlongbudget){......
  • 【LeetCode Hot 100】2. 两数相加
    题目描述题目手下留情给出的链表使用逆序表示加数,因此我们可以从链表头开始逐位相加。我总结了一下有几点需要注意:显然加法需要注意进位,此外需要格外注意的是最后一位没有加数时,还需要考虑进位是否被置位,如果最后的进位为1,我们还需要创建一个新的节点。当其中一个链表走完,需要......
  • 【每日一题】LeetCode 2398.预算内的最多机器人数目(滑动窗口、数组、二分查找、前缀和
    【每日一题】LeetCode2398.预算内的最多机器人数目(滑动窗口、数组、二分查找、前缀和、堆(优先队列))题目描述给定两个整数数组chargeTimes和runningCosts,分别代表n个机器人的充电时间和运行成本。再给定一个整数budget,表示预算。我们需要计算在不超过预算的情况下,最......
  • leetcode刷题day17|二叉树Part05(654.最大二叉树、617.合并二叉树、700.二叉搜索树中的
    654.最大二叉树构造树一般采用的是前序遍历,因为先构造中间节点,然后递归构造左子树和右子树。递归三步曲:1、传入参数,整数数组,数组的开始和结束,返回树的中间节点。2、终止条件:开始大于等于结束,即数组为空。3、递归逻辑:找到最大的元素,记录元素其下标,构建中间节点;递归构造......
  • LeetCode算法—分治法
    思路:分治法的核心思想是“分而治之”,即将一个复杂的问题分成多个较小的子问题,分别求解这些子问题,然后将子问题的解合并,得到原问题的解。具体到求众数的问题上,分治法通过递归地将数组分成两部分,分别找出每一部分的众数,最后通过合并步骤来确定整个数组的众数。LeetCode169多数元素......
  • LeetCode 692.前K个高频单词
    LeetCode692.前K个高频单词C++思路......