首页 > 其他 > 详细

37-42,多做了一道是因为看了两道题的思路

时间:2021-09-21 00:26:27      阅读:3      评论:0      收藏:0      [点我收藏+]

37:  解数独  

唉 其实这道题我觉得我是可以的  但是后来想着这回溯太深了 方法是不是不对 就放弃了 后悔  就是后悔

力扣的全局变量我也不是很会写

全局变量不会写 只能传递了

class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        def DFS(pos,valid):         #pos表示当前填的是第几个格子

            i,j = gap[pos]
            if pos == len(gap)-1:
                for num in range(9):
                    if (row[i][num] == False) and (col[j][num] == False) and (block[i//3][j//3][num] == False):
                        board[i][j] = str(num +1)
                        valid = True
                        return valid

            for num in range(9):
                if (row[i][num] == False) and (col[j][num] == False) and (block[i//3][j//3][num] == False):
                    board[i][j] = str(num +1)
                    row[i][num] = True
                    col[j][num] = True
                    block[i//3][j//3][num] = True
                    valid = DFS(pos+1,valid)
                    row[i][num] = False
                    col[j][num] = False
                    block[i//3][j//3][num] = False
                if valid:
                    return valid


作者:yizhu-jia
链接:https://leetcode-cn.com/problems/sudoku-solver/solution/pythonde-quan-ju-bian-liang-zen-yao-xie-36wgn/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

 

38 :外观数组

就一个一个推过去

没想到超过大部分人

        def nextsay(countstr):
            nextcountstr =""
            count = 0
            curnum = countstr[0]
            for each in countstr:
                if each == curnum:
                    count += 1
                    continue
                else:
                    nextcountstr +=(str(count)+str(curnum))
                    curnum = each
                    count = 1
            nextcountstr += (str(count)+str(curnum))
            return nextcountstr
        count = 1
        for i in range(n-1):
            count = nextsay(count)
        return count

 

39:

组合总和:  不知道是不是自己写出来的第一道回溯

        rel = []
        currel = []
        def DFS(cursum,rel,currel):
            n = len(candidates)
            for i in range(n):
                if len(currel) != 0 :
                    if candidates[i] < currel[-1]:
                        break          #这里表示只能往后找 不能往前找
                cursum += candidates[i]
                currel .append(candidates[i])
                if cursum  == target:
                    rel .append(currel[:])
                elif cursum < target:
                    DFS(cursum,rel,currel)
                currel.pop()
                cursum -= candidates[i]
        DFS(0,rel,currel)
        return     rel

 

40:组合但是不能重复

但是好难  最后看别人的方法...

这种觉得残差还是传剩余值比较好

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """

        def DFS(begin,path,residual):
            if residual == 0:
                rel.append(path[:])
                return
            for i in range(begin,n):
                if candidates[i]  > residual:
                    break
                if i > begin and candidates[i-1] == candidates[i]:
                    continue
                path .append(candidates[i])
                DFS(i+1,path,residual-candidates[i])
                path.pop()


        rel = []
        candidates = sorted(candidates)
        n = len(candidates)
        DFS(0,[],target)
        return  rel


作者:yizhu-jia
链接:https://leetcode-cn.com/problems/combination-sum-ii/solution/bie-wen-liao-chao-de-by-yizhu-jia-8ve9/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

41:

求未出现最小正整数

说是固定长度的空间  本意是原地哈希

但是我:  毅然被所有人击败:::

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        num = [0] * 5*10**5
        for each in nums:
            if each <= 5*10**5 and each > 0:
                num[each-1] = 1
        for i in range(5*10**5):
            if num[i] == 0 :
                return i+1
        return 5*10**5 +1

作者:yizhu-jia
链接:https://leetcode-cn.com/problems/first-missing-positive/solution/bei-suo-you-ren-ji-bai-by-yizhu-jia-no8s/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

 

42:接牙吗么接雨水

单调栈 第一次见  大概懂了  就是栈里只能递减着存   不能出现后面数大的情况  可以处理很多题

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        stack=[]
        water = 0
        for index,h in enumerate(height):
            while stack and h > height[stack[-1]]:
                l = stack.pop()
                if not stack:
                    break
                wid = index-stack[-1]-1
                hig = min(height[stack[-1]],h) - height[l]
                water += hig* wid
            stack.append(index)
        return water
            

作者:yizhu-jia
链接:https://leetcode-cn.com/problems/trapping-rain-water/solution/dui-bu-qi-chao-de-by-yizhu-jia-wo6i/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

 

37-42,多做了一道是因为看了两道题的思路

原文:https://www.cnblogs.com/xiaoli1996/p/15310910.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!