手撕代码练习

手撕代码

递归

70. 爬楼梯

动态规划$f(x) = f(x-1)+f(x-2)$

class Solution:
    def climbStairs(self, n: int) -> int:
        a = 1
        b = 2
        if n<=1:
            return a
        for i in range(n-2):
            sum = a + b
            a = b
            b = sum
        return b

112. 路径总和

递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        if not root.left and not root.right :
            return targetSum-root.val == 0
        return self.hasPathSum(root.left,targetSum-root.val) or self.hasPathSum(root.right, targetSum-root.val)

509. 斐波那契数

class Solution:
    def fib(self, n: int) -> int:
        a = 0
        b = 1 
        if n < 2:
           return n
        for i in range(n-1):
            sum = a + b
            a = b
            b = sum
        return b

分治

23. 合并k个升序链表

用分治的方法进行合并。

• 将 $k$ 个链表配对并将同一对中的链表合并；
• 第一轮合并以后， $k$ 个链表被合并成了 $\frac{k}{2} $个链表，平均长度为 $\frac{2n}{k} $ ，然后是 $\frac{k}{4} $个链表， $\frac{k}{8} $个链表等等；
• 重复这一过程，直到我们得到了最终的有序链表。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        return self.merge(lists,0,len(lists)-1)
    
    def mergeTwoLists(self, a, b):
        if not a or not b:
            return a if a else b
        head,tail = ListNode(), ListNode()
        tail = head
        while(a and b):
            if(a.val<b.val):
                tail.next = a
                a = a.next
            else:
                tail.next =b
                b = b.next
            tail = tail.next
        tail.next = a if a else b
        return head.next
                
    def merge(self, lists, l ,r):
        if(l ==r): return lists[l]
        if(l > r): return None
        mid = (l + r)//2
        return self.mergeTwoLists( self.merge(lists, l, mid), self.merge(lists, mid + 1, r));

169. 多数元素

本题仍然是使用分治算法

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

        return self.majorityElementRec(nums,0,len(nums)-1)

    def majorityElementRec(self,nums, l, r):
        if l == r :
            return nums[l]
        mid = (l+r)//2
        
        left = self.majorityElementRec(nums,l,mid)
        right = self.majorityElementRec(nums,mid+1,r)

        if (left == right):
            return left
        leftCount = sum(1 for i in range(l, r+1) if nums[i] == left)
        rightCount = sum(1 for i in range(l, r+1) if nums[i] == right)
        
        return left if leftCount > rightCount else right

一种时间复杂度更高效的方法是使用 Boyer-Moore 投票算法，Boyer-Moore 投票算法的基本思想是维护一个候选元素和一个计数器，遍历数组中的每个元素进行投票，以确定可能的多数元素。

该算法类似于游戏中的“战斗”，每次遇到与 candidate 相同的元素时，它的“生命值”（count）就增加，当遇到不同的元素时，就减少。如果 count 降到 0，意味着当前的 candidate 被“打败”了，需要选择新的 candidate。由于多数元素的数量超过一半，所以最后能存活下来的 candidate 必然是多数元素。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        candidate = None
        count = 0

        for num in nums:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)

        count = 0
        for num in nums:
            if num == candidate:
                count += 1
        if count > len(nums) // 2:
            return candidate
        return -

二分查找

240. 搜索二维矩阵Ⅱ

由于是有序矩阵，可以使用在二维上的二分查找算法

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # 二维的二分查找
        m,n=len(matrix),len(matrix[0])
        for i in range(m):
            left,right=0,n-1
            while left<=right:
                mid=(left+right)//2
                if matrix[i][mid]>target:right=mid-1
                elif matrix[i][mid]<target:left=mid+1
                else:return True
        return False

当然我们也可以使用贪心算法

class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        i, j = len(matrix) - 1, 0
        while i >= 0 and j < len(matrix[0]):
            if matrix[i][j] > target: i -= 1
            elif matrix[i][j] < target: j += 1
            else: return True
        return False

单调栈

单调栈的核心特点是，它按照单调增或单调减的顺序来维护栈内元素。这样的特性对于很多问题来说非常有用，因为它可以在一次遍历内完成对元素的处理，大大提高效率。

假设单调栈按单减顺序存储

• 每次越到比栈顶小的数则存入栈

• 遇到比栈顶大的数，则弹栈直到栈顶比该数大，然后入栈

适合解决数组中离某元素最近的最大/最小元素这类问题

84. 柱状图中最大的矩形

矩形的宽度是由柱子左侧和右侧最近的比它矮的柱子决定的。这是因为：

• 左边界：只有当你知道左边第一个不支持当前高度（即高度小于当前柱子）的柱子在哪里时，你才能确定当前柱子能向左扩展到哪里。如果左侧的柱子比当前柱子高或等高，那么它们可以支持至少与当前柱子同样的矩形高度，因此不会成为限制当前柱子向左扩展的边界。
• 右边界：同理，右边界的确定也依赖于找到第一个高度小于当前柱子的柱子。这个位置标志着当前柱子能向右扩展的极限。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        left = [-1] * n
        st = []
        for i , x in enumerate(heights):
            while st and x<= heights[st[-1]]:
                st.pop()
            if st:
                left[i] = st[-1]
            st.append(i)
            
        right = [n] * n
        st.clear()
        for i in range(n - 1, -1, -1):
            x = heights[i]
            while st and x <= heights[st[-1]]:
                st.pop()
            if st:
                right[i] = st[-1]
            st.append(i)

        ans = 0
        for h, l, r in zip(heights, left, right):
            ans = max(ans, h * (r - l - 1))
        return ans

优化一下本题代码，因为我们没有必要把左右边界都搜索一遍

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        r = [0]
        st = []
        heights = [0] + heights + [0]
        for i, h in enumerate(heights):
            while st and h < heights[st[-1]]:
                a = st.pop()
                if st:
                    hi = heights[a]
                    r.append((i - st[-1] - 1) * (hi))
            st.append(i)
        return max(r)

85. 最大矩阵

这一题是84题的升级版，我们可以遍历每一行，分别找出最大柱状图面积

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        r = [0]
        st = []
        heights = [0] + heights + [0]
        for i, h in enumerate(heights):
            while st and h < heights[st[-1]]:
                a = st.pop()
                if st:
                    hi = heights[a]
                    r.append((i - st[-1] - 1) * (hi))
            st.append(i)
        return max(r)

    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        m,n=len(matrix),len(matrix[0])
        heights = [0]*n
        ans = 0
        for row in matrix:
            for i,c in enumerate(row):
                heights[i]=0 if c=='0' else heights[i]+1
            if self.largestRectangleArea(heights)>ans: ans = self.largestRectangleArea(heights)
        return ans

739. 每日温度

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        right = [0]*n
        st = []
        for i in range(n-1,-1,-1):
            while st and temperatures[i]>= temperatures[st[-1]]:
                st.pop()
            if st:
                right[i] = st[-1] - i
            st.append(i)

        return right

503. 下一个更大元素Ⅱ

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

本题求出单调栈即可，需要注意的是循环数组要遍历两遍

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        st = []
        lnum = n*[-1]
        for i in range(n*2):
            while(st and nums[i%n]> nums[st[-1]]):
                lnum [st.pop()] = nums[i%n]
            st.append(i%n)
        return lnum

并查集

关于并查集的介绍可以看下面这篇文章

https://leetcode.cn/problems/number-of-provinces/solutions/550107/python-duo-tu-xiang-jie-bing-cha-ji-by-m-vjdr

547. 省份数量

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def find(index: int) -> int:
            if parent[index] != index:
                parent[index] = find(parent[index])
            return parent[index]
        
        def union(index1: int, index2: int):
            parent[find(index1)] = find(index2)
        
        cities = len(isConnected)
        parent = list(range(cities))
        
        for i in range(cities):
            for j in range(i + 1, cities):
                if isConnected[i][j] == 1:
                    union(i, j)
        
        provinces = sum(parent[i] == i for i in range(cities))
        return provinces

200. 岛屿数量

本题是一个很好的并查集样例

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def find(index):
            if parent[index] != index:
                parent[index] = find(parent[index])
            return parent[index]
        def union(index1,index2):
            root1 = find(index1)
            root2 = find(index2)
            if root1 != root2:
                if rank[root1] > rank[root2]:
                    parent[root2] = root1
                elif rank[root1] < rank[root2]:
                    parent[root1] = root2
                else:
                    parent[root2] = root1
                    rank[root1] += 1
        
        m = len(grid)
        n = len(grid[0])
        lands = m * n
        parent = list(range(lands))
        rank = [0] * lands

        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    for x,y in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
                        if 0<=x<m and 0<=y<n and grid[x][y] == "1":
                            union(i*n+j,x*n+y)
        islands = sum((parent[i] == i and grid[i//n][i%n] =="1") for i in range(lands))
        return islands

不过更推荐使用深度优先算法来解决本题

class Solution:
    def dfs(self, grid, r, c):
        grid[r][c] = 0
        nr, nc = len(grid), len(grid[0])
        for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
            if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
                self.dfs(grid, x, y)

    def numIslands(self, grid: List[List[str]]) -> int:
        nr = len(grid)
        if nr == 0:
            return 0
        nc = len(grid[0])

        num_islands = 0
        for r in range(nr):
            for c in range(nc):
                if grid[r][c] == "1":
                    num_islands += 1
                    self.dfs(grid, r, c)
        
        return num_islands

使用栈迭代而非递归可以进一步优化空间复杂度

class Solution:
    def dfs(self, grid, r, c):
        grid[r][c] = 0
        nr, nc = len(grid), len(grid[0])
        for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
            if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
                self.dfs(grid, x, y)

    def numIslands(self, grid: List[List[str]]) -> int:
        nr = len(grid)
        if nr == 0:
            return 0
        nc = len(grid[0])

        num_islands = 0
        for r in range(nr):
            for c in range(nc):
                if grid[r][c] == "1":
                    num_islands += 1
                    stack = [(r, c)]
                    while stack:
                        cr, cc = stack.pop()
                        grid[cr][cc] = "0"
                        for x, y in [(cr - 1, cc), (cr + 1, cc), (cr, cc - 1), (cr, cc + 1)]:
                            if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
                                stack.append((x, y))
        
        return num_islands

684. 冗余连接

需要注意的是本题节点的标号从1开始

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:

        def find(index):
            if parent[index] != index:
                parent[index] = find(parent[index])
            return parent[index]
        def union(index1,index2):
            root1 = find(index1)
            root2 = find(index2)
            if root1 != root2:
                parent[root1] = root2
                return False
            return True

        n = len(edges)
        parent = list(range(n))
        for fr,to in edges:
            if union(fr,to):
                return [fr,to]

题目中所说的edges 中最后出现的那个，其实就是这两个点的连线

滑动窗口

209. 长度最小的子数组

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        
        start = end = 0
        n = len(nums)
        minLen = n+1
        sum = 0
        while end<n:
            sum += nums[end]
            while sum>= target:
                minLen = min(minLen,end - start +1)
                sum -= nums[start]
                start += 1   
            end += 1
        return 0 if minLen == n+1 else minLen

for循环的时间复杂度要小于while循环

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        
        start = end = 0
        minLen = len(nums)+1
        sum = 0
        for end in range(len(nums)):
            sum += nums[end]
            while sum>= target:
                minLen = min(minLen,end - start +1)
                sum -= nums[start]
                start += 1   
        return 0 if minLen == len(nums)+1 else minLen

3. 无重复字符的最长子串

本题使用了哈希表作为窗口，用于快速查找是否存在重复元素

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:return 0
        left = 0
        lookup = set()
        max_len = 0
        cur_len = 0
        for i in range(len(s)):
            cur_len += 1
            # 当出现重复字符，清空窗口
            while s[i] in lookup:
                lookup.remove(s[left])
                left += 1
                cur_len -= 1
            if cur_len > max_len:max_len = cur_len
            lookup.add(s[i])
        return max_len

前缀和

724. 寻找数组的中心下标

class Solution:
    def pivotIndex(self, nums: List[int]) -> int:
        total = sum(nums)
        sum_right = total
        for i in range(len(nums)):
            sum_right -= nums[i]
            sum_left = total - sum_right - nums[i]
            if sum_left == sum_right: return i
        return -1

560. 和为 K 的子数组

1. 初始化：
   • dic = {0: 1}：这是一个非常关键的初始化。这表示前缀和为 0 的情况有一个，这对于处理从数组开始到当前元素的和刚好为 k 的情况是必需的。
   • sums = 0：用来计算当前的前缀和。
   • res = 0：用来存储结果，即和为 k 的子数组的数量。
2. 遍历数组：
   • 对于每个元素 num，首先更新当前的前缀和 sums += num。
   • 接着检查 sums - k 是否已经在 dic 中出现过，因为如果出现过，说明存在一个 j，使得 pre[i] - pre[j] = k，这正是我们要找的和为 k 的子数组的结束点 i。dic.get(sums-k, 0) 会得到这种情况的次数，加到 res 上。
   • 最后，更新哈希表以包含当前的前缀和的出现次数，即 dic[sums] = dic.get(sums, 0) + 1。

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:

       # pre[i]−pre[j−1]==k
        dic={0:1}
        sums,res=0,0
        for num in nums:
            sums+=num
            res+=dic.get(sums-k,0)
            dic[sums]=dic.get(sums,0)+1
        return res

差分

队列有入有出的题目适合差分数组

1094. 拼车

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:

        to_max = max(trip[2] for trip in trips)
        diff = [0]*(to_max+1)

        for num_i, from_i, to_i in trips:
            diff[from_i] += num_i
            diff[to_i] -= num_i
        count = 0
        for i in range(to_max+1):
            count += diff[i]
            if count > capacity:
                return False
        return True

121.卖卖股票的最佳时机

动态规划加差分数组

• 如果 max_here > 0，则说明 max_here 对截止当前元素的结果有增益效果，则 max_here 保留并加上当前遍历数字
• 如果 max_here <= 0，则说明 max_here 对截止当前元素的结果无增益效果，需要舍弃，则将 max_here 直接更新为当前遍历数字

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 0:
            return 0
        prev = prices[0]
        max_profit = 0
        for t in prices[1:]:
            max_profit += (t - prev) if t > prev else 0
            prev = t
        return max_profit

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

累加差分数组中的所有正值即可

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

拓扑排序

210. 课程表

本题可以将课程看为有向图，某个课程在另一个课程前，则可以构造一条有向边

如果有环存在则不能构建课程表

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        # 存储有向图
        edges = [[] for _ in range(numCourses)]
        # 标记每个节点的状态：0=未搜索，1=搜索中，2=已完成
        visited = [0] * numCourses
        # 用数组来模拟栈，下标 0 为栈底，n-1 为栈顶
        result = list()
        # 判断有向图中是否有环
        valid = True

        for info in prerequisites:
            edges[info[1]].append(info[0])
        
        def dfs(u: int):
            nonlocal valid
            # 将节点标记为「搜索中」
            visited[u] = 1
            # 搜索其相邻节点
            # 只要发现有环，立刻停止搜索
            for v in edges[u]:
                # 如果「未搜索」那么搜索相邻节点
                if visited[v] == 0:
                    dfs(v)
                    if not valid:
                        return
                # 如果「搜索中」说明找到了环
                elif visited[v] == 1:
                    valid = False
                    return
            # 将节点标记为「已完成」
            visited[u] = 2
            # 将节点入栈
            result.append(u)
        
        # 每次挑选一个「未搜索」的节点，开始进行深度优先搜索
        for i in range(numCourses):
            if valid and not visited[i]:
                dfs(i)
        
        if not valid:
            return list()
        
        # 如果没有环，那么就有拓扑排序
        # 注意下标 0 为栈底，因此需要将数组反序输出
        return result[::-1]

字符串

5. 最长回文子串

使用中心扩展法，将每个字符作为潜在的回文中心

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expandAroundCenter(left: int, right: int):
            nonlocal longest  # 使用 nonlocal 关键字引用外部变量
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            current = s[left + 1:right]
            if len(current) > len(longest):
                longest = current

        if len(s) == 0:
            return ""

        longest = ""
        for i in range(len(s)):
            expandAroundCenter(i, i)     # 奇数长度回文串
            expandAroundCenter(i, i + 1) # 偶数长度回文串

        return longest

20. 有效的括号

简单的栈题

class Solution:
    def isValid(self, s: str) -> bool:
        st = []
        ldic = {'(':')','{':'}','[':']'}

        for c in s:
            if c in ldic:
                st.append(c)
            elif not st or ldic[st.pop()] != c:
                return False

        return not st

43. 字符串相乘

模拟乘法过程即可

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        # 先让长度最长的数字作为第一个乘数（减少乘积次数）
        if len(num2) > len(num1): num1, num2 = num2, num1
        # 让第一个乘数转化为整数
        int1 = 0
        for n in num1:
            int1 *= 10
            int1 += (ord(n) - ord('0'))
        # 然后乘法
        ans, mult = 0, 10
        for i, n in enumerate(num2[::-1]):
            coin = (ord(n) - ord('0'))
            ans += (coin * int1) * mult ** i
        
        return str(ans)

93. 复原IP地址

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:

        ans = []
        segments = [0] * 4

        def dfs(segId, segStart):
            if segId == 4:
                if segStart == len(s):
                    ans.append(".".join(str(seg) for seg in segments))
                return
            
            if segStart == len(s):
                return
            
            if s[segStart] == '0':
                segments[segId] = 0
                dfs(segId+1,segStart+1)
                return
            
            addr =0 
            #一般情况
            for segEnd in range(segStart,len(s)):
                addr = addr*10 + (ord(s[segEnd]) - ord("0"))
                if 0<addr<=0xFF:
                    segments[segId] = addr
                    dfs(segId+1, segEnd+1)
                else:
                    break
            

        dfs(0,0)
        return ans

二分查找

33. 搜索旋转排序数组

切为两半，那么其中一半必定为有序数组

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = (l + r) // 2
            if nums[mid] == target:
                return mid
            if nums[0] <= nums[mid]:
                if nums[0] <= target < nums[mid]:
                    r = mid - 1
                else:
                    l = mid + 1
            else:
                if nums[mid] < target <= nums[len(nums) - 1]:
                    l = mid + 1
                else:
                    r = mid - 1
        return -1

34. 在排序数组中查找元素的第一个和最后一个位置

本题可以简化为找到第一个大于等于某元素的位置和第一个大于某元素的位置-1

大于x可以看作为大于等于x+1

要记住我们每次查找都是在一个闭区间上

def lower_bound(nums: List[int], target: int) -> int:
    left, right = 0, len(nums) - 1  # 闭区间 [left, right]
    while left <= right:  # 区间不为空
        # 循环不变量：
        # nums[left-1] < target
        # nums[right+1] >= target
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1  # 范围缩小到 [mid+1, right]
        else:
            right = mid - 1  # 范围缩小到 [left, mid-1]
    return left  # 或者 right+1
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        start = lower_bound(nums, target)  # 选择其中一种写法即可
        if start == len(nums) or nums[start] != target:
            return [-1, -1]
        # 如果 start 存在，那么 end 必定存在
        end = lower_bound(nums, target + 1) - 1
        return [start, end]

BFS

双端列表deque比较适合在BFS算法中使用

139. 单词拆分

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        word_set = set(wordDict)
        queue = deque([0])
        visited = set()

        while queue:
            start = queue.popleft()
            if start in visited:
                continue
            for end in range(start + 1, len(s) + 1):
                if s[start:end] in word_set:
                    if end == len(s):
                        return True
                    queue.append(end)
            visited.add(start)

        return False

DFS&回溯

934. 最短的桥

使用显示栈来进行DFS而非递归，可以降低空间复杂度

class Solution:
    def shortestBridge(self, grid: List[List[int]]) -> int:
        
        def dfs(x,y):
            stack = [(x,y)]
            while stack:
                x, y = stack.pop()
                if grid[x][y] == -1:
                    continue
                grid[x][y] = -1
                q.append((x, y))
                for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):
                    if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 1:
                        stack.append((nx, ny))

        n = len(grid)
        q = deque()
        i, j = next((i, j) for i in range(n) for j in range(n) if grid[i][j]==1)
        dfs(i,j)
        ans = 0
        while q:
            for _ in range(len(q)):
                i, j = q.popleft()
                for nx, ny in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):
                    if 0 <= nx < n and 0 <= ny < n:
                        if grid[nx][ny] == 1:
                            return ans
                        if grid[nx][ny] == 0:
                            grid[nx][ny] = -1
                            q.append((nx, ny))
            ans +=1

动态规划

213. 打家劫舍Ⅱ

转移方程：$ dp[n+1]=max(dp[n],dp[n−1]+num)$

由于是环形，我们可以考虑两种情况：排除第一家、排除最后一家

class Solution:
    def rob(self, nums: [int]) -> int:
        def my_rob(nums):
            cur, pre = 0, 0
            for num in nums:
                cur, pre = max(pre + num, cur), cur
            return cur
        return max(my_rob(nums[:-1]),my_rob(nums[1:])) if len(nums) != 1 else nums[0]

贪心算法

55. 跳跃游戏

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_distance = 0
        for i in range(len(nums)):
            if i <= max_distance:
                max_distance = max(max_distance,i+nums[i])
                if max_distance >= len(nums)-1 :
                    return True
        return False

435. 无重叠区间

这题的叙述可以转化为最多参加多少个活动

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        n = len(intervals)
        right = intervals[0][1]
        ans = 1

        for i in range(len(intervals)):
            if intervals[i][0] >= right:
                ans += 1
                right = intervals[i][1]
        return n-ans

621. 任务调度器

先排满数量最多的任务

剩下的任务都可以中间插空，如果存在数量相同的不同类型任务，则需要

在最后额外执行一次这些任务

class Solution(object):
    def leastInterval(self, tasks, n):
        """
        :type tasks: List[str]
        :type n: int
        :rtype: int
        """
        length = len(tasks)
        if length <= 1:
            return length
        
        # 用于记录每个任务出现的次数
        task_map = dict()
        for task in tasks:
            task_map[task] = task_map.get(task, 0) + 1
        # 按任务出现的次数从大到小排序
        task_sort = sorted(task_map.items(), key=lambda x: x[1], reverse=True)
        
        # 出现最多次任务的次数
        max_task_count = task_sort[0][1]
        # 至少需要的最短时间
        res = (max_task_count - 1) * (n + 1)
        
        for sort in task_sort:
            if sort[1] == max_task_count:
                res += 1
        
        # 如果结果比任务数量少，则返回总任务数
        return res if res >= length else length