提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

LeetCode笔记：Biweekly Contest 89

LeetCode笔记 Contest 89 Biweekly
2023-06-13 09:14:10 时间

1. 题目一

给出题目一的试题链接如下：

1. 解题思路

这一题我的思路比较暴力，算是反其道行之吧，正常来说是考察给定的数字可以构成那些组合，但是这样得涉及到一些分类讨论问题。

所以这里我反了一下，直接考察全部可能的时间，然后看有哪些可以用给定的字符串进行表示，这样就可以规避掉分类讨论的问题，不过对应的会增加一下时间开销。

2. 代码实现

给出python代码实现如下：

class Solution:
    def countTime(self, time: str) -> int:
        
        def is_equal(t, time):
            for c1, c2 in zip(t, time):
                if c2 == "?":
                    continue
                elif c1 != c2:
                    return False
            return True
        
        res = 0
        for h in range(24):
            for m in range(60):
                t = f"{h}".rjust(2, "0") + ":" + f"{m}".rjust(2, "0")
                if is_equal(t, time):
                    res += 1
        return res

提交代码评测得到：耗时82ms，占用内存13.8MB。

2. 题目二

给出题目二的试题链接如下：

1. 解题思路

这一题我的思路就是先把给定的n的分解求出来，这个只要通过求

\log_2(n)

是很方便就可以快速实现的。

然后，求范围内的乘积我们可以通过求取累积乘积的方式进行实现，不过处于简单考察，我们直接使用一个二重循环就行。

2. 代码实现

给出python代码实现如下：

class Solution:
    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        MOD = 10**9 + 7
        
        powers = []
        while n != 0:
            p = int(log(n) / log(2))
            k = 2**p
            powers.insert(0, k)
            n -= k
        
        res = []
        for i, j in queries:
            ans = 1
            for k in range(i, j+1):
                ans = ans * powers[k] % MOD
            res.append(ans)
        return res

提交代码评测得到：耗时5967ms，占用内存51.7MB。

3. 题目三

给出题目三的试题链接如下：

1. 解题思路

这一题我的思路是使用二分法找到最小的可以实现的值。

而对于任意给定的

k

，要看这个数能否满足，我们只需要看在任意时刻，其之前给出的余留的空间是否足够即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def minimizeArrayValue(self, nums: List[int]) -> int:
        n = len(nums)
        def is_possible(k):
            remain = k - nums[0]
            for i in range(1, n):
                if nums[i] - k > remain:
                    return False
                if nums[i] < k:
                    remain += k - nums[i]
                else:
                    remain -= nums[i] - k
            return True        
        
        i, j = max(0, nums[0]-1), max(nums)
        while j - i > 1:
            m = (i+j) // 2
            if is_possible(m):
                j = m
            else:
                i = m
        return j

提交代码评测得到：耗时6985ms，占用内存26.1MB。

4. 题目四

给出题目四的试题链接如下：

1. 解题思路

这一题实在是没啥思路，只能放弃了……

相关文章