Python：每日一题 298

zltzlt · 发表于 2020-1-1 17:35:50

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

今天的题目：

给一个 01 矩阵，求不同的岛屿的个数。

0 代表海，1 代表岛，如果两个 1 相邻，那么这两个 1 属于同一个岛。只考虑上下左右为相邻。

示例 1：

输入：
[
  [1,1,0,0,0],
  [0,1,0,0,1],
  [0,0,0,1,1],
  [0,0,0,0,0],
  [0,0,0,0,1]
]
输出：3

示例 2：

输入：
[
[1,1]
]
输出：1

欢迎大家一起答题！

18463102026 · 发表于 2020-1-1 17:44:08

本帖最后由 18463102026 于 2020-1-1 18:49 编辑

def fun297(s):
if len(s) == 0 or len(s[0]) == 0:
return 0
count, m, n = 0, len(s), len(s[0])
def fun(i, j):
if i < 0 or i >= m or j < 0 or j >= n or s[i][j] != 1:
return
s[i][j] = 0
fun(i, j - 1)
fun(i - 1, j)
fun(i + 1, j)
fun(i, j + 1)
for i in range(m):
for j in range(n):
if s[i][j] == 1:
count += 1
fun(i, j)
return count

复制代码

Croper · 发表于 2020-1-1 18:29:30

本帖最后由 Croper 于 2020-1-1 18:32 编辑

def func298(grid)->int:
if len(grid)==0 or len(grid[0])==0:
return 0
ret=0
width=len(grid[0])
height=len(grid)
#嗯，把岛炸掉
def burnisland(i,j):
if i<0 or i>=height or j<0 or j>=width:
return
if grid[i][j]==0:
return
grid[i][j]=0
burnisland(i+1,j)
burnisland(i-1,j)
burnisland(i,j+1)
burnisland(i,j-1)
#遇到一个岛炸一个岛
for i in range(height):
for j in range(width):
if grid[i][j]==0:
continue
ret+=1
burnisland(i,j)
return ret

复制代码

阴阳神万物主 · 发表于 2020-1-1 19:45:53

抢滩登陆模拟器~~~

def solve(world):
num = 0
lx,ly = len(world),(len(world[0]) if world else 0)
the_map = [[0]*ly]*lx
def explore(x,y):#探索岛屿并绘制地图，炸岛什么的不利于生存
nonlocal the_map
#print('调试',x,y,lx,ly)
if world[x][y]:
if the_map[x][y]:
return
else:
the_map[x][y] = num
if x:
explore(x-1,y)
if lx - x > 1:
explore(x+1,y)
if y:
explore(x,y-1)
if ly - y > 1:
explore(x,y+1)
for x in range(lx):
for y in range(ly):
if world[x][y] and (not the_map[x][y]):
num += 1
explore(x,y)
return num
if __name__ == '__main__':
print('示例1 输出：',solve([
[1,1,0,0,0],
[0,1,0,0,1],
[0,0,0,1,1],
[0,0,0,0,0],
[0,0,0,0,1]
]))
print('示例2 输出：',solve([
[1,1]
]))

复制代码

塔利班 · 发表于 2020-1-1 20:03:56

def f298(M):
res,I,J=0,len(M),len(M[0])
def dp(i,j):
if i in range(I) and j in range(J) and M[i][j]==1:
M[i][j]=0
dp(i,j-1)
dp(i-1,j)
dp(i+1,j)
dp(i,j+1)
for i in range(I):
for j in range(J):
if M[i][j]:
res+=1
dp(i,j)
return res

复制代码

DP都差不多

TJBEST · 发表于 2020-1-1 21:25:55

本帖最后由 TJBEST 于 2020-1-2 14:54 编辑

哈哈，我编了一个非常麻烦的方法，但是结果正确，哈哈

def fun298(matrix):
m = len(matrix)
n = len(matrix[0])
count = 1
##改写矩阵
for i in range(0,m):
for j in range(0,n):
if matrix[i][j]!=0:
if i!=0 and j!=0:
temp = max((matrix[i][j-1],matrix[i-1][j]))
if temp > 1:
matrix[i][j] = temp
else:
count = count + 1
matrix[i][j] = count
elif i == 0 and j != 0:
temp = matrix[i][j-1]
if temp > 1:
matrix[i][j] = temp
else:
count = count + 1
matrix[i][j] = count
elif i !=0 and j == 0:
temp = matrix[i-1][j]
if temp > 1:
matrix[i][j] = temp
else:
count = count + 1
matrix[i][j] = count
else:
count = count + 1
matrix[i][j] = count
##统计矩阵
listSet = set()
for i in range(0,m):
for j in range(0,n):
if matrix[i][j]!=0:
if i!=(m-1) and j!=(n-1):
temp1 = matrix[i][j]
temp2 = matrix[i][j+1]
temp3 = matrix[i+1][j]
if temp2 != 0:
listSet.add(tuple(sorted((temp1,temp2))))
elif temp3 != 0:
listSet.add(tuple(sorted((temp1,temp3))))
else:
listSet.add(tuple([temp1,temp1]))
elif i == (m-1) and j!=(n-1):
temp1 = matrix[i][j]
temp2 = matrix[i][j+1]
if temp2 != 0:
listSet.add(tuple(sorted((temp1,temp2))))
else:
listSet.add(tuple([temp1,temp1]))
elif i != (m-1) and j ==(n-1):
temp1 = matrix[i][j]
temp3 = matrix[i+1][j]
if temp3 != 0:
listSet.add(tuple(sorted((temp1,temp3))))
else:
listSet.add(tuple([temp1,temp1]))
else:
temp1 = matrix[i][j]
listSet.add(tuple([temp1,temp1]))
#计算多少个小岛
setCount = []
for eachmin in range(2,count + 1):
eachSet = {eachmin}
for eachTuple in listSet:
if eachmin == eachTuple[0]:
eachSet.add(eachTuple[1])
setCount.append(eachSet)
for index in range(count - 2,-1,-1):
temp = setCount[index]
for inner in range(0,index):
if (temp & setCount[inner])!=set():
setCount[inner] = setCount[inner] | temp
del setCount[index]
return len(setCount)

复制代码

ly.liu612308 · 发表于 2020-1-2 10:38:00

比较高级了啊，仔细看看，

archlzy · 发表于 2020-1-2 20:57:51

本帖最后由 archlzy 于 2020-1-3 00:36 编辑

import copy
def fun298(target_list):
def change(_m,_n, temp,m,n):
if 0<=_m<m and 0<=_n <n:
if temp[_m][_n] == 0:
return
else:
temp[_m][_n] = 0
change(_m-1,_n,temp,m,n)
change(_m,_n-1,temp,m,n)
change(_m+1,_n,temp,m,n)
change(_m,_n+1,temp,m,n)
else:
return
temp = copy.deepcopy(target_list)
m = len(target_list)
n = len(target_list[0])
count = 0
for _m in range(m):
for _n in range(n):
if temp[_m][_n] == 0:
pass
else:
count += 1
change(_m,_n, temp,m,n)
return count

复制代码

来个不是递归的

import copy
def fun298(tar_list):
m = len(tar_list)
n = len(tar_list[0])
temp = copy.deepcopy(tar_list)
count_list = [[0 for i in j] for j in temp]
count=0
res = []
for _m in range(m):
for _n in range(n):
if temp[_m][_n] == 0:
pass
else:
if _m==0:
if (temp[_m][_n-1] if _n>0 else 0) == 0:
count += 1
count_list[_m][_n] = count
else:
count_list[_m][_n] = count_list[_m][_n-1]
elif _n == 0:
if temp[_m-1][_n] == 0:
count += 1
count_list[_m][_n] = count
else:
count_list[_m][_n] = count_list[_m-1][_n]
elif temp[_m][_n-1] and temp[_m-1][_n] == 1:
if count_list[_m-1][_n] == count_list[_m][_n-1]:
count_list[_m][_n] = count_list[_m][_n-1]
else:
count_list[_m][_n] = count_list[_m-1][_n]
temp_count = count_list[_m][_n-1]
for i in range(_m+1):
for j in range(_n+1):
if count_list<i>[j] == temp_count:
count_list<i>[j] = count_list[_m-1][_n]
elif temp[_m][_n-1] == 1:
count_list[_m][_n] = count_list[_m][_n-1]
elif temp[_m-1][_n] == 1:
count_list[_m][_n] = count_list[_m-1][_n]
else:
count += 1
count_list[_m][_n] = count
for i in count_list:
res += i
res = set(res)
return len(res) - 1</i></i>

复制代码

zltzlt · 发表于 2020-1-2 21:28:23

阴阳神万物主发表于 2020-1-1 19:45
抢滩登陆模拟器~~~

解答错误

输入：[
[0,1,0],
[1,0,1],
[0,1,0]
]
输出：3
预期结果：4

zltzlt · 发表于 2020-1-2 21:30:14

TJBEST 发表于 2020-1-1 21:25
哈哈，我编了一个非常麻烦的方法，但是结果正确，哈哈

确实挺麻烦。。

输入大数据超时

TJBEST · 发表于 2020-1-2 21:43:52

zltzlt 发表于 2020-1-2 21:30
确实挺麻烦。。

输入大数据超时

就先这样吧，我测试大概 0.025ms一个点差不多矩阵 m*n= 40000 大概1秒

fan1993423 · 发表于 2020-1-2 22:58:43

这道题如果不用递归是不是做出来就超时了哦

阴阳神万物主 · 发表于 2020-1-2 23:42:28

本帖最后由阴阳神万物主于 2020-1-2 23:43 编辑

zltzlt 发表于 2020-1-2 21:28
解答错误

输入：[

登录/注册后可看大图

忘记检查登记的地图了……

登录/注册后可看大图

忘却了地址相通的特性。

def solve(world):
num = 0
lx,ly = len(world),(len(world[0]) if world else 0)
the_map = [[0]*ly for i in range(lx)]
def explore(x,y):#探索岛屿并绘制地图，炸岛什么的不利于生存
nonlocal the_map
if world[x][y]:
if the_map[x][y]:
return
else:
#print('调试',x,y,lx,ly)
the_map[x][y] = num
if x:
explore(x-1,y)
if lx - x > 1:
explore(x+1,y)
if y:
explore(x,y-1)
if ly - y > 1:
explore(x,y+1)
for x in range(lx):
for y in range(ly):
if world[x][y] and (not the_map[x][y]):
num += 1
explore(x,y)
'''
for line in the_map:
print(line)
'''
return num
if __name__ == '__main__':
'''
print('示例1 输出：',solve([
[1,1,0,0,0],
[0,1,0,0,1],
[0,0,0,1,1],
[0,0,0,0,0],
[0,0,0,0,1]
]))
print('示例2 输出：',solve([
[1,1]
]))
'''
print(solve([
[0,1,0],
[1,0,1],
[0,1,0]
]))

复制代码

Croper · 发表于 2020-1-2 23:43:14

不用递归也行啊。其实省去了函数调用，理论上还应该快点，而且不会浪费宝贵的栈空间。就是写着麻烦。
《数据结构于算法》的书上应该都有，二叉树周游的非递归写法，
其实是一个思想，手动进栈出栈。递归只是把这一系列工作交给了函数调用来处理罢了。

Croper · 发表于 2020-1-2 23:53:12

本帖最后由 Croper 于 2020-1-2 23:59 编辑

不用递归的

def func298(grid)->int:
if len(grid)==0 or len(grid[0])==0:
return 0
ret=0
width=len(grid[0])
height=len(grid)
#嗯，把岛炸掉
def burnisland(i,j):
if i<0 or i>=height or j<0 or j>=width:
return
if grid[i][j]==0:
return
stk=[(i,j)]
grid[i][j]=0
offset=((-1,0),(1,0),(0,-1),(0,1))
while (len(stk)>0):
(y,x)=stk.pop()
for (y1,x1) in offset:
y1+=y
x1+=x
if 0<=x1<width and 0<=y1<height and grid[y1][x1]==1:
grid[y1][x1]=0
stk.append((y1,x1))
#遇到一个岛炸一个岛
for i in range(height):
for j in range(width):
if grid[i][j]==0:
continue
ret+=1
burnisland(i,j)
return ret

复制代码

gink · 发表于 2020-1-2 23:59:47

#coding:utf-8

b=[
  [1,1,0,0,0],
  [0,1,0,0,1],
  [0,0,0,1,1],
  [0,0,0,0,0],
  [0,0,0,0,1]
]

row=len(b[0])
column=len(b)

def func(x,i,j):
if i<0 or j<0 or i>=row or j>=column:
      return 0
elif x[i][j]==0 or x[i][j]==2:
      return 0
else:
      x[i][j]=2
      func(x,i-1,j)
      func(x,i+1,j)
      func(x,i,j-1)
      func(x,i,j+1)

if __name__ =="__main__":
num=0
x=b
for i in range(row):
      for j in range(column):
         if x[i][j]==1:
            num+=1
            func(x,i,j)
print x
print num

Python_meng · 发表于 2020-1-3 09:33:54

膜拜各位大佬，这个应该是图像处理领域的连通性检测

776667 · 发表于 2020-1-3 10:48:07

def fun298(chart):
def nearland_check(chart,x,y):
nearby = [i for i in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]] if i[0] in range(len(chart)) and i[1] in range(len(chart[x]))]
return [i for i in nearby if chart[i[0]][i[1]]]
islands_count = 0
islands = []
for i in range(len(chart)):
for j in range(len(chart[i])):
if chart[i][j] and [i,j] not in islands:
islands_count += 1
near_land = nearland_check(chart,i,j)
islands.extend(near_land)
for n in near_land:
if nearland_check(chart,n[0],n[1]):
islands.extend(nearland_check(chart,n[0],n[1]))
return islands_count

复制代码

zltzlt · 发表于 2020-1-4 17:28:17

archlzy 发表于 2020-1-2 20:57
来个不是递归的

解答错误

输入：[[1,1,0,0,0],[0,1,0,0,1],[0,0,0,1,1],[0,0,0,0,0],[0,0,0,0,1]]
输出：4
预期结果：3

zltzlt · 发表于 2020-1-4 17:30:06

gink 发表于 2020-1-2 23:59
#coding:utf-8

b=[

请使用 Python 3。

账号		自动登录	找回密码
密码			立即注册

Python：每日一题 298

马上注册，结交更多好友，享用更多功能^_^

本帖被以下淘专辑推荐:

评分

评分

评分

评分

评分

评分

评分

评分

评分

浏览过的版块