こんにちは
今回の学びは
・ソートされた配列と二分木はよく似てるよ。
・できれば二分木探索を配列で実装していて 🙂
問題は。。。
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
まずは入出力をしっかりおさえましょう。
水のながれは高いところから低いとこへ（同じ高さも移動可能）
で、どのポイントから両端へつながるか？
という問題。
最初はブルートフォースで
O(4^(m+2))で果てしないのでダメ
graphっぽいことをかんがえて
特定のポイントから〜と＊の両方につながれば、オッケでしょ とかんがえる
枝刈りもできるし。それ以上いけなかったら。
dpも使えそう。
なんかスパイラルにループしていうのが効率的そう
dfsで[０＝なし、1＝〜、２＝＊、３＝〜 and *] みたいなenumにして行けそう。
その場合は
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は
O(m+n)でいけるはず。
ただし、その枡は４方のdpによるのだが、これが終わっているのかどうかの
判断がむずかしい
からり試行錯誤を重ねて、Wrongアンサーになるのがこちら
実際の実装はこちら
class Solution:
def pacificAtlantic(self, S: List[List[int]]) -> List[List[int]]:
m = len(S)
if m == 0: return []
n = len(S[0])
dp = [ [-1] * n for _ in range(m) ]
done = [ [0] * n for _ in range(m) ]
# -1, not visitted
# 0 = none, 1 = ~, 2 = *, 3 = ~ and *
def idx_valid(i, j):
if i < 0 or i >= m: return False
if j < 0 or j >= n: return False
return True
def dp_get(i, j, default=-1):
if idx_valid(i, j): return dp[i][j]
return default
def matrix_get(matrix, i, j, default=-1):
if idx_valid(i, j): return matrix[i][j]
return default
def print_matrix(matrix:List[List[int]]):
for row in matrix:
logging.debug(row)
def myself(i, j):
if not idx_valid(i, j): return -1
if (i == 0 or j == 0) and ((i == (m-1)) or (j == (n-1))): return 3
if ((i == (m-1)) or (j == (n-1))): return 2
if (i == 0 or j == 0): return 1
return 0
def dfs(i, j, parent=(-1, -1)):
logging.debug("dfs(%s, %s)" % (i, j))
if done[i][j] == 2: return dp[i][j] #調査済みならその結果を教えてやろう。
# 自分以下でかつ未踏の地であればdfs
done[i][j] = 1
me = myself(i, j)
if idx_valid(i, j-1) and S[i][j-1] <= S[i][j] and done[i][j-1] == 0: dfs(i, j-1, (i,j));
if idx_valid(i, j+1) and S[i][j+1] <= S[i][j] and done[i][j+1] == 0: dfs(i, j+1, (i,j));
if idx_valid(i-1, j) and S[i-1][j] <= S[i][j] and done[i-1][j] == 0: dfs(i-1, j, (i,j));
if idx_valid(i+1, j) and S[i+1][j] <= S[i][j] and done[i+1][j] == 0: dfs(i+1, j, (i,j));
l = dp_get(i, j-1)
r = dp_get(i, j+1)
u = dp_get(i-1, j)
b = dp_get(i+1, j)
surroundings = [l, r, u, b, me]
if idx_valid(parent[0], parent[1]):
if S[parent[0]][parent[1]] == S[i][j]:
surroundings.append(myself(parent[0], parent[1]))
if 1 in surroundings and 2 in surroundings:
dp[i][j] = 3
else:
dp[i][j] = max([0] + surroundings)
done[i][j] = 2
return dp[i][j]
ans = []
for i in range(m):
for j in range(n):
local = dfs(i, j)
if local >= 3:
ans.append([i, j])
logging.debug("---- dp ----")
print_matrix(dp)
logging.debug("---- S ----")
print_matrix(S)
logging.debug("---- done ----")
print_matrix(done)
return ans
十分格闘したので今回はソリューションンをみようと
おもいます。
こういう時は、すごく小さなバグだったりすることがほとんですが、
これを予め、予防する方法はなにかあるのでしょうか？
ログ出して、ソースビューして、テスト書けというようなことです。
実装後です。timespace analysis (時間とスペースの分析）は ◯◯
自分ではとけてないです。
この人は逆転の発想ですね。すばらしい、流れの低いところから高いとこへと登っていっています。これは、まずすばらしい。
わたしは、すべての点において、河口までいけるかのみしかかんがえていませんでした。それに逆転の思想ではでてきませんでした。
特に、もうすぐで解けそう、という時は頭をリセットしてあたらしい手法を感がつこうと思うのは難しいことです。が、これが高速に繰り返せる、メンタルと脳の思考体力とスピードと集中力を鍛えましょう。
まずは、１０分以上詰まったら、別の手法を思考するというよな自分ルールをもうけてもいいかもしれません。
といことで
（試行中 ）１０分以上詰まったら、別の手法を思考する
彼も答えから逆算の芋づるdfsです。逆転の発想です
いい名前だ、答えからの逆算芋づるdfs
ふむ〜、
これを見る限りパフォーマンスは考えなくて良よいのかと早合点しかけましたが、
いえ、O(n+m)*4なので、パフォーマンス出てますね。
~にたどりついたのか？という風にだけ考えて問題を簡素化するテクニックも
使えたことでしょう。
ちなみに、これといっているこれも逆算ですね。
逆から行かないと、自分のパスの通過点が最終的に海に到達できるか否かの判断が難しいです。実際わたしはそれが実装できませんでした。複雑になります。
それが、逆から考えると一気に消えます。マジックです。これ。あらためて。
これらのを踏まえて一度
自分でも実装しなおしたいと思います。
実装はこちら
答えのヒント、もしくは答えがわかっていても、テストパスするのに30分くらいかかりました。
dfs(i, 0, visited)とか何をあたえるのか。がバグで駆除に時間を割いた
neighbours関数は単体テストできるので、やはり小分けにするのは吉である
class Solution:
"""
へー、一回こたえ、
他の人のソリューションをみましたので、それをふまえて再実装といきやす
自分の考えに近かった。そして自分は実装しきれなかった
アトランティスとパシフィックをにそれぞれ到達したかを確認する
アルゴリズムで行ってみます
"""
def pacificAtlantic(self, S: List[List[int]]) -> List[List[int]]:
m = len(S)
if m == 0: return []
n = len(S[0])
def print_matrix(matrix:List[List[int]]):
for row in matrix:
logging.debug(row)
# inspired from https://leetcode.com/problems/pacific-atlantic-water-flow/discuss/365921/Search-in-Python
# def neighbours(i, j):
# directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
# nbs = []
# for arrow in directions:
# x, y = arrow
# if 0 <= i+x < n:
# if 0 <= j+y < m:
# nbs.append((i+x, j+y))
# return nbs
def neighbours(i, j):
return [
(i + a, j + b)
for (a, b) in [(-1, 0), (1, 0), (0, -1), (0, 1)]
if 0 <= i + a < m
if 0 <= j + b < n
]
def dfs(i, j, visited):
logging.debug("dfs(%s, %s, visited)" % (i, j))
if visited[i][j]: return
visited[i][j] = True
nbs = neighbours(i, j)
logging.debug("neighbors(i:%s, j:%s) => %s" % (i, j, nbs))
for r, c in nbs:
logging.debug("r:%s, c:%s, i:%s, j:%s" % (r, c, i, j))
if S[r][c] >= S[i][j]:
dfs(r, c, visited)
ans = []
pacific = [[False] * n for _ in range(m)]
atlantic = [[False] * n for _ in range(m)]
for i in range(m):
dfs(i, 0, pacific)
dfs(i, n-1, atlantic)
for j in range(n):
dfs(0, j, pacific)
dfs(m-1, j, atlantic)
for i in range(m):
for j in range(n):
if pacific[i][j] and atlantic[i][j]:
ans.append((i, j))
logging.debug("---- pacific ----")
print_matrix(pacific)
logging.debug("---- atlantic ----")
print_matrix(atlantic)
logging.debug("---- S ----")
print_matrix(S)
return ans
まとめ
・（試行中 ）１０分以上詰まったら、別の手法を思考する
・いい名前だ、答えからの逆算芋づるdfs
・問題の簡素化
以上です