【leetcode】翻转单词lambda map filter+填数独+回溯算法locs+getMaps+fillboard
程序员文章站
2024-02-28 22:23:16
...
第一次提交结果
class Solution(object):
def reverseWords(self, s):
"""
:type s: str
:rtype: str
"""
#print(a.strip()) #去除首尾空格
#print(a.lstrip()) #去除首空格
#print(a.rstrip()) #去除尾空格
string=s.strip().split(' ')
string=[value.strip() for key,value in enumerate(string)]
stri=[]
for key,value in enumerate(string):
if not value=="" : stri.append(value)
return " ".join(stri[::-1])
第二次简化 使用map 和 lambda 函数
class Solution(object):
def reverseWords(self, s):
string=s.strip().split(' ')
map(lambda x:x.strip(),string)
stri=[]
for key,value in enumerate(string):
if not value=="" : stri.append(value)
return " ".join(stri[::-1])
第三次简化 学习list filter 函数
def reverseWords(self, s):
return " ".join(list(filter(lambda x:not x=='',list(map(lambda x:x.strip(),s.split(' ')))))[::-1])
学习别人的方法
def reverseWords(self, s):
return ' '.join(reversed(s.strip().split()))
数独
class Solution(object):
def solveSudoku(self, boar):
"""
:type board: List[List[str]]
:rtype: None Do not return anything, modify board in-place instead.
"""
def getLocs(board):
locs=[]
for row in range(9):
for col in range(9):
if board[row][col]=='.':
locs.append((row,col))
return locs
def getMaps(board):
from collections import defaultdict as dd
rowMap =[dd(int) for _ in range(9)]
colMap =[dd(int) for _ in range(9)]
blockMap=[dd(int) for _ in range(9)]
for row in range(9):
for col in range(9):
if board[row][col]!='.':
num=int(board[row][col])
rowMap[row][num]+=1
colMap[col][num]+=1
blockIndex=int(row/3)*3+int(col/3)
blockMap[blockIndex][num]+=1
return rowMap,colMap,blockMap
def fillboard(locs):
from collections import defaultdict as dd
if not locs:
return True
global rowMap,colMap,blockMap,board
row,col =locs.pop() #弹出一个待填充位置
blockIndex=int(row/3)*3+int(col/3)
found= False
for num in range(1,10):
if found: break
if (not rowMap[row][num]) and( not colMap[col][num]) and (not blockMap[blockIndex][num]):
rowMap[row][num]+=1
colMap[col][num]+=1
blockIndex=int(row/3)*3+int(col/3)
blockMap[blockIndex][num]=1
board[row][col]=str(num)
found=fillboard(locs) #递归到下一层
rowMap[row][num]=0 #状态回溯,将填充的位置清空
colMap[col][num]=0
blockIndex=int(row/3)*3+int(col/3)
blockMap[blockIndex][num]=0 ##这里出错了
if not found: ##如果本轮都无法求解,则回溯到初始状态,继续从前面再填充
locs.append((row,col))
board[row][col]='.'
return found
global rowMap,colMap,blockMap,board
board=boar
rowMap,colMap,blockMap =getMaps(board)
locs= getLocs(board)
fillboard(locs)
return board