作者benchen0812 (あBen)
看板Python
標題[問題] 想請問leetcode694和inner func相關問題
時間Wed Mar 27 12:52:48 2019
Hi all,
今天刷到一題
leetcode694 題目是
Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's
(representing land) connected 4-directionally (horizontal or vertical.) You
may assume all four edges of the grid are surrounded by water.
Count the number of distinct islands. An island is considered to be the same
as another if and only if one island can be translated (and not rotated or
reflected) to equal the other.
先附上我的寫法還有解答
https://imgur.com/fnrJUsG
然後error message
https://imgur.com/ycaClM6
這邊想請問的是
我看我的寫法和解答的寫法除了他用inner
然後我的function 是define 在class 底下之外 應該是沒有什麼太大差別
(如果有錯誤請幫我指證謝謝)
這邊想請問的是 如果我是用inner function 做recursion
請問function return address是不是也是存在stack
如果是的話 想請問一下為什麼我的寫法會max recursion depth exceeded?
但是他的寫法卻可以過?
兩種recursion depth 應該要一樣不是?
謝謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 174.55.55.170
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Python/M.1553662373.A.46E.html
1F：推 lemon651: 你有發現你跟解答的終止條件不一樣嗎？第一長寬應該是< 03/27 17:38
2F：→ lemon651: 不是<= 不過這不影響max depth，第二你把grid[x][y]看過 03/27 17:38
3F：→ lemon651: 的沒有紀錄起來也沒有轉成能當False的東西 等於你的每一 03/27 17:38
4F：→ lemon651: 層都會互相調用，肯定爆棧，舉個例你11 從左邊的往右邊d 03/27 17:38
5F：→ lemon651: fs 右邊的又往左dfs 等於這個遞歸完全不會終止 03/27 17:38
6F：推 lemon651: 你給的解答 用了seen紀錄過走過的點 並用一個set紀錄形 03/27 17:42
7F：→ lemon651: 狀 這題因為空間複雜度最差還是m * n所以用一個set紀錄 03/27 17:42
8F：→ lemon651: 走過的點不影響空間複雜度 03/27 17:43
阿我發現我是要讓 grid[x][y] = 0...
感謝! 沒想到犯了這麼蠢的問題ORZ
※ 編輯: benchen0812 (174.55.55.170), 03/27/2019 22:35:11
9F：推 lemon651: 我是建議你不要讓他等於0啦 這樣你走完一遍就把整個inpu 03/28 12:40
10F：→ lemon651: t改變了 而且還不可逆 03/28 12:40