Brush question 6

23、 climb stairs

Suppose you're climbing the stairs . need n You can reach the top of the building . Every time you climb 1 or 2 A stair . How many different ways can you climb to the top of the building ？ Be careful ： Given n Is a positive integer

class Solution(object):
    def climbStairs(self, n):
        if n < 2:
            return n
        dp = [1 for __ in range(n)]  
        dp[1] = 2
        for i in range(2, n):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[-1]

26、 Gray code

Gray coding is a binary digital system , In this system , There is only one digit difference between two consecutive values . Given a non negative integer representing the total number of bits encoded n, Print its gray code sequence . Gray coding sequence must be in 0 start .

class Solution: 
    def grayCode(self, n: int) -> List[int]: 
        res = [] 
        for i in range(2 ** n): 
            res.append((i >> 1) ^ i) 
        return res

33、 Circular list

Given a linked list , Return to the first node of the link where the list begins to enter . If the list has no links , Then return to null. To represent a ring in a given list , We use integers pos To indicate where the end of the list is connected to the list （ Indexes from 0 Start ）. If pos yes -1, There are no links in the list . explain ： It is not allowed to modify the given linked list .

def hasCycle(self, head):

     if head == None or head.next == None:

         return False

     first = second = head

     while second and second.next:

    first = first.next

     second = second.next.next

     if first == second:

         return True

    return False