欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【leetcode】翻转单词lambda map filter+填数独+回溯算法locs+getMaps+fillboard

程序员文章站 2024-02-28 22:23:16
...

【leetcode】翻转单词lambda map filter+填数独+回溯算法locs+getMaps+fillboard

第一次提交结果

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()))

数独

【leetcode】翻转单词lambda map filter+填数独+回溯算法locs+getMaps+fillboard

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
                
相关标签: 面试准备