2024.9.3 Python，二分查找解决在D天内送达包裹的能力，dfs二叉树的层平均值，动态规划二分查找贪心算法解决最长增长子序列和马戏团人塔

1.在D天内送达包裹的能力

传送带上的包裹必须在 days 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量（weights）的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
返回能在 days 天内将传送带上的所有包裹送达的船的最低运载能力。
示例 1：
输入：weights = [1,2,3,4,5,6,7,8,9,10], days = 5
输出：15
解释：
船舶最低载重 15 就能够在 5 天内送达所有包裹，如下所示：
第 1 天：1, 2, 3, 4, 5
第 2 天：6, 7
第 3 天：8
第 4 天：9
第 5 天：10
请注意，货物必须按照给定的顺序装运，因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。
示例 2：
输入：weights = [3,2,2,4,1,4], days = 3
输出：6
解释：
船舶最低载重 6 就能够在 3 天内送达所有包裹，如下所示：
第 1 天：3, 2
第 2 天：2, 4
第 3 天：1, 4
示例 3：
输入：weights = [1,2,3,1,1], days = 4
输出：3
解释：
第 1 天：1
第 2 天：2
第 3 天：3
第 4 天：1, 1
题目分析：
我看了这个题的答案以后真的非常的火大，讲的云里雾里的，我的理解是这样的，确定运载能力的范围，再不考虑天数的情况下，最小是单个货物的最大值，最大是一天运完也就是所有货物总和，也就是说这样确定了答案的最粗略的上下线，现在目标是这样的，根据贪心算法，你能够通过当前的运载量计算出在当前运载量下能需要几天完成运输，这个day如果大于要求里的day了，说明当前运载量不够，要往上加，如果day小于要求里的day了，那说明当前运载量超了，可以尝试降一降，也就是说这个题最好的结果是二分法的变体，之前的判断是直接判断本值是不是列表里最合适的，现在是通过计算当前值的走一个函数，看看他是不是合适。
也就是说这个题考两件事，一件是能不能通过贪心算法写出这个函数计算出当前运载量下需要多少天能完成，二是需要二分法查找最合适的值，代码如下：

class Solution:
    def shipWithinDays(self, weights: List[int], days: int) -> int:        
        def canShipInDays(capacity):
            total_weight = 0
            days_needed = 1  # 从第一天开始
            for weight in weights:
                total_weight += weight
                if total_weight > capacity:  # 如果当前这一天的总重量超过了容量
                    days_needed += 1  # 需要多一天
                    total_weight = weight  # 开始下一天，并将当天的第一个包裹放入
            return days_needed <= days

        left, right = max(weights), sum(weights)

        while left < right:
            mid = (left + right) // 2
            if canShipInDays(mid):
                right = mid  # 找到可能的较小的容量
            else:
                left = mid + 1  # 加大容量
        return left

代码逻辑其实很简单了，上面也说的非常的清楚，如果有问题请随时评论区联系我，我会做出讲解。

2.二叉树的层平均值

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。
示例 2:
输入：root = [3,9,20,15,7]
输出：[3.00000,14.50000,11.00000]

class Solution:
    def averageOfLevels(self, root: TreeNode) -> List[float]:
        def dfs(root: TreeNode, level: int):
            if not root:
                return
            if level < len(totals):
                totals[level] += root.val
                counts[level] += 1
            else:
                totals.append(root.val)
                counts.append(1)
            dfs(root.left, level + 1)
            dfs(root.right, level + 1)

        counts = list()
        totals = list()
        dfs(root, 0)
        return [total / count for total, count in zip(totals, counts)]

这个代码我需要讲一下是怎么动态扩充这个列表的，在第一次进入一个新层的时候，他会直接进append来更新第一个值，然后第二次这一层进来的时候，level和len(totals)比较发现，已经建立了一层了，所以就往这一层里+=就可以了，最后return里的这个手法其实有点不太会写，自己写可能写个循环也是一样的。

3.最长增长子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的
子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
***方法一：***动态规划

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums:
            return 0
        dp = []
        for i in range(len(nums)):
            dp.append(1)
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

代码逻辑：
dp这里代表的是在指针在当前值的情况下把当前值算进去的，最长的子串长，那么上一个元素的，你在当前值前向遍历所有的值，如果遇见一个比自己小的数，那就读取他的dp值，然后给他的dp值加一，同时和自己的dp值进行比较，大的那个就是自己新的dp值，这样最后选最大的dp值就是最长的子串。
***方法二：***二分查找+贪心算法：

# Dynamic programming + Dichotomy.
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        d = []
        for n in nums:
            if not d or n > d[-1]:
                d.append(n)
            else:
                l, r = 0, len(d) - 1
                loc = r
                while l <= r:
                    mid = (l + r) // 2
                    if d[mid] >= n:
                        loc = mid
                        r = mid - 1
                    else:
                        l = mid + 1
                d[loc] = n
        return len(d)

4.马戏团人塔

有个马戏团正在设计叠罗汉的表演节目，一个人要站在另一人的肩膀上。出于实际和美观的考虑，在上面的人要比下面的人矮一点且轻一点。已知马戏团每个人的身高和体重，请编写代码计算叠罗汉最多能叠几个人。
示例：
输入：height = [65,70,56,75,60,68] weight = [100,150,90,190,95,110]
输出：6
解释：从上往下数，叠罗汉最多能叠 6 层：(56,90), (60,95), (65,100), (68,110), (70,150), (75,190)
思路：
这个题和上面这个题有一些异曲同工之妙，这个题根据高度排序以后，在重量里找最大子串就好了，代码如下：

class Solution:
    def bestSeqAtIndex(self, height: List[int], weight: List[int]) -> int:
        li = []
        for i, j in zip(height, weight):
            li.append([i,j])
        li.sort(key = lambda x:(x[0],-x[1]))

        nums = [i[1] for i in li]
        dp = []
        for i in range(len(nums)):
            # 如果新数比末尾数大，直接append
            if not dp or nums[i]>dp[-1]:
                dp.append(nums[i])
            # 如果新数没有末尾数大，寻找第一个比新数小的数d[k]，并更新d[k+1] = nums[i]
            left, right = 0, len(dp)-1
            while left <= right:
                mid = (left + right) // 2
                if dp[mid] >= nums[i]:
                    right = mid - 1
                else:
                    left = mid + 1
            if left < len(dp):
                dp[left] = nums[i]

        return len(dp)

解题思路
1.现将数据按身高升序，体重降序排列。
2.对体重取最长递增子序列：
1)dp[i]表示长度为i时末尾最小的数是多少
2)如果新数比末尾数大，直接append
3)如果新数没有末尾数大，寻找第一个比新数小的数d[k]，并更新d[k+1] = nums[i]。