1020. The number of enclaves
Give you a size of m x n The binary matrix of grid , among 0 Represents an ocean cell 、1 Represents a land cell .
once Move It refers to walking from one land cell to another （ On 、 Next 、 Left 、 Right ） Land cells or across grid The boundary of the .
Return to grid unable The number of land cells that leave the grid boundary in any number of moves .
Example 1：
Input ：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]] Output ：3 explain ： There are three 1 By 0 Surround . One 1 Not surrounded , Because it's on the border .
Example 2：
Input ：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]] Output ：0 explain ： all 1 Are on the boundary or can reach the boundary .
Tips ：
m == grid.lengthn == grid[i].length1 <= m, n <= 500grid[i][j] The value of is 0 or 1from collections import deque
from typing import List
# dfs
class Solution:
def numEnclaves(self, grid: List[List[int]]) -> int:
row, colomn = len(grid), len(grid[0])
visit = [[False]*colomn for _ in range(row)]
def dfs(i, j):
if i >= 0 and i <= row-1 and j >=0 and j<=colomn-1 and grid[i][j] and not visit[i][j]:
visit[i][j] = True
for x, y in ((i-1, j), (i+1, j), (i, j-1), (i, j+1)):
dfs(x, y)
else:
return
for i in range(row):
dfs(i, 0)
dfs(i, colomn-1)
for j in range(1, colomn-1):
dfs(0, j)
dfs(row-1, j)
return sum(grid[i][j] if not visit[i][j] else 0 for i in range(row) for j in range(colomn))
# The official caption reads like this , Be careful sum You can operate on Boolean types
# return sum(grid[i][j] and not vis[i][j] for i in range(1, m - 1) for j in range(1, n - 1))
# official dfs
class Solution:
def numEnclaves(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
vis = [[False] * n for _ in range(m)]
def dfs(r: int, c: int) -> None:
if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == 0 or vis[r][c]:
return
vis[r][c] = True
for x, y in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
dfs(x, y)
for i in range(m):
dfs(i, 0)
dfs(i, n - 1)
for j in range(1, n - 1):
dfs(0, j)
dfs(m - 1, j)
return sum(grid[i][j] and not vis[i][j] for i in range(1, m - 1) for j in range(1, n - 1))
# tip: sum Function can be used for bool Type to operate
a = (2==1 and not 3==1 for _ in range(10))
print([x for x in a])
print (sum([False, False]))
# bfs
class Solution:
def numEnclaves(self, grid: List[List[int]]) -> int:
row, colomn = len(grid), len(grid[0])
visit = [[False]*colomn for _ in range(row)] # dfs and bfs The key to
d = deque()
for i in range(row):
for j in range(colomn):
if i == 0 or j == 0 or i == row-1 or j == colomn-1:
if grid[i][j] == 1 and not visit[i][j]:
visit[i][j] = True
d.append((i, j))
while d: # Pay attention to this while The loop cannot be written in this if below （ The results are different ）, I don't know why , Pay attention next time , First put all the things to be traversed into the queue
i, j = d.popleft()
for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
if x >= 0 and x <= row - 1 and y >= 0 and y <= colomn - 1 and not visit[x][y] and grid[x][y]:
d.append((x, y))
visit[x][y] = True
return sum(grid[i][j] and not visit[i][j] for i in range(1, row-1) for j in range(1, colomn-1))Be careful ：dfs Corresponding to three kinds of recursive traversal of binary tree ,bfs Corresponding sequence traversal
113. The sum of the paths II
Give you the root node of the binary tree root And an integer target and targetSum , Find out all From the root node to the leaf node The path sum is equal to the given target sum .
Leaf node A node without children .
Example 1：
Input ：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 Output ：[[5,4,11,2],[5,8,4,5]]
Example 2：
Input ：root = [1,2,3], targetSum = 5 Output ：[]
Example 3：
Input ：root = [1,2], targetSum = 0 Output ：[]
Tips ：
[0, 5000] Inside -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# dfs
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
def dfs(root:Optional[TreeNode], target, path:List[int], mysum:int):
if root:
path.append(root.val)
mysum += root.val
if not root.right and not root.left and mysum == target:
ret.append(path[:])
"""
This must be sliced , Otherwise, mistakes will happen （ Output an empty list directly ）, I guess it's because when a function is called ,
direct append（path） It's right path Address space append That's why empty collections are displayed , and
path[:] It is equivalent to a deep copy of a new path, For this new path The operation of is in a new address space
operation , Will not be used by the original address space path influence
See in detail ：https://leetcode-cn.com/problems/path-sum-ii/solution/lc113-fengwei2002-guan-yu-bu-li-jie-slic-hank/
for example a = [1,2,3]
b = a
c = a[:]
b.append(4)
c.append(5)
print(a) # [1, 2, 3, 4]
"""
dfs(root.left, target, path, mysum)
dfs(root.right, target, path, mysum) # The inside of these two recursive functions will not change the outside mysum The value of a variable
path.pop()
# mysum -= root.val No need for this step , because mysum This variable is for recursive dfs The inner function is equivalent to a global variable
ret = []
path = []
dfs(root, targetSum, path, 0)
return ret
