2020-2-19 刷题记录

0X00 leetcode 做了 6 道

• Leetcode 501. Find Mode in Binary Search Tree
• Leetcode 746. Min Cost Climbing Stairs
• Leetcode 1137. N-th Tribonacci Number
• Leetcode 303. Range Sum Query - Immutable
• Leetcode 1218. Longest Arithmetic Subsequence of Given Difference
• Leetcode 53. Maximum Subarray

0X01 每道题的小小总结

首先今天难题做的不多,大多数是简单题,算是开了 DP 的坑了

501. Find Mode in Binary Search Tree

这道题...虽然看着我用 inorder 去做的,但是和 inorder 并没有多大关系 水过

class Solution:
    def findMode(self, root: TreeNode) -> List[int]:
        self.recoder = {}
        self.max = 1

        def inorder(root):
            if root is None: return
            inorder(root.left)
            if root.val not in self.recoder:
                self.recoder[root.val] =  1
            else:
                self.recoder[root.val] += 1
                self.max = max(self.recoder[root.val], self.max)
            inorder(root.right)

        inorder(root)

        ans = []

        for k in self.recoder.keys():
            if self.recoder[k] == self.max:
                ans.append(k)
        return ans

746. Min Cost Climbing Stairs

开动态规划的坑了,花花的动态规划的题目还是很多的,好好做

这个上楼梯的问题

dp(n) = min(dp(n-1), dp(n-2)) + cost

但是这个题的最后一层没有花费所以直接返回 min(dp(n-1), dp(n-2)) 而且是自底向上

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        # 自底向上
        # 写出 dp 公式
        # dp(n) = min(dp(n-1), dp(n-2)) + cost[n]

        dp1 = cost[0]
        dp2 = cost[1]

        for i in range(2, len(cost), 1):
            dp_n = min(dp1, dp2) + cost[i]
            dp1, dp2 = dp2, dp_n
        
        return min(dp1, dp2)

1137. N-th Tribonacci Number

这个题就更简单了...直接写出

T(n) = T(n-1) + T(n-2) + T(n-3)

class Solution:
    def tribonacci(self, n: int) -> int:
        memory = [0, 1, 1]
        if n < 3:
            return memory[n]
        
        ans = 0
        for i in range(3, n+1):
            t = sum(memory)
            memory[0], memory[1], memory[2] = memory[1], memory[2], t 
        
        return memory[2]

303. Range Sum Query - Immutable

这道题还是很有意思的,我已开始以为是「线段树」但是看了解答觉得解答还是非常的牛逼的

其实就用到一条

sum[i, j] = sum[j] - sum[i-1] (i > 0)

class NumArray:

    def __init__(self, nums: List[int]):
        if len(nums) <= 0: return
        self.sums = [x for x in nums]

        for i in range(1, len(nums)):
            self.sums[i] = self.sums[i-1] + nums[i] 


    def sumRange(self, i: int, j: int) -> int:
        if i == 0:
            return self.sums[j]
        return self.sums[j] - self.sums[i-1]

1218. Longest Arithmetic Subsequence of Given Difference

这道题也很牛逼,,,以为我完全不会做...看了解答觉得很巧妙,

像这种在序列中找等差数列的这类题应该都是「这种模板」

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        visited = {}
        for i in arr:
            if i - difference in visited:
                visited[i] = visited[i - difference] + 1
            else:
                visited[i] = 1
        return max(visited.values())

53. Maximum Subarray

这道题用动态规划做还是很巧秒的,从 0 开始遍历寻找不超过每个元素的最大子串

• 如果上一次的子串和小于 0 那么我肯定不加上一位的 这一位的最大就是自己
• 反之就加上

很巧妙

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 包括自己的最大子串
        f = [x for x in nums]

        for i in range(1, len(f)):
            f[i] = f[i] if f[i-1] < 0 else f[i] + f[i-1]

        return max(f)

明天继续做「动态规划」,加油!