Re: [閒聊] 每日leetcode
看板Marginalman作者sustainer123 (caster )時間1年前 (2024/08/08 12:06)推噓0(0推 0噓 1→)留言1則, 1人參與討論串669/1548 (看更多)
※ 引述《smart0eddie (smart0eddie)》之銘言：
: 2024-08-08
: 885. Spiral Matrix III
: 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.
: 好像只能照著刻然後一格一格走塞進去欸?
: 在外面的時候可能可以用數學解跳過吧
: 可是感覺好麻煩
: 基本上蘿懸是從最小圈開始往前走一格以後轉彎
: 每轉彎兩次會碰到上一圈的 要多走一格
: class Solution {
: public:
: vector<vector<int>> spiralMatrixIII(int rows, int cols, int rStart, int
: cStart) {
: const vector<vector<int>> ds = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
: const int grids_number = rows * cols;
: vector<vector<int>> results;
: int max_step = 1;
: int dir = 0;
: int step = 0;
: int x = cStart, y = rStart;
: while (results.size() < grids_number) {
: if (isInside(x, y, rows, cols)) {
: results.push_back({y, x});
: }
: x += ds[dir][0];
: y += ds[dir][1];
: step++;
: if (step == max_step) {
: step = 0;
: dir = (dir + 1) % 4;
: if (!(dir % 2)) {
: max_step++;
: }
: }
: }
: return results;
: }
: private:
: inline bool isInside(const int x, const int y, const int rows, const int
: cols) {
: return x >=0 && x < cols && y >= 0 && y < rows;
: }
: };
思路:
順時鐘走就每走兩個方向就多走一步 11,22,33...... 以此類推
然後要走完整個矩陣 所以先算矩陣大小
後面就照著模擬 假如所在位子在矩陣範圍內 矩陣大小-1
最後矩陣大小歸零代表走完矩陣 回傳結果end
Python Code:
class Solution:
def spiralMatrixIII(self, rows: int, cols: int, rStart: int, cStart: int)
-> List[List[int]]:
dx = [1,0,-1,0]
dy = [0,1,0,-1]
result = [[rStart,cStart]]
total = (rows * cols)-1
direction = 0
time = 1
while total:
for _ in range(time):
cStart += dx[direction]
rStart += dy[direction]
if rStart >= 0 and cStart >= 0 and cStart < cols and rStart <
rows:
total -= 1
result.append([rStart,cStart])
if (direction % 2) == 1:
time += 1
direction = (direction + 1) % 4
return result
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.194.160.111 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723090016.A.41F.html
→
08/08 12:13,
1年前
, 1F
08/08 12:13, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 669 之 1548 篇)：