自己紹介
初めまして。
本誌を訪問頂き有難うございます。
趣味で python を始めた中年おじさんです。
基礎から始めたくて記事を書き始めた今日この頃です。
本誌は基礎編 第四弾です。
第一弾 基礎編:木構造の全探索(DFS/BFS)
第二弾 基礎編:二分探索
第三弾 基礎編:再帰処理
全部わからなくてもいい。
気が向いたときに改めて向き合えば良いと思っているので
ゆるーく、やっていきます。
学習目標
今回は Leetcode:Queue & Stack の理解を目標とします。
どのように理解するかは、以下のアプローチで進めます。
テンプレートの暗記 =>
記述の理解(イメージ作成) =>
自分なりのアプローチで再検証 =>
理解の穴を埋める
試行錯誤を繰り返すことで理解が深まり、思考力が養われると思います。
例題 * Queue & BFS
上図のグラフ構造のデータを探索してみましょう!!
A から start して G に行ってみましょう!!
解説
まずはグラフ構造を作成し、
再帰処理で bfs を実現するケースと
Queue で bfs を実現するケースの 2 つを用意しました。
class node:
def __init__(self,name):
self.name = name
self.visit = False
self.adjust = []
def visit(node):
print(f"node:{node.name}")
node.visit = True
def recursive(node):
if not node:
return
visit(node)
for i in node.adjust:
if not i.visit:
recursive(i)
def queue(node):
q = [node]
while q:
nums = q.pop(0)
if not nums.visit:
visit(nums)
for i in nums.adjust:
q.append(i)
n_a = node("a")
n_b = node("b")
n_c = node("c")
n_d = node("d")
n_e = node("e")
n_f = node("f")
n_g = node("g")
n_a.adjust = [n_b,n_c,n_d]
n_b.adjust = [n_e]
n_c.adjust = [n_e,n_f]
n_d.adjust = [n_g]
n_f.adjust = [n_g]
#recursive(n_a)
queue(n_a)
node:a
node:b
node:c
node:d
node:e
node:f
node:g
演習 Walls and Gates
m x n の配列に初期値を代入して差し上げます。
初期値の意味は以下になります。
・-1 : 壁、もしくは障害物
・ 0 : 門
・Inf: 2^31 -1 = 2147483647 を Inf と定義し、空き部屋と同義
空き部屋には、最寄りの門からの距離を埋めてください。
もし、門に辿り着けない場合は INF を入れてください。
#Example1
Input: rooms = [
[2147483647,-1,0,2147483647],
[2147483647,2147483647,2147483647,-1],
[2147483647,-1,2147483647,-1],
[0,-1,2147483647,2147483647]]
Output: [
[3,-1,0,1],
[2,2,1,-1],
[1,-1,2,-1],
[0,-1,3,4]
]
#Example 2:
Input: rooms = [[-1]]
Output: [[-1]]
#Example 3:
Input: rooms = [[2147483647]]
Output: [[2147483647]]
#Example 4:
Input: rooms = [[0]]
Output: [[0]]
解説
過去に似たようなことをやっていたので
やりやすかったです。=> 過去の記事: 迷路に迷ってみた
class Solution():
def wallsAndGates(self, rooms):
"""
input: List[int][int]
rtype: List[int][int]
"""
m = len(rooms)
n = len(rooms[0])
if m == 0:
return rooms
#add all gates to a queue
queue = []
for i in range(m):
for j in range(n):
if rooms[i][j] == 0:
queue.append((i,j))
while queue:
row, col = queue.pop(0)
for i in range(4):
r,c = row + [1,0,-1,0][i],col+[0,1,0,-1][i]
if r < 0 or c < 0 or r >= m or c >= n or rooms[r][c] != 2147483647:
continue
rooms[r][c] = rooms[row][col] + 1
queue.append((r,c))
演習 Number of Islands
プレゼントした m x n の配列では 1 は陸、0 は水になりますので、島の数を返してください。
島とは水で囲まれており、1 を水平、垂直方向につながって形成されている物を指します。
枠の外は水で囲まれていると想定して oK です。
#Example 1:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
#Example 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
制約:
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.
解説
今回は障害物で囲まれていることを利用します。
つまり、1 である場合は、それを 0 に塗り替える。
塗り替えたら、上下左右も同じように塗り替える。
しかし、枠の制限を超えたり、もともと 0 であれば、
塗りつぶす作業が Stop します。
2 重 for 分で 1 である個所を探し、
前述の強制 stop が掛かる塗りつぶし作業を何回行ったか？
これが大陸の数になります。
class Solution():
def numIslands(self,grid):
islands = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == "1":
islands += 1
self.part_of_island(i,j,grid)
return islands
def part_of_island(self,i,j,grid):
if i < 0 or j < 0 or i == len(grid) or j == len(grid[0]) or grid[i][j] != "1":
return
else:
grid[i][j] = "0"
for k in range(4):
i,j = i+[1,0,-1,0][k],j+[0,1,0,-1][k]
self.part_of_island(i,j,grid)
演習 Open the Lock
図にあるように南京錠をプレゼントします。南京錠には 4 つのダイヤルがあり、
それぞれ'0', '1', '2', '3', '4', '5', '6', '7', '8', '9' の合計 10 個を設定できます。
各ダイヤルは自由に回して数字を設定できます。例えば、'9' から '0', '0' から '9' のように変えることが出来ます。
ダイヤルの初期値は "0000" です。
この "0000" は 4 つのダイヤルの文字を並べて構成されています。
注意点として、特定のコードになると、
ダイヤルを回すことが出来なくなり、鍵を開けることが出来なくなります。
target がカギを解除するコードになります。
鍵を開けるための最低何回ダイヤルを回す必要があるか教えて下さい。
開けられない場合は -1 を返してください。
#Example 1:
Input: deadends = ["0201","0101","0102","1212","2002"], target = "0202"
Output: 6
#Explanation:
#A sequence of valid moves would be "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202".
#Note that a sequence like "0000" -> "0001" -> "0002" -> "0102" -> "0202" would be invalid,
#because the wheels of the lock become stuck after the display becomes the dead end "0102".
#Example 2:
Input: deadends = ["8888"], target = "0009"
Output: 1
#Explanation:
#We can turn the last wheel in reverse to move from "0000" -> "0009".
#Example 3:
Input: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
Output: -1
#Explanation:
#We can't reach the target without getting stuck.
#Example 4:
Input: deadends = ["0000"], target = "8888"
Output: -1
解説
class Solution(object):
def openLock(self, deadends, target):
def neighbors(node):
for i in range(4):
x = int(node[i])
for d in (-1, 1):
y = (x + d) % 10
yield node[:i] + str(y) + node[i+1:]
dead = set(deadends)
queue = collections.deque([('0000', 0)])
seen = {'0000'}
while queue:
node, depth = queue.popleft()
if node == target: return depth #鍵が解除できれば return depth
if node in dead: continue #lock code に該当したら pass
for nei in neighbors(node): #neighbors を使って該当案をリスト
if nei not in seen: #過去に確認した記録がないことを確認
seen.add(nei) #確認したことを記録
queue.append((nei, depth+1)) #depth をインクリメント
#nei を buff して次回 neighbors に渡して案を作ってもらう
return -1
該当案の組み合わせをどうやって捻出するかを neighbor で
処理しているので切り出して動かしてみます。
def neighbor(node):
for i in range(4):
x = int(node[i])
for d in (-1,1):
y = (x+d)%10
yield node[:i] + str(y) + node[i+1:]
for i in neighbor("0000"):
print(i)
今回はテストで "0000" としていますが、
[0] ~ [3] を一つずつ取り出してある処理をします。
それは取り出したデータを (+1 or -1) %10 とします。
%10 としているのが味噌です。
これにより -1 % 10 = 9 , 1 %10 = 1 を
[0] ~ [3] に順番に代入していきます。
それが以下の実行結果です。
#実行結果
9000 #i = 0 , d = -1
1000 #i = 0 , d = 1
0900 #i = 1 , d = -1
0100 #i = 1 , d = 1
0090 #i = 2 , d = -1
0010 #i = 2 , d = 1
0009 #i = 3 , d = -1
0001 #i = 4 , d = 1
因みに yield に関しては以下のサイトが分かりやすかったです。
演習 Perfect Squares
整数 n をプレゼントしますので、正方形の総和で n となる最小の正方形の数を教えてください。
勿論、正方形は整数で 1,4,9,16... を意味しており、3 や 11 ではありません。
#Example 1:
Input: n = 12
Output: 3
#Explanation: 12 = 4 + 4 + 4.
#Example 2:
Input: n = 13
Output: 2
#Explanation: 13 = 4 + 9.
制約:
1 <= n <= 10^4
解説
class Solution:
def numSquares(self, n):
# list of square numbers that are less than `n`
square_nums = [i * i for i in range(1, int(n**0.5)+1)]
# if n = 4 , int(4**0.5)+1 = 3, squre_nums = [1,4]
# if n = 15, int(15**0.5)+1= 4, squre_nums = [1,4,9]
level = 0
queue = {n}
while queue:
level += 1
#! Important: use set() instead of list() to eliminate the redundancy,
# which would even provide a 5-times speedup, 200ms vs. 1000ms.
next_queue = set()
# construct the queue for the next level
for remainder in queue:
for square_num in square_nums:
if remainder == square_num:
return level # find the node!
elif remainder < square_num:
break
else:
next_queue.add(remainder - square_num)
queue = next_queue
return level
リストを使った以下の記述でも行ける気がするのですが、
time over となります。
class solution:
def numSquare(self,n):
base = [i*i for i in range(1,int(n**0.5)+1)]
q = [n]
level = 0
length = 0
while q:
level += 1
length = len(q)
for _ in range(length):
nums = q.pop(0)
for i in base:
if i == nums:
return level
elif i < nums:
q.append(nums-i)
set() の使い方を整理して list 以外の表記でも
理解できるようにしましょう。
演習 Min Stack
スタックがサポートしている push/pop/top を作ってみましょう。
・push(x) -- スタックにデータを push !!
・pop() -- スタックから top data を取り出します
・top() -- top data を確認
・getMin() -- スタックから最小値を取り出す
解説
class MinStack:
def __init__(self):
self.stack = []
def push(self, x: int) -> None:
if not self.stack:
self.stack.append((x,x))
return
current_min = self.stack[-1][1]
self.stack.append((x,min(x,current_min)))
def pop(self) -> None:
self.stack.pop()
def top(self) -> int:
return self.stack[-1][0]
def getMin(self) -> int:
return self.stack[-1][1]
演習 Valid Parentheses
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
#Example 1:
Input: s = "()"
Output: true
#Example 2:
Input: s = "()[]{}"
Output: true
#Example 3:
Input: s = "(]"
Output: false
#Example 4:
Input: s = "([)]"
Output: false
#Example 5:
Input: s = "{[]}"
Output: true
解説
#approach 1
class Solution:
def isValid(self, s: str) -> bool:
while "()" in s or "{}" in s or "[]" in s:
#左から順番に処理
# 1番目 ↓ 2番目 ↓ 3番目 ↓
s=s.replace("()","").replace("{}","").replace("[]","")
# "[{()}]"=> remove "()" =>
# "[{}]" => remove "{}" =>
# "[]" => remove "[]" => ""
return s == ""
#approach 2
def isValid(s):
maps = { ")":"(", "]":"[", "}":"{"}
q = []
for i in s:
if i in maps:
#if s = "]", q has no data to pop to top.
#in that case we have to output dummy data to reach the goal(to output False)
top = q.pop() if q else "#"
print(q,top)
if maps[i] != top:
return False
else:
q.append(i)
return not q
演習 Daily Temperatures
温度 T を daily で記録したリストを差し上げます。
そのリストを元に、何日待てば温度が上昇するか、各日を基準に考えたリストに直して返してください。
もし、今後、その日以上に温かくなることが見込まれない場合は 0 を入力してください。
例えば、 T = [73, 74, 75, 71, 69, 72, 76, 73] を与えられたとすると
output は [1, 1, 4, 2, 1, 1, 0, 0] になります。
メモ:温度は 1 以上 30000 以下とし、日数は 30 以上 100 以下とします。
解説
class Solution:
def dailyTemperatures(self, T):
ans = [0] * len(T)
stack = [] #indexes from hottest to coldest
for i in range(len(T) - 1, -1, -1):
while stack and T[i] >= T[stack[-1]]:
stack.pop()
if stack:
ans[i] = stack[-1] - i
stack.append(i)
return ans
GIF で追いかけてみました。
演習 Evaluate Reverse Polish Notation
逆ポーランド記法で算術表現を評価してください。
有効な演算子は +, -, *, / です。
Each operand may be an integer or another expression.
各オペランドは整数もしくは他の数式にすることが出来ます。
注意:
割り算は小数点以下は切り捨て。
#Example 1:
Input: ["2", "1", "+", "3", "*"]
Output: 9
#Explanation: ((2 + 1) * 3) = 9
#Example 2:
#Input: ["4", "13", "5", "/", "+"]
Output: 6
#Explanation: (4 + (13 / 5)) = 6
#Example 3:
Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
#Explanation:
# ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
#= ((10 * (6 / (12 * -11))) + 17) + 5
#= ((10 * (6 / -132)) + 17) + 5
#= ((10 * 0) + 17) + 5
#= (0 + 17) + 5
#= 17 + 5
解説
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
operations = {
"+": lambda a, b: a + b,
"-": lambda a, b: a - b,
"/": lambda a, b: int(a / b),
"*": lambda a, b: a * b
}
stack = []
for token in tokens:
if token in operations:
number_2 = stack.pop()
number_1 = stack.pop()
operation = operations[token]
stack.append(operation(number_1, number_2))
else:
stack.append(int(token))
return stack.pop()
今回は lambda の使い方と、その呼び出し方を勉強させてもらいました。
演算子を除いて、基本は append していきます。
演算子が出てきたら、pop を 2 回行って、演算を行います。
すばらしい!!勉強になりました。