leetcode做题记录

目录

• 动态规划：不同的子序列

• 优先队列：最大平均通过率

• 先进后出：逆波兰表达式求值

• 递归解决：杨辉三角，扁平化嵌套列表迭代器(深度优先)，删除排序链表中的重复元素

• 链表操作: 旋转链表

• 排序比较: 最大数

• 115. 不同的子序列

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        
        len_row = (len(t))+1
        len_col = (len(s))+1
        dp = [[0] * len_col for _ in range(len_row)]
        ## 初始化 dp[0][j] = 1
        for j in range(len_col):
            dp[0][j] = 1
        
        ## 字符串跟数组是不对应的
        ## 从行遍历
        for i in range(1, len_row):
            ## 从左到右遍历
            for j in range(1, len_col):
                if t[i-1] == s[j-1]:
                    dp[i][j] = dp[i-1][j-1] + dp[i][j-1]
                elif t[i-1] != s[j-1]:
                    dp[i][j] = dp[i][j-1]
        
        return dp[-1][-1]

• 最大平均通过率

class Solution:
    def maxAverageRatio(self, classes: List[List[int]], extraStudents: int) -> float:
        ## 优先队列
        ## 每次的增加量
        diff = lambda x, y: (x+1)/(y+1) - x/y
        res  = 0.
        q    = []
        for x, y in classes:
            res += x/y
            q.append((-diff(x,y), x, y))  ## 以增量为记录值
        
        heapq.heapify(q)

        for _ in range(extraStudents):
            d, x, y = heapq.heappop(q) ## 弹出最小值，也就是最大值
            res += -d ## 加入增量, 负数
            heapq.heappush(q, (-diff(x+1, y+1), x+1, y+1)) ## 更新优先队列

        return res/len(classes)

• 150. 逆波兰表达式求值 优先队列

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        if len(tokens) == 1:
            return int(tokens[0])
        import queue
        q_num = queue.LifoQueue(10000)
        def foo(var, x, y):
            #print(var)
            #print(x,y)
            return {
            '+': lambda x,y: x+y,
            '-': lambda x,y: y-x,
            '*': lambda x,y: x*y,
            '/': lambda x,y: int(y/x), 
            }[var](x,y)

        for i in tokens:
            if (i.startswith('-') and i[1:] or i).isdigit():
                q_num.put(int(i))
            else:
                res = foo(i, q_num.get(), q_num.get())
                q_num.put(res)
        return res
                

• 119. 杨辉三角 II, 递归方法解决

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        import functools

        if rowIndex == 0:
            return [1]

        @functools.lru_cache()
        def helper(k):
            if k == 1:
                return [1,1]
            else:
                list1 = [1]
                list0 = helper(k-1)
                for i in range(len(list0)-1):
                    list1.append(list0[i]+list0[i+1])
                list1.append(1)
                return list1
        
        res = helper(rowIndex)
        return res

• 191. 位1的个数， 字符串记录频数Counter用法

class Solution:
    def hammingWeight(self, n: int) -> int:
        from collections import Counter
        a = str(bin(n))
        list0 = Counter(a)
        if '1' in list0:
            return list0['1']
        else:
            return 0

• 341. 扁平化嵌套列表迭代器

class NestedIterator:    
    def __init__(self, nestedList: [NestedInteger]):
        self.queue = []
        ## 深度优先搜索
        def dfs(nestedList):
            for item in nestedList:
                ## 如果是数字
                if item.isInteger():
                    self.queue.append(item.getInteger())
                ## 如果是list，继续递归
                else:
                    dfs(item.getList())
        dfs(nestedList)
    
    ## 记得是pop(0) 默认最后一个元素
    def next(self) -> int:
        return self.queue.pop(0)

    def hasNext(self) -> bool:
        return len(self.queue)

• 82. 删除排序链表中的重复元素 II

class Solution(object):
    def deleteDuplicates(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        ## 如果是空
        if not head or not head.next:
            return head
        ## 重新更新next值
        if head.val != head.next.val:
            ## 这里面用next，因为head没有变化
            head.next = self.deleteDuplicates(head.next)
        else:
            ## 跳过相同的值，保证下一个next不等于move
            move = head.next
            while move and head.val == move.val:
                move = move.next
            ## 返回新的move，这里面是递归
            return self.deleteDuplicates(move)
        return head

• 旋转链表

class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        tail = head   
        len1 = 1
        while tail and tail.next:
            len1+=1
            ## 记录最后一个指针
            tail = tail.next

        ## 当元素<=1或者k为0，不需要挪动
        if len1 <= 1 or k == 0:
            return head

        tail.next = head ## 进行闭环

        ## 重新确定要挪动的位置
        k = k%len1
        
        ## 重新构建
        k0 = len1 - k 
        index = 0
        while head:
            index +=1
            if index == k0:
                newHead = head.next
                head.next = None
            head = head.next

        ## 重新结合
        return newHead

• 最大数, 学会自己做排序的函数

class Solution:
    def largestNumber(self, nums: List[int]) -> str:

        ## 自定义排序, python2 跟python3有很大的区别
        from functools import cmp_to_key
        compare = lambda x, y: int(y+x) - int(x+y) 
        
        ## 变成字符串
        nums_str =  list(map(str, nums))
        nums_str.sort(key=cmp_to_key(compare))
        res = "".join(nums_str)
        if res[0] == '0':
            res = '0'
        
        return res