[已解决]Python：每日一题 302

zltzlt · 发表于 2020-1-7 22:03:11

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

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

x

今天的题目：

给定一个矩阵，仅包含 'X' 和 'O'，找到所有被 'X' 围绕的区域，并用 'X' 替换被围绕的所有的 'O'。

示例 1：

输入：
[
  ['X', 'X', 'X', 'X'],
  ['X', 'O', 'O', 'X'],
  ['X', 'X', 'O', 'X'],
  ['X', 'O', 'X', 'X'],
]
输出：
[
  ['X', 'X', 'X', 'X'],
  ['X', 'X', 'X', 'X'],
  ['X', 'X', 'X', 'X'],
  ['X', 'O', 'X', 'X'],
]

示例 2：

输入：
[
  ['X', 'X', 'X', 'X'],
  ['X', 'O', 'O', 'X'],
  ['X', 'O', 'O', 'X'],
  ['X', 'O', 'X', 'X'],
]
输出：
[
  ['X', 'X', 'X', 'X'],
  ['X', 'O', 'O', 'X'],
  ['X', 'O', 'O', 'X'],
  ['X', 'O', 'X', 'X'],
]

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

TJBEST

2020-1-8 15:26:47

本帖最后由 TJBEST 于 2020-1-8 20:53 编辑

题主改完了，你给测个数吧

def fun302(grid):
if grid == [] :
return []
def find_O_side(x,y,where):
if grid[x][y] == 'X':
pass
elif (x,y) in O_side:
pass
else:
O_side.append((x,y))
if 'left' not in where:
if y > 0:
find_O_side(x,y - 1,['right'])
if 'right' not in where:
if y < n - 1:
find_O_side(x,y + 1,['left'])
if 'up' not in where:
if x > 0:
find_O_side(x - 1,y,['bottom'])
if 'bottom' not in where:
if x < m - 1:
find_O_side(x + 1,y,['up'])
O_side = []#记录所有最后还是O的点
m = len(grid)
n = len(grid[0])
#左侧
find_O_side(0,0,['left','up'])
for i in range(1,m - 1):
find_O_side(i,0,['left'])
#底层
find_O_side(m - 1,0,['left','bottom'])
for i in range(1,n - 1):
find_O_side(m - 1,i,['bottom'])
#右侧
find_O_side(m - 1,n - 1,['right','bottom'])
for i in range(1,m - 1):
find_O_side(i,n - 1,['right'])
#顶层
find_O_side(0,n - 1,['right','up'])
for i in range(1,n - 1):
find_O_side(0,i,['up'])
res = [['X'for i in range(0,n)]for j in range(0,m)]#二维数组的问题建立时注意引用关系
for each in O_side:
res[each[0]][each[1]] = 'O'
return res

复制代码

跳转到最佳答案楼层

阴阳神万物主 · 发表于 2020-1-7 22:34:19

本帖最后由阴阳神万物主于 2020-1-8 04:06 编辑

下围棋？
我已经不考虑效率哒！

def solve(face:'list 棋盘'):
class Point:
def __init__(self,pos:tuple,side:int):
self.x,self.y = pos
self.side = side
def cycle(x,y):#从O看
c = [Point((x,y-1),0)]
#print('调试',x,y)
try:
while c:#并非全气
now = c[-1]
#从已知方向探寻
for i in range(7):
index = (i+now.side)%8
x,y = now.x+sides[index][0],now.y+sides[index][1]
if x<0 or y<0:#过界了
return []
elif x==c[0].x and y<c[0].y:#圈反了，要顺时针圈
return []
if face[x][y] == 'X':
c.append(Point((x,y),(index-1 if index%2 else index-2)))
break
else:
return []
if (c[0].x,c[0].y)==(c[-1].x,c[-1].y):
if c[0].side != c[-1].side:#折返到头了
return []
break
except IndexError:#在边上，必然不会围上
return []
#print('调试',len(c))
return c
sides = ((-1,1),(-1,0),(-1,-1),(0,-1),(1,-1),(1,0),(1,1),(0,1))
for x in range(len(face)):
for y in range(1,len(face[x])):
if face[x][y]=='O' and face[x][y-1]=='X' and ('X'in face[x][y:]):#西方无气
for each in cycle(x,y):#有围
index = (each.side-1)%8
#print('调试',each.x,each.y,index)
nx,ny = each.x+sides[index][0],each.y+sides[index][1]
while face[nx][ny] == 'O':
#print('调试',nx,ny,index)
face[nx][ny] = 'X'
nx,ny = nx+sides[index][0],ny+sides[index][1]
return face

复制代码

结果应该没问题。
如下玩法都没玩脱

>>> for line in solve([
['O', 'O', 'X', 'O', 'O', 'O', 'O', 'O', 'O', 'O'],
['O', 'X', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O'],
['X', 'O', 'X', 'X', 'O', 'X', 'O', 'O', 'O', 'O'],
['X', 'O', 'X', 'O', 'X', 'O', 'X', 'O', 'O', 'O'],
['X', 'O', 'X', 'O', 'X', 'O', 'X', 'O', 'O', 'X'],
['O', 'O', 'X', 'O', 'O', 'O', 'X', 'O', 'X', 'O'],
['O', 'O', 'O', 'X', 'O', 'X', 'O', 'O', 'O', 'X'],
['O', 'O', 'O', 'O', 'X', 'O', 'O', 'O', 'O', 'O'],
['O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O'],
['O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O']
]):
print(line)
['O', 'O', 'X', 'O', 'O', 'O', 'O', 'O', 'O', 'O']
['O', 'X', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O']
['X', 'O', 'X', 'X', 'O', 'X', 'O', 'O', 'O', 'O']
['X', 'O', 'X', 'X', 'X', 'X', 'X', 'O', 'O', 'O']
['X', 'O', 'X', 'X', 'X', 'X', 'X', 'O', 'O', 'X']
['O', 'O', 'X', 'X', 'X', 'X', 'X', 'O', 'X', 'O']
['O', 'O', 'O', 'X', 'X', 'X', 'O', 'O', 'O', 'X']
['O', 'O', 'O', 'O', 'X', 'O', 'O', 'O', 'O', 'O']
['O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O']
['O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O', 'O']
>>>

复制代码

Stubborn · 发表于 2020-1-7 23:45:19

本帖最后由 Stubborn 于 2020-1-8 02:45 编辑

这让我学习过的一个数据结构：并查集查一个点，到另外一个点，是否有联系。

，
勉强通过，虽然速度慢了点， def gang(coordinate): 检查连通性，可以优化，

，不过还是算了吧

# -*- coding: utf-8 -*-
# !/usr/bin/python3
"""
@ Version : ??
@ Author : Alex
@ Software : Pycharm
@ Time : 2020/1/2 下午2:20
"""
from typing import List
def union(array: List[List[str]]) -> List[List[str]]:
"""
首先说下，并查集解决的问题，假设有这样的数据 1->2-3 4->5->6
1和3是有关系的吗？是的
1和4是有关系的吗？不是
所以我们的思路是把所有边界上的O看做一个连通区域。
遇到O就执行并查集合并操作，这样所有的O就会被分成两类
和边界上的O在一个连通区域内的。这些O我们保留。
不和边界上的O在一个连通区域内的。这些O就是被包围的，替换
"""
row = len(array)
col = len(array[0])
# 这里是链接池，和外围有关系的家伙都被加进这里啦
unions = []
ret = [['X'] * col for _ in range(row)]
def enclosure(array):
"""圈地，看下外围有多少‘O’，进而往内部搜索"""
r = []
l = len(array) - 1
s = len(array[0]) - 1
for i, v in enumerate(array[0]):
if v == "O":
r.append((0, i))
for i, v in enumerate(array[-1]):
if v == "O":
r.append((l, i))
for i, v in enumerate(array[1:-1]):
if v[0] == "O":
r.append((i + 1, 0))
if v[-1] == "O":
r.append((i + 1, s))
return r
def gang(coordinate):
"""看看刁民(coordinate),有没有团伙"""
res = []
r, c = coordinate
if 0 < r < row - 1:
if array[r + 1][c] == "O":
res.append((r + 1, c))
if array[r - 1][c] == "O":
res.append((r - 1, c))
elif r == 0: # 只能向下扩展，
if array[r + 1][c] == "O":
res.append((r + 1, c))
elif r == row - 1: # 只能向上扩展
if array[r - 1][c] == "O":
res.append((r - 1, c))
if 0 < c < col - 1:
if array[r][c + 1] == "O":
res.append((r, c + 1))
if array[r][c - 1] == "O":
res.append((r, c - 1))
if c == 0: # 只能向右扩展，
if array[r][c + 1] == "O":
res.append((r, c + 1))
elif c == col - 1: # 只能向左扩展
if array[r][c - 1] == "O":
res.append((r, c - 1))
new = []
for i in res:
if i not in unions:
new.append(i)
return new
# 这是我们初始的刁民，开始往里面圈地了
temporary_union = enclosure(array)
while temporary_union:
unions.append(temporary_union[-1])
O = temporary_union.pop()
temporary_union += gang(O)
for x, y in unions:
ret[x][y] = "O"
return ret

复制代码

Croper · 发表于 2020-1-7 23:50:27

本帖最后由 Croper 于 2020-1-7 23:58 编辑

继续炸岛喽，今天只炸一圈

def func302(grid)->int:
if len(grid)==0 or len(grid[0])==0:
return grid
width=len(grid[0])
height=len(grid)
ret=[['X']*width for _ in range(height)]
#把岛，哦不，把白棋吃掉
def burnisland(i,j):
if i<0 or i>=height or j<0 or j>=width:
return
if grid[i][j]=='X':
return
grid[i][j]='X'
ret[i][j]='O'
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 (0<i<height-1 and 0<j<width-1) or grid[i][j]=='X':
continue
burnisland(i,j)
return ret

复制代码

阴阳神万物主 · 发表于 2020-1-8 00:10:38

Croper 发表于 2020-1-7 23:50
继续炸岛喽，今天只炸一圈

>>> func302([
['X','O','X','X'],
['X','X','O','X'],
['X','O','O','X'],
['X','O','O','O']
])
Traceback (most recent call last):
File "<pyshell#8>", line 5, in <module>
['X','O','O','O']
File "<pyshell#1>", line 8, in func302
ret=[['X']*width for _ in height]
TypeError: 'int' object is not iterable
>>>

复制代码

你没调试过吗？

Croper · 发表于 2020-1-8 00:17:14

阴阳神万物主发表于 2020-1-8 00:10
你没调试过吗？

不好意思，最先改了点就发上来了。。。

没到一分钟我就删了没想到还是被你复制下来了。。。

hrp · 发表于 2020-1-8 01:09:13

本帖最后由 hrp 于 2020-1-8 19:55 编辑

乱七八糟

def func302(m):
if (not m) or (not m[0]):
return m
om, xm, flag = set(), set(), 1
line, row = len(m), len(m[0])
def find(i, j):
nonlocal flag
if not (i, j) in xm:
if flag:
if (m[i][j] == 'O') and (i in range(1, line-1)) and (j in range(1, row-1)):
temp = (i, j-1), (i-1, j), (i, j+1), (i+1, j)
if not False in ((m[p][q] == 'X') or ((p, q) in om) for p, q in temp):
for k, l in om:
m[k][l] = 'X'
else:
for p, q in temp:
if (m[p][q] == 'O') and (not (p, q) in om):
om.add((p, q))
find(p, q)
elif (m[p][q] == 'X') and (not (p, q) in xm):
xm.add((p, q))
elif ((not (i in range(1, line-1))) or (not (j in range(1, row-1)))) and (m[i][j] == 'O'):
flag = 0
for i in range(1, line-1):
for j in range(1, row-1):
if m[i][j] == 'X':
if not (i, j) in xm:
xm.add((i, j))
else:
if not (i, j) in om:
om.add((i, j))
find(i, j)
return m

复制代码

kinkon · 发表于 2020-1-8 11:58:54

Croper 发表于 2020-1-7 23:50
继续炸岛喽，今天只炸一圈

def burnisland(i,j):
      if i<0 or i>=height or j<0 or j>=width:
         return
      if grid[i][j]=='X':
         return
      grid[i][j]='X'
      ret[i][j]='O'
      burnisland(i+1,j)
      burnisland(i-1,j)
      burnisland(i,j+1)
      burnisland(i,j-1)
新手求教，能不能解释这段代码是怎么执行的？
字面上看是把grid中的'0'赋值给了ret

Croper · 发表于 2020-1-8 13:49:45

kinkon 发表于 2020-1-8 11:58
def burnisland(i,j):
if i=height or j=width:
return

把周围一圈（以及与其相邻的）‘O’赋值给ret，
不相邻的‘O’当然是被围死了啊

kinkon · 发表于 2020-1-8 14:31:58

本帖最后由 kinkon 于 2020-1-8 15:16 编辑

Croper 发表于 2020-1-8 13:49
把周围一圈（以及与其相邻的）‘O’赋值给ret，
不相邻的‘O’当然是被围死了啊

谢谢，函数这里明白了，不理解的应该是在for循环里。4行4列的循环后为什么会变成10行10列了？

TJBEST · 发表于 2020-1-8 15:26:47

这个最佳答案由 TJBEST 给出，感谢 TJBEST 的回答。

单击隐藏图章

本帖最后由 TJBEST 于 2020-1-8 20:53 编辑

题主改完了，你给测个数吧

def fun302(grid):
if grid == [] :
return []
def find_O_side(x,y,where):
if grid[x][y] == 'X':
pass
elif (x,y) in O_side:
pass
else:
O_side.append((x,y))
if 'left' not in where:
if y > 0:
find_O_side(x,y - 1,['right'])
if 'right' not in where:
if y < n - 1:
find_O_side(x,y + 1,['left'])
if 'up' not in where:
if x > 0:
find_O_side(x - 1,y,['bottom'])
if 'bottom' not in where:
if x < m - 1:
find_O_side(x + 1,y,['up'])
O_side = []#记录所有最后还是O的点
m = len(grid)
n = len(grid[0])
#左侧
find_O_side(0,0,['left','up'])
for i in range(1,m - 1):
find_O_side(i,0,['left'])
#底层
find_O_side(m - 1,0,['left','bottom'])
for i in range(1,n - 1):
find_O_side(m - 1,i,['bottom'])
#右侧
find_O_side(m - 1,n - 1,['right','bottom'])
for i in range(1,m - 1):
find_O_side(i,n - 1,['right'])
#顶层
find_O_side(0,n - 1,['right','up'])
for i in range(1,n - 1):
find_O_side(0,i,['up'])
res = [['X'for i in range(0,n)]for j in range(0,m)]#二维数组的问题建立时注意引用关系
for each in O_side:
res[each[0]][each[1]] = 'O'
return res

复制代码

776667 · 发表于 2020-1-8 15:45:47

def fun302(matrix):
def near_check(matrix,x,y):
near = [i for i in [[x-1,y],[x+1,y],[x,y-1],[x,y+1]] if 0 <= i[0] <= len(matrix)-1 and 0 <= i[1] <= len(matrix[x])-1]
return [i for i in near if matrix[i[0]][i[1]] == 'O']
O_zone,nearby,nearby_2 = [],[],[]
for i in range(len(matrix)):
if matrix[0][i] == 'O':
O_zone.append([0,i])
if near_check(matrix,0,i):
nearby = near_check(matrix,0,i)
while True:
O_zone.extend(nearby)
for j in nearby:
for n in near_check(matrix,j[0],j[1]):
if n not in O_zone:
nearby_2.append(n)
if not nearby_2:
break
nearby,nearby_2 = nearby_2,[]
if matrix[len(matrix)-1][i] == 'O' and [len(matrix)-1,i] not in O_zone:
O_zone.append([len(matrix)-1,i])
if near_check(matrix,len(matrix)-1,i):
nearby = near_check(matrix,len(matrix)-1,i)
while True:
O_zone.extend(nearby)
for j in nearby:
for n in near_check(matrix,j[0],j[1]):
if n not in O_zone:
nearby_2.append(n)
if not nearby_2:
break
nearby,nearby_2 = nearby_2,[]
for i in range(len(matrix[0])):
if matrix[i][0] == 'O' and [i,0] not in O_zone:
O_zone.append([i,0])
if near_check(matrix,i,0):
nearby = near_check(matrix,i,0)
while True:
O_zone.extend(nearby)
for j in nearby:
for n in near_check(matrix,j[0],j[1]):
if n not in O_zone:
nearby_2.append(n)
if not nearby_2:
break
nearby,nearby_2 = nearby_2,[]
if matrix[i][len(matrix[0])-1] == 'O' and [i,len(matrix[0])-1] not in O_zone:
O_zone.append([i,len(matrix[0])-1])
if near_check(matrix,i,len(matrix[0])-1):
nearby = near_check(matrix,i,len(matrix[0])-1)
while True:
O_zone.extend(nearby)
for j in nearby:
for n in near_check(matrix,j[0],j[1]):
if n not in O_zone:
nearby_2.append(n)
if not nearby_2:
break
nearby,nearby_2 = nearby_2,[]
for i in range(len(matrix)):
for j in range(len(matrix[i])):
if matrix[i][j] == 'O' and [i,j] not in O_zone:
matrix[i][j] = 'X'
return matrix

复制代码

阴阳神万物主 · 发表于 2020-1-8 18:13:44

TJBEST 发表于 2020-1-8 15:26
我又来了，超长代码你值得拥有。话说最近版主出题越来越难了

一直都是普通偏简单的难度，不同类的题型已经出得差不多了，版主大大还没有江郎才尽，已然是难能可贵。

zltzlt · 发表于 2020-1-8 20:20:04

hrp 发表于 2020-1-8 01:09
乱七八糟

解答错误

输入：[['X', 'X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X', 'X'], ['X', 'X', 'O', 'O', 'X'], ['X', 'X', 'O', 'X', 'X'], ['X', 'X', 'O', 'X', 'X']]
输出：[['X', 'X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X', 'X'], ['X', 'X', 'O', 'X', 'X'], ['X', 'X', 'O', 'X', 'X']]
预期结果：[['X', 'X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X', 'X'], ['X', 'X', 'O', 'O', 'X'], ['X', 'X', 'O', 'X', 'X'], ['X', 'X', 'O', 'X', 'X']]

zltzlt · 发表于 2020-1-8 20:23:55

Stubborn 发表于 2020-1-7 23:45
这让我学习过的一个数据结构：并查集查一个点，到另外一个点，是否有联系。，
勉强通过，虽然 ...

输入空矩阵 [] 报错。

zltzlt · 发表于 2020-1-8 20:24:51

TJBEST 发表于 2020-1-8 15:26
我又来了，超长代码你值得拥有。话说最近版主出题越来越难了

输入空矩阵 [] 报错。

zltzlt · 发表于 2020-1-8 20:26:18

776667 发表于 2020-1-8 15:45

输入空矩阵 [] 报错。

Croper · 发表于 2020-1-8 20:40:40

Stubborn 发表于 2020-1-7 23:45
这让我学习过的一个数据结构：并查集查一个点，到另外一个点，是否有联系。，
勉强通过，虽然 ...

并查集求动态问题比较好使一点。。
比如棋一直在下，然后求每一步的死活什么的。。

这里用这个有点杀鸡用牛刀的意思了- -

塔利班 · 发表于 2020-1-8 20:51:58

def f302(M):
J=len(M[0])
I=len(M)
if {0,1,2}&{J,I}:
return M
res=[['X']*J for _ in range(I)]
def dp(i,j):
if i in range(I) and j in range(J) and M[i][j]=='O':
res[i][j]='O'
M[i][j]='X'
dp(i+1,j)
dp(i-1,j)
dp(i,j+1)
dp(i,j-1)
for i in range(I):
dp(i,0)
dp(i,J-1)
for j in range(J):
dp(0,j)
dp(I-1,j)
return res

复制代码

来晚了，瞟了眼，

TJBEST · 发表于 2020-1-8 20:54:45

题主改完了，你给测个速度吧

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

[已解决]Python：每日一题 302

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

本帖被以下淘专辑推荐:

评分

评分

评分

评分

评分

评分

评分