讨论/题目交流/🐱 力扣第 11 场夜喵双周赛/
🐱 力扣第 11 场夜喵双周赛

欢迎在这里交流分享你的参赛心得以及体验。【前往竞赛
image.png

展开讨论
共 4 个讨论

题解代码链接
总结: 这次的题目都不是特别难,比较基础,很有可能出现在面试或者笔试中,大家一定要了解每道题目背后的原理和思想

  • 等差数列中缺失的数字
    数据量不大,直接对整个数组求和,然后按照等差数列的求和公式求出的结果与刚才的结果相减

  • 安排会议日程
    先排序,然后双指针分别指向两个区间,注意指针的移动即可(根据结束时间来移动)

  • 抛掷硬币
    动态规划
    二维 DP
    dp[i][j] 代表 掷了 i 个骰子,正面向上的个数为 j
    递推公式: dp[i][j] = dp[i-1][j] * 当前骰子为反面的概率 + dp[i-1][j-1] * 当前骰子为正面的概率;
    一维 DP 注意需要倒序更新
    dp[i] 代表 掷出个数为 i 的概率
    递推公式: dp[i] = dp[i] * 当前骰子为反面的概率 + dp[i-1] * 当前骰子为正面的概率;

  • 分享巧克力
    把可能的结果进行二分,然后进行查找,是否满足条件,注意边界条件
    二哥:典型的二分题 二分 + 贪心
    二哥:水题 我:???
    看了答案后 我:果然是水题,二哥牛批(破音)

24

关于第四题的二分解法,数组的分段最大最小和问题和最小最大和问题的思路是一样的,就是将分成K段理解为放进K个桶,使每个桶中元素之和不大于(不小于)目标值S,这个S就是我们二分的对象。S最小值为最小元素,最大值为所有元素之和。每次对S的尝试都是遍历一次数组,所以最终时间复杂度为Nlog2Smax。
这题dp也可以做,但是会超时。

5

双周赛的题目总的来说难度会比周赛的要简单一些

Problem 1: 等差数列中缺失的数字

题目大意:给定一个等差数列的数组,但其中少了一个数,需要将其找出来。同时题目中告知缺失的项不会是首项和尾项,因为如果是缺失首尾项答案就不唯一了

Example 1:
Input: arr = [5,7,11,13]
Output: 9
Explanation: The previous array was [5,7,9,11,13].
Example 2:
Input: arr = [15,13,12]
Output: 14
Explanation: The previous array was [15,14,13,12].

第一题比较简单,思路很容易想到,根据首项和尾项可以求出等差数列的步长,有了步长遍历一遍就能找到等差数列里缺失的数了

class Solution(object):
    def missingNumber(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        step = (arr[-1] - arr[0]) / len(arr) # 等差数列的步长
        last = arr[0]
        for item in arr[1:]:
            if item - last == step:
                last = item
                continue
            # 当步长不等于等差的步长时即找到缺失数字的位置
            return last + step
        return last

还有一种解法,当知道等差数列首项和尾项时,可以利用等差数列求和公式求出等差数列的和减去当前数组的和,结果即为缺失的那个数

class Solution(object):
    def missingNumber(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        return (arr[-1] + arr[0]) * (len(arr) + 1) / 2 - sum(arr)

Problem 2: 安排会议日程

题目大意:有两个人他们需要一起开一个时长为 duration 的会,用 slots1 和 slots2 两个数组分别表示每个人有空的时间段,需要找出他们都有空的时间段并且时长能满足大于等于 duration 的时间段,如果没有满足的时间段,则返回空数组

Example 1:
Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8
Output: [60,68]
Example 2:
Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 12
Output: []

这道题跟之前的一道 Meeting Rooms 的题目很相似,我们可以先将入参做一个转换,将所有时间点排序,同时记录时间点的状态,用 1 表示开始时间,用 -1 表示结束时间,比如 [[10, 50], [60, 120]] 会转换为 [[10, 1], [50, -1], [60, 1], [120, -1]], 我们依次遍历这个转换后的二维数组,并不断的更新当前状态的累积的值,当累积值为 2 时,说明此时开始两人均有空,再判断一下有空的时长是否满足所需的 duration ,满足则找到了所求的解

class Solution(object):
    def minAvailableDuration(self, slots1, slots2, duration):
        """
        :type slots1: List[List[int]]
        :type slots2: List[List[int]]
        :type duration: int
        :rtype: List[int]
        """
        slots = [v for s, e in (slots1 + slots2) for v in [[s, 1], [e, -1]]]
        state = 0 # 记录累积的状态值
        now = 0 # 记录开始的时间
        for t, s in sorted(slots):
            if state == 2 and now + duration <= t:
                return [last, last + duration]
            state += s
            now = t
        return []

Problem 3: 抛掷硬币

题目大意:有 n 个硬币,用一个数组记录了每个硬币被抛到正面的概率。给定一个整数 target 目标值,每个硬币抛一次,返回有 target 个硬币抛到正面的概率

Example 1:
Input: prob = [0.4], target = 1
Output: 0.40000
Example 2:
Input: prob = [0.5,0.5,0.5,0.5,0.5], target = 0
Output: 0.03125

这是道典型的 dp 的题目,解释一下是怎么想到 dp 的,当每抛一个硬币时,是不关心在此之前抛硬币的过程的,只关心当前的两个状态,一个是已经抛了几个硬币,另一个是正面的已经有几个,明确了这两个因素后,我们很容易的可以写出状态转移方程

用 dp[coin][k] 表示已经抛了 coin 个硬币,其中有 k 个是正面的概率

dp[coin][k] = dp[coin - 1][k] * (1 - p) + dp[coin - 1][k -1 ] * p

如果前 coin - 1 个已经有 k 个硬币朝上了,那当前的硬币就不能朝上了;另一种情况是前 coin - 1 次有 k - 1 个朝上,那当前抛的硬币必须朝上

初值: dp[0][0] = 1, dp[0][1] = 0, dp[0][2] = 0 … dp[0][target] = 0

class Solution(object):
    def probabilityOfHeads(self, prob, target):
        """
        :type prob: List[float]
        :type target: int
        :rtype: float
        """
        # 初值
        dp = [[1] + [0] * target] + [[0] * (target + 1) for i in range(len(prob))]  
        for i, p in enumerate(prob):
            for k in xrange(target + 1):
                dp[i + 1][k] = dp[i][k] * (1 - p) + (dp[i][k - 1] if k else 0) * p
        return dp[-1][target]

这里很容易发现一个优化点,我们可以用滚动数组将 dp 降维,具体代码如下:

class Solution(object):
    def probabilityOfHeads(self, prob, target):
        """
        :type prob: List[float]
        :type target: int
        :rtype: float
        """
        # 初值
        dp = [1] + [0] * target
        for i, p in enumerate(prob):
            # 因为要用到 dp[k - 1],所以倒序遍历,避免覆盖
            for k in xrange(target, -1, -1): 
                dp[k] = dp[k] * (1 - p) + (dp[k - 1] if k else 0) * p
        return dp[target]

Problem 4: 分享巧克力

题目大意:有一个巧克力棒,包含若干的小节,每个小节有一个甜度的数值,现在需要把巧克力分给 K 个朋友,用刀切 K 次将巧克力棒分为 K + 1 片,每片有若干节。作为巧克力棒的主人,需要慷慨一些,总是把切好后甜度值之和最小的那片留给自己,把其余的分给朋友。实现一个函数,给定甜度数值的数组 sweetness 以及朋友的个数 K,需要返回你能吃到的巧克力的最大的甜度

Example 1:
Input: sweetness = [1,2,3,4,5,6,7,8,9], K = 5
Output: 6
Explanation: You can divide the chocolate to [1,2,3], [4,5], [6], [7], [8], [9]
Example 2:
Input: sweetness = [5,6,7,8,9,1,2,3,4], K = 8
Output: 1
Explanation: There is only one way to cut the bar into 9 pieces.
Example 3:
Input: sweetness = [1,2,2,1,2,2,1,2,2], K = 2
Output: 5
Explanation: You can divide the chocolate to [1,2,2], [1,2,2], [1,2,2]

最大化最小值问题,有比较多类似的题目,主要的思路是用二分去枚举最小值,再判断够不够分,不够分说明给的最小值大了,则将这个数调小,如果够分,则将这个数调大

class Solution(object):
    def maximizeSweetness(self, sweetness, K):
        """
        :type sweetness: List[int]
        :type K: int
        :rtype: int
        """
        def helper(x):
            cur = chunk = 0
            for a in sweetness:
                cur += a
                if cur >= x:
                    chunk += 1
                    cur = 0
                if chunk >= K + 1:
                    return True
            return False
        
        left, right = 1, sum(sweetness) / (K + 1)
        while left < right:
            mid = (left + right + 1) / 2
            if helper(mid):
                left = mid
            else:
                right = mid - 1
        return left

That's all, Happy Programmers' Day~!

2

丢个链接跑路(必然不是最优解,都是比赛时想到的能过的写法)
https://zhuanlan.zhihu.com/p/87527285

2