2021-07-20leetcode刷题

image.png

class Solution:
    def climbStairs(self, n: int) -> int:
        dp=[1,2]
        i=2
        while i<n:
            dp.append(dp[-1]+dp[-2])
            i+=1
        return dp[n-1]

image.png

class Solution:
    def rob(self, nums: List[int]) -> int:
        value=[]
        if len(nums)>2:
            value.append(nums[0])
            value.append(nums[1])
            value.append(nums[0]+nums[2])
            i=3
            while i<len(nums):
                value.append(max(value[i-2],value[i-3])+nums[i])
                i+=1
            #print(value)
            return max(value[-1],value[-2])
        elif len(nums)==2:
            return max(nums)
        else:
            return nums[0]

image.png

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        a=[triangle[0][0]]
        b=[]
        for c in range(1,len(triangle)):
            
            for i in range(len(a)):
                if i==0:
                    b.append(a[i]+triangle[c][i])
                else:
                    b.append(min(a[i],a[i-1])+triangle[c][i])

            b.append(a[-1]+triangle[c][-1])
            
            a=b[:]
            b.clear()
        #print(a)
        return min(a)

image.png

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        if n==1:
            return True
        def judge(n):
            if n/2==1:
                return True
            elif n%2!=0 or n/2<1:
                return False
            else:
                return self.isPowerOfTwo(n//2)
        return judge(n)

image.png

class Solution:
    def hammingWeight(self, n: int) -> int:
        ans=0
        while n:
            if n%2!=0:
                ans+=1
            n//=2
        return ans

image.png

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        isvisited=[[False]*len(board[0]) for i in range(len(board))]
        len_str=len(word)
        ans=[]
        def dfs(cnt,i,j):
            #p=False
            #global flag
            if cnt==len_str or len(ans)!=0:
                ans.append(True)
                return 
        
            #print(cnt==len_str)
            isvisited[i][j]=True
            for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
                if 0<=x<len(board) and 0<=y<len(board[0]) and not isvisited[x][y]:
                    try:
                        if board[x][y]==word[cnt]:
                            dfs(cnt+1,x,y)
                    except:
                        print(cnt,x,y)
            isvisited[i][j]=False
        for i in range(len(board)):
            for j in range(len(board[0])):
                if board[i][j]==word[0]:
                    dfs(1,i,j)
                    if len(ans)!=0:
                        return True
        return False

不加剪枝过不了，加了一个简单的剪枝之后