【日常】2022年3月21日 - 2022年3月27日

700. 二叉搜索树中的搜索

传送门

比较简单，递归和迭代都可以。

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root: return None
        if root.val == val: return root

        if root.val < val: return self.searchBST(root.right, val)
        if root.val > val: return self.searchBST(root.left, val)

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        if not root: return

        while root:
            if root.val == val: return root
            if root.val < val: root = root.right
            elif root.val > val: root = root.left
        
        return 

98. 验证二叉搜索树

传送门

可能会想使用递归，每次判断该节点的左节点是不是比根节点小，右节点是不是比根节点大，但是这种情况忽略了子节点的右节点可能比子节点大，但是不一定比根节点小。

而二叉搜索树的特性是：使用中序遍历得到的是一个递增序列。

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        nums = []
        def traversal(root):
            if not root: return
            traversal(root.left)
            nums.append(root.val)
            traversal(root.right)

        traversal(root)
        for i in range(1, len(nums)):
            if nums[i] <= nums[i-1]: return False
        return True

530. 二叉搜索树的最小绝对差

传送门

只要遇到二叉搜索树，首先要想到中序遍历的结果是一个有序数组，然后对有序数组进行判断，会方便很多。但是这种做法不一定是最优的，不过总比写不出来要强。

class Solution:
    def getMinimumDifference(self, root: TreeNode) -> int:
        # 找树中任意两个不同节点的最小值
        if not root: return

        nums = []
        def traversal(root):
            if not root: return
            traversal(root.left)
            nums.append(root.val)
            traversal(root.right)
        
        traversal(root)
        res = float('inf')
        for i in range(1, len(nums)):
            res = min(res, nums[i]-nums[i-1])
        
        return res

501. 二叉搜索树中的众数

传送门

先来一个笨方法，统计每个数的频率，之后再排序。

class Solution:
    def findMode(self, root: TreeNode) -> List[int]:
        if not root: return
        dic = collections.defaultdict(int)

        def traversal(root):
            if not root: return
            traversal(root.left)
            dic[root.val] += 1
            traversal(root.right)
        
        traversal(root)
        dic = sorted(dic.items(), key=lambda x: x[1], reverse=True)

        res = []
        pre = 0
        for i, (k, v) in enumerate(dic):
            if i == 0:
                pre = v
                res.append(k)
            elif pre == v:
                res.append(k)
        return res

236. 二叉树的最近公共祖先

传送门

比较难，可以再理解理解。

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 如果节点为空，或者节点等于p或者q，就返回
        if not root or root == p or root == q:
            return root
        
        left = self.lowestCommonAncestor(root.left, p, q)  # 看看左子树有没有pq，返回的是找到的话的节点
        right = self.lowestCommonAncestor(root.right, p, q)

        # 如果left和right都不为空，说明pq分别在左右子树，此时root就是最近的公共祖先
        if left and right:
            return root
        # 如果只有left不为空，说明右子树没有p和q，那么左子节点就是pq的最近公共祖先
        if left:
            return left
        else:
            return right

235. 二叉搜索树的最近公共祖先

传送门

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        # 如果root小于p和q，说明pq只可能在右子树
        if root and root.val < p.val and root.val < q.val:
            return self.lowestCommonAncestor(root.right, p, q)
        # 如果root大于p和q，说明pq只可能在左子树
        if root and root.val > p.val  and root.val > q.val:
            return self.lowestCommonAncestor(root.left, p, q)
        # 如果root的值在pq之间，说明pq分别位于左右子树，此时root就是最近的公共祖先
        return root

79. 单词搜索

传送门

好几天没做回溯算法了，这一题和之前的回溯还不太一样，所以做的比较难。

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m = len(board)
        n = len(board[0])
        n_word = len(word)

        
        def backtrack(i, j, p):
            if p == n_word:
                return True
            if i < 0 or i >= m or j < 0 or j >= n: return False

            if board[i][j] == word[p]:
                board[i][j] = '0'
                if backtrack(i-1, j, p+1) or backtrack(i+1, j, p+1) or backtrack(i, j-1, p+1) or backtrack(i, j+1, p+1):
                    return True
                board[i][j] = word[p]   # 撤销操作

            return False

        for i in range(len(board)):
            for j in range(len(board[0])):
                if word[0] == board[i][j]:
                    if backtrack(i, j, 0): return True
        return False

这个做法是一个比较暴力的方法，遍历每一个字母，然后以该字母为开头遍历上下左右四个字母，很明显复杂度高。执行起来要好三四千ms，不过也能超过很大一部分python用户。

下面是一个时间效率很高的代码，但是占用空间稍微多一点。其中有一个哈希表，但是具体用法还没看明白。

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:

        def backtracking(r, c, step=0):
            if step == len(word):  return True
            if 0 <= r < m and 0 <= c < n and board[r][c] == word[~step] and (
                    r, c) not in visited:
                visited.add((r, c))
                HashMap[(r, c, step)] += 1
                for nr, nc in (r, c + 1), (r, c - 1), (r - 1, c), (r + 1, c):
                    if HashMap[(nr, nc, step + 1)] < n:
                        if backtracking(nr, nc, step + 1):
                            return True
                visited.remove((r, c))
                return False

        m, n = len(board), len(board[0])
        visited, HashMap = set(), collections.defaultdict(int)  # hashmap记录每一个节点作为word中第step个元素被遍历的个数
                
        for i, j in itertools.product(range(m), range(n)):  # 等价于两层for循环
            if backtracking(i, j):
                return True
        return False

376. 摆动序列

传送门

注意这一题并不是说要连续才算子序列，而是只要保持原数组的相对顺序即可。这样的话就可以只统计当前差分和前面差分之间的关系了。而不需要在判断如果摆动中断怎么办。

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        res = 1
        preDiff, curDiff = 0, 0
        
        for i in range(len(nums)-1):
            curDiff = nums[i+1] - nums[i]
            # s
            # if (curDiff > 0 and preDiff <= 0) or (curDiff < 0 and preDiff >= 0):
            if curDiff * preDiff <= 0 and curDiff != 0:   # 这两个判断条件都可以，当前差值为0，不算摆动
                res += 1
                preDiff = curDiff     # 当前差值不为0切与前一个差值符号相反，此时满足条件，也将preDiff更新
        
        return res

53. 最大子数组和

传送门

非常简单的贪心算法

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res = -float('inf')
        cur = 0

        for i in range(len(nums)):
            cur = max(nums[i] + cur, nums[i])
            res = max(cur, res)
        
        return res

122. 买卖股票的最佳时机 II

传送门

有两种方法：贪心和动态规划

贪心：因为可以无限买卖，所以只要后一天的价格高于今天，那么我就可以赚到这个差价。于是，直接把所有的差价都赚了。就得到最大收益了。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 因为可以多次买卖股票，所以只要第二天的价格高于前一天的价格，那么这个差价我就是可以赚到的
        res = 0
        for i in range(len(prices)-1):
            if prices[i+1] > prices[i]:
                res += prices[i+1] - prices[i]
        
        return res

动态规划：第k天的最大收益等于第k-1天的收益加上今天比昨天高的价格，如果今天价格降了，那么最大收益不变。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp = [0] * len(prices)
        
        for i in range(1, len(prices)):
            dp[i] = max(dp[i-1], dp[i-1] + prices[i] - prices[i-1])
        
        return dp[-1]

下面这个是二维dp数组的解法，对于这题来说比较麻烦，但是可以更好的理解dp的思想。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)

        dp = [[0] * 2 for _ in range(n)]
        dp[0][0] = -prices[0]

        for i in range(1, n):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i])
            dp[i][1] = max(dp[i-1][1], prices[i]+dp[i-1][0])

        return dp[-1][1]

55. 跳跃游戏

传送门

也不算难的一道题。

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # 只需要知道最远覆盖距离是否大于nums长度
        cover = 0
        for i, jump in enumerate(nums):
            if cover >= i and i + jump >= cover:
                # 第一个条件是防止陷入某一个位置跳不出去
                # 第二个条件是判断当前位置能跳的最远距离是不是大于当前能跳的最远距离
                cover = i + jump
        
        return cover >= i  # 当循环结束，i=n-1，就看cover能不能覆盖n-1

45. 跳跃游戏 II

传送门

贪心

class Solution:
    def jump(self, nums: List[int]) -> int:
        # 贪心思想，
        if len(nums) == 1: return 0
        res = 0
        curDistance = 0
        nexDistance = 0


        for i in range(len(nums)):
            nexDistance = max(i+nums[i], nexDistance)
            if i == curDistance:
                if curDistance != len(nums) - 1:
                    res += 1
                    curDistance = nexDistance
                    if curDistance == len(nums) - 1: break
                else:
                    break
        return res

1005. K 次取反后最大化的数组和

传送门

使用堆是一个比较简单的方法。

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        # 只需要每次将最小的数字进行取反即可，但是取反之后还要排序，每次排序会耗时，所以使用堆
        heap = []
        for num in nums:
            heapq.heappush(heap, num)

        # 最小堆构建完成
        # 取反
        for _ in range(k):
            num = heapq.heappop(heap)
            heapq.heappush(heap, -num)
        
        # 统计总和
        return sum(heap)

除了使用堆，还可以使用其他的方法，贪心法。
步骤如下：

• 将所有数字按照绝对值进行排序
• 从前往后遍历，遇到负数就取反，同时k-1
• 如果所有负数都取反之后，k还大于0，那么反复转变数值最小的元素，直到k为0
• 求和

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        # 按照绝对值进行从大到小排序
        nums = sorted(nums, key=abs, reverse=True)

        for i in range(len(nums)):
            if nums[i] < 0 and k > 0:
                nums[i] = -nums[i]
                k -= 1
        # 如果k是非零偶数，此时已经没有负数了，所以总和不可能再大了。为了保持最大，可以随便对一个数字取反再取反，偶数次刚好用完
        # 也就是相当于不需要取反了
        if k % 2 == 1:
            # 如果剩余k为奇数，那么其实相当于偶数+1，偶数可以忽略。那么就只需要再取反1次就可以了，因为这时候已经没有负数了，必须对
            # 正数进行取反了，那么就对最小的整数进行取反
            nums[-1] = -nums[-1]  
        return sum(nums)

134. 加油站

传送门
暴力解法：

• 以每一个加油站作为起点，看看能不能转一圈
• 注意：如果有一个能走到j == n的位置，代表确实能走一圈

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # 从某一个加油站出发可以环绕所有加油站一圈，这个解是唯一的。于是很容易想到两层循环，
        # 第一层用来以每个加油站作为起点，第二层用来看能不能转一圈

        for i in range(len(gas)):
            # 如果当前加油站作为起点的油都不够到下一站
            if gas[i] < cost[i]:
                continue
            left = 0
            tmp_gas = gas[i:] + gas[:i] 
            tmp_cost = cost[i:] + cost[:i]

            j = 0
            while j < len(cost):
            # for j in range(len(tmp_cost)):
                if left + tmp_gas[j] >= tmp_cost[j]:
                    left = left + tmp_gas[j] - tmp_cost[j]
                    j += 1
                else:
                    break
            # 车走到最后一个位置并不代表能够回到开头,只有等于n才可以
            if j == len(cost):
                return i
        return -1

很遗憾，python的暴力解法会超时。

同时上面的代码还有一点就是每次都生成两个新数组，其实是可以使用while循环来进行环形便利的。

使用while循环进行环形遍历的方法如下：

for i in range(len(cost)):
	j = i + 1
	while j != i:
		j = (j + 1) % len(cost)

改进过的写法如下：

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # 从某一个加油站出发可以环绕所有加油站一圈，这个解是唯一的。于是很容易想到两层循环，
        # 第一层用来以每个加油站作为起点，第二层用来看能不能转一圈

        for i in range(len(gas)):
            # 如果当前加油站作为起点的油都不够到下一站
            if gas[i] < cost[i]:
                continue
            left = gas[i] - cost[i]
            j = (i + 1) % len(cost)
            while left > 0 and j != i:
                left = left + gas[j] - cost[j]
                j = (j + 1) % (len(cost))

            # 车走到最后一个位置并不代表能够回到开头,只有等于n才可以
            if j == i and left >= 0:
                return i
        return -1

但是还是会超时。

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        start = 0
        cur_sum = total_sum = 0

        for i in range(len(cost)):
            cur_sum += gas[i] - cost[i]
            total_sum += gas[i] - cost[i]
            # 如果当前加油站
            if cur_sum < 0:
                cur_sum = 0
                start = i + 1 
        if total_sum < 0:
            return -1
        return start

860. 柠檬水找零

传送门

不是很难，模拟就行了。

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        # 使用一个字典维护每种钱的个数，每次优先找零大的钱
        # 比如别人给20，有优先给他10+5，而不是5+5+5
        if bills[0] > 5:
            return False
        
        money = collections.defaultdict(int)

        for i in range(len(bills)):
            if bills[i] == 5:
                money[5] += 1
            elif bills[i] == 10:
                if money[5] == 0:
                    return False
                else:
                    money[10] += 1
                    money[5] -= 1
            elif bills[i] == 20:
                # 优先找10块钱的
                if money[10] > 0 and money[5] > 0:
                    money[10] -= 1
                    money[5] -= 1
                    money[20] += 1
                elif money[5] >= 3:
                    money[5] -= 3
                    money[20] += 1
                else:
                    return False
        return True