#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算两个数之和
# @param s string字符串 表示第一个整数
# @param t string字符串 表示第二个整数
# @return string字符串
#
class Solution:
def solve(self , s: str, t: str) -> str:
# write code here
# 进位
carry = 0
lens = len(s)
lent = len(t)
max_len = max(lens, lent)
res = ''
for i in range(max_len):
# 逆序相加x1 x2 carry
if i < lens:
x1 = int(s[lens - i -1])
# 说明s是短的则 前面补0对齐
else:
x1 = 0
if i < lent:
x2 = int(t[lent - i -1])
# 说明s是短的则 前面补0对齐
else:
x2 = 0
temp = x1 + x2 + carry
res += str(temp % 10)
carry = temp // 10# 注意// 才是整数除余
# 说明首位是进位
if carry == 1:
res += '1'
# 逆序输出
return res[::-1]
不进位的长乘法
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串 第一个整数
# @param t string字符串 第二个整数
# @return string字符串
#
class Solution:
def solve(self , s: str, t: str) -> str:
# write code here
if s == '0' or t == '0':
return '0'
s = list(s)
t = list(t)
# 因为是从最后一位开始相乘 所以需要逆转一下
s.reverse()
t.reverse()
res = [0] * (len(s) + len(t))
print(s, t)
for i in range(len(s)):
for j in range(len(t)):
#结果是 18 25 8 0
res[i + j ] += int(s[i])*int(t[j])
“”“
['2', '1'] ['9', '8']
”“”
print(res)
carry = 0 # 进位
for k in range(len(res)):
res[k] += carry
carry = res[k] // 10
res[k] = res [k] % 10
# res是int的列表 且是逆序所以需要逆转 且最后一位是0 说明逆转后高位是0 所以去除最后一位
if res[-1] == 0:
res.pop()
res.reverse()
ans = ''
for x in res:
ans += str(x)
return ans
思路参考：https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/
简单来说：就是由二叉树的前序遍历推广到网格的dfs，二叉树是左右两个孩子，网格是上下左右四个孩子。
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
def dfs(grid, i, j):
# 边界出口
if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]):return
# 不是岛屿 返回
if grid[i][j] == '0':return
# 访问过的陆地记为0 海洋
grid[i][j] = '0'
#遍历 分别是上下左右
dfs(grid, i-1, j)
dfs(grid, i+1, j)
dfs(grid, i, j-1)
dfs(grid, i, j+1)
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
# 取出所有陆地
if grid[i][j] == '1':
dfs(grid, i, j)
count += 1
return count
思路:先求岛屿面积，每遍历一个格子就面积加1
class Solution(object):
def maxAreaOfIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
def dfs(grid, i, j):
# 边界
if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]):return 0
# 不是岛屿 返回
if grid[i][j] != 1 :return 0
# 标记已访问的结点 赋值为2
grid[i][j] = 2
num = 1
# 遍历上下左右的陆地 每遍历一次陆地就加1
num += dfs(grid, i-1, j)
num += dfs(grid, i+1, j)
num += dfs(grid, i, j-1)
num += dfs(grid, i, j+1)
return num
res = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
res = max(res, dfs(grid, i, j))
return res
tips：注意题目给的是str还是int 是‘1’还是1
思路：
总体思路： 对网格做两遍 DFS：第一遍 DFS 遍历陆地格子，计算每个岛屿的面积并标记岛屿；这个题目见LeetCode 695. Max Area of Island ，
第二遍 DFS 遍历海洋格子，观察每个海洋格子相邻的岛屿格子。重点！！！把每个岛屿格子的值标为面积
0是海洋1是岛屿
class Solution(object):
def largestIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
# 第一步遍历陆地 求岛屿的面积area
# 第二步遍历海洋 求海洋上下左右不同的岛屿的编号 才能联通 findneighbor
# 边界函数
def inbound(grid, i, j):
return 0 <= i < len(grid) and 0 <= j < len(grid[0])
# 求编号为index岛屿的面积
def area(grid, i, j, index):
if not inbound(grid, i, j):return 0
# 如果不是未访问过的陆地
if grid[i][j] != 1 :return 0
# 标记为index 表示访问过
grid[i][j] = index
return 1 + area(grid, i - 1, j, index) + area(grid, i + 1, j, index) + area(grid, i, j-1, index) + area(grid, i, j+1, index)
# 将来遍历海洋时 需要找到每格海洋上下左右相邻的陆地编号 同时要保证陆地编号要是index
def findneighbor(grid, i, j):
PerOceacnNeighlan = set()
if(inbound(grid, i - 1, j) and grid[i - 1][j] >= 2):
PerOceacnNeighlan.add(grid[i - 1][j])
if(inbound(grid, i + 1, j) and grid[i + 1][j] >= 2):
PerOceacnNeighlan.add(grid[i + 1][j])
if(inbound(grid, i, j - 1) and grid[i][j - 1] >= 2):
PerOceacnNeighlan.add(grid[i][j - 1])
if(inbound(grid, i, j + 1) and grid[i][j + 1] >= 2):
PerOceacnNeighlan.add(grid[i][j + 1])
return PerOceacnNeighlan
# 主函数 分两步进行
# 第一步遍历陆地 求岛屿的面积area
# 第二步遍历海洋 求海洋上下左右不同的岛屿的编号 才能联通 findneighbor
index = 2 # index从2开始 避免与陆地1和海洋0冲突
res = 0 #最终连通的最大面积和
PerIlanArea = {}# 计算不同编号岛屿的面积
# 遍历没有访问的陆地
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
sum = area(grid, i, j, index) # 求岛屿面积
PerIlanArea[index] = sum # 存入岛屿编号、岛屿面积
index += 1 # 岛屿编号增加
res = max(res,sum)# 记录不同编号之间最大的岛屿面积
if res == 0:return 1 # res =0 表示没有陆地 就造一块陆地
# 遍历没有访问的海洋格子
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 0:
# 对于每个海洋格子求出他上下左右陆地的编号
OceanSet = findneighbor(grid, i, j)
if len(OceanSet) < 1 :continue # 说明这个海洋格子周围没有不同的陆地编号 联通不了
total = 1 # 这个海洋变陆地的格子，之后记录连通后的和
# print(OceanSet)
for index in OceanSet:
total += PerIlanArea[index]
res = max(total,res) # 记录所有【连通后的】最大的岛屿面积
return res
class Solution(object):
def islandPerimeter(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
# 当一个陆地格子分别走向边界和海洋时都会使周长加1 而陆地格子走向陆地格子不影响周长
def dfs(grid, i, j):
# 走向边界 加1
if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]):return 1
# 走向海洋 加1
if grid[i][j] == 0:return 1
# 走向已经访问过的陆地
if grid[i][j] != 1:return 0
# 标记访问过的陆地
grid[i][j] = 2
return dfs(grid, i-1, j) + dfs(grid, i+1, j) + dfs(grid, i, j - 1) + dfs(grid, i, j + 1)
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
res = dfs(grid, i, j)
return res
此题是1254. 统计封闭岛屿的数目+695. 岛屿的最大面积的结合，即全被水围起来的陆地才是封闭岛屿，被边界围绕的不算，即求解封闭岛屿的面积
class Solution:
def numEnclaves(self, grid: List[List[int]]) -> int:
def dfs(row, col):
if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]):
self.val = 0 # 是边界 说明不是封闭岛屿
return
if grid[row][col] != 1:
return
grid[row][col] = 0;
self.s += 1 # 有一个陆地格子，面积S就+1
dfs(row - 1, col)
dfs(row + 1, col)
dfs(row, col - 1)
dfs(row, col + 1)
count = 0
for i in range(0, len(grid)):
for j in range(0, len(grid[0])):
if grid[i][j] == 1:
self.s = 0 #面积先初始化为0
self.val = 1 #先假设是封闭岛屿
dfs(i, j) # 如果不是封闭岛屿 val会被置为0
#说明是封闭岛屿 计算面积
if self.val:
count += self.s
return count
法二：从边界出发进行深搜dfs，因为边界的陆地相连不算岛屿，所以dfs中会把在边界上的陆地置为海洋0，那么剩下的1就是封闭岛屿的面积。
class Solution:
def numEnclaves(self, grid: List[List[int]]) -> int:
def dfs(row, col):
if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]):
return
if grid[row][col] == 0:
return
grid[row][col] = 0;
dfs(row - 1, col)
dfs(row + 1, col)
dfs(row, col - 1)
dfs(row, col + 1)
# 从边界出发 把不是封闭岛屿的部分沉底
for i in range(0, len(grid)):
dfs(i, 0)
dfs(i, len(grid[0]) - 1)
for i in range(0, len(grid[0])):
dfs(0, i)
dfs(len(grid) - 1, i)
# 剩下一定是封闭岛屿 求岛屿的面积
count = 0
for i in range(0, len(grid)):
for j in range(0, len(grid[0])):
if grid[i][j] == 1:
count += 1
return count
这里要注意0是陆地 1是水…
此题是200.岛屿数量的变形，不同点在于此题中完全被水围起来的陆地才是封闭岛屿，被边界围绕的不算，那么我们只需要将遇到边界时的‘岛屿’省略掉
class Solution(object):
def closedIsland(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
def dfs(grid, i, j):
if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]):
self.val = 0# #注意这里用self.val=0 假如遇到边界，标记此时不算做岛屿
return
# 本题0是陆地 1是海洋
if grid[i][j] != 0:return
grid[i][j] = 2 #标记访问过的陆路为2
dfs(grid, i - 1, j)
dfs(grid, i + 1, j)
dfs(grid, i, j - 1)
dfs(grid, i, j + 1)
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 0:
self.val = 1 # 先假设遇到封闭岛屿
dfs(grid, i, j)# 如果没遇到 会置为0
count += self.val
return count
```
法二：
从边界开始寻找是土地但不是封闭岛屿的土地，先将这些土地至1（海洋）后，再统计封闭岛屿的数目，现在剩下就是封闭岛屿。
```python
class Solution:
def closedIsland(self, grid: List[List[int]]) -> int:
def dfs(row, col):
if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]):
return
# 遇到的不是陆地 返回
if grid[row][col] != 0:
return
# 标记访问过的陆地变成海洋
grid[row][col] = 1
dfs(row - 1, col)
dfs(row + 1, col)
dfs(row, col - 1)
dfs(row, col + 1)
# 判断边界 从边界出发 然后沉底
for i in range(0, len(grid)):
dfs(i, 0)
dfs(i, len(grid[0]) - 1)
for i in range(0, len(grid[0])):
dfs(0, i)
dfs(len(grid) - 1, i)
# 剩下的就是封闭岛屿 看可以几次dfs 就有几个封闭岛屿
count = 0
for i in range(0, len(grid)):
for j in range(0, len(grid[0])):
if grid[i][j] == 0:
dfs(i,j)
count += 1
return count
class Solution:
def solve(self,grid: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
# 相当于找封闭的岛屿 且把封闭岛屿置为x 假设 x是海洋 o是陆地
# 从边界出发把边界处的o（陆地）变成B 然后剩下的就是封闭的岛屿
# 遍历整个表格 找到封闭岛屿o变x B再变o
def dfs(grid, i, j):
if not 0 <= i < len(grid) or not 0 <= j < len(grid[0]):
return
if grid[i][j] != 'O':
return
# 访问过的O 变成B
grid[i][j] = 'B'
dfs(grid, i - 1, j)
dfs(grid, i + 1, j)
dfs(grid, i, j - 1)
dfs(grid, i, j + 1)
# 对边界处的o进行变换B的 *** 作
for i in range(len(grid)):
dfs(grid, i, 0)
dfs(grid, i, len(grid[0])-1)
for j in range(len(grid[0])):
dfs(grid, 0, j)
dfs(grid, len(grid)-1, j)
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 'O':
grid[i][j] = 'X'
if grid[i][j] == 'B':
grid[i][j] = 'O'
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）