Stack and DFS
本文蒐集
LeetCode 200: Number of Islands
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
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: 1Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]is'0'or'1'.
我的解法
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
queue = []
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
self.dfs(grid, i, j)
count += 1
return count
def dfs(self, grid, i, j):
if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != '1':
return
grid[i][j] = '0'
self.dfs(grid, i+1, j)
self.dfs(grid, i-1, j)
self.dfs(grid, i, j+1)
self.dfs(grid, i, j-1)LeetCode 133: Clone Graph
Given a reference of a node in a connected undirected graph.
Return a deep copy (clone) of the graph.
Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.
class Node {
public int val;
public List<Node> neighbors;
}For simplicity sake, each node's value is the same as the node's index (1-indexed). For example, the first node with val = 1, the second node with val = 2, and so on. The graph is represented in the test case using an adjacency list.
Adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.
The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.
Example:
Constraints:
1 <= Node.val <= 100Node.valis unique for each node.- Number of Nodes will not exceed 100.
- There is no repeated edges and no self-loops in the graph.
- The Graph is connected and all nodes can be visited starting from the given node.
我的解法
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
if node is None:
return
self.nodes = [None] * 100
self.dfs(node)
for i, _ in enumerate(self.nodes):
if _ is not None:
return _
def dfs(self, node: 'Node') -> 'Node':
if self.nodes[node.val-1] is None:
n = Node(val = node.val)
self.nodes[node.val-1] = n
for i in node.neighbors:
self.dfs(i)
n.neighbors.append(self.nodes[i.val-1])
else:
returnLeetCode 494: Target Sum
You are given an integer array nums and an integer target.
You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.
For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1". Return the number of different expressions that you can build, which evaluates to target.
Example 1:
Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3Input: nums = [1], target = 1
Output: 1Constraints:
1 <= nums.length <= 200 <= nums[i] <= 10000 <= sum(nums[i]) <= 1000-1000 <= target <= 1000
我的解法 1
class Solution:
def findTargetSumWays(self, nums: List[int], S: int) -> int:
if nums is None:
return
if len(nums) == 1:
if nums[0] == 0 and S == 0:
return 2
elif nums[0] == abs(S):
return 1
else:
return 0
else:
n1 = self.findTargetSumWays(nums[:-1], S + nums[-1])
n2 = self.findTargetSumWays(nums[:-1], S - nums[-1])
return n1 + n2我的解法 2
利用 dict 字典紀錄搭配 list 兩層紀錄已計算過的資訊，但效率不好
class Solution:
def findTargetSumWays(self, nums: List[int], S: int) -> int:
self.arrived = [dict()]*len(nums)
print(self.arrived)
return self.dfs(nums, S)
def dfs(self, nums: List[int], S: int) -> int:
if len(nums) == 1:
if nums[0] == abs(S):
if S == 0:
self.arrived[0][S] = 2
return 2
else:
self.arrived[0][S] = 1
return 1
else:
self.arrived[0][S] = 0
return 0
else:
n1 = self.arrived[len(nums)-2].get(S-nums[-1], self.dfs(nums[:-1], S-nums[-1]))
n2 = self.arrived[len(nums)-2].get(S+nums[-1], self.dfs(nums[:-1], S+nums[-1]))
self.arrived[len(nums)-1][S] = n1 + n2
return n1 + n2我的解法 3
利用 @functools.cache 快取
可參考 docs
class Solution:
def findTargetSumWays(self, nums: List[int], S: int) -> int:
@functools.cache
def _findWays(idx, remaining):
if idx == len(nums):
return remaining == 0
return _findWays(idx+1, remaining-nums[idx]) + _findWays(idx+1, remaining+nums[idx])
return _findWays(0, S)我的解法 4
利用 dict 字典和 set 集合紀錄已計算過的資訊效率不錯
class Solution:
def findTargetSumWays(self, nums: List[int], S: int) -> int:
dp = {}
def dfs(i=0, total=0):
if i >= len(nums):
return 1 if total == S else 0
key = (i, total)
if key not in dp:
dp[key] = dfs(i+1, total+nums[i]) + dfs(i+1, total-nums[i])
return dp[key]
return dfs()LeetCode 94: Binary Tree Inorder Traversal
Given the root of a binary tree, return the inorder traversal of its nodes' values.
Example:
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Follow up:
Recursive solution is trivial, could you do it iteratively?
我的解法 1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
result = []
self.dfs(root, result)
return result
def dfs(self, root, r):
if root is None:
return
self.dfs(root.left, r)
r.append(root.val)
self.dfs(root.right, r)我的解法 2
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
if root is None:
return
result = []
stack = []
visited = set()
stack.append(root)
while stack:
curr = stack.pop()
if curr in visited:
result.append(curr.val)
else:
if curr.right:
stack.append(curr.right)
stack.append(curr)
visited.add(curr)
if curr.left:
stack.append(curr.left)
return result