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

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

本帖被以下淘专辑推荐:

评分

评分

评分

评分

评分

评分

评分

评分

评分