LeetCode笔记：Weekly Contest 294

codename_cys

发布于 2022-05-23 10:54:40

2300

发布于 2022-05-23 10:54:40

文章被收录于专栏：我的充电站

1. 题目一

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

2278. Percentage of Letter in String

1. 解题思路

这一题的思路其实很直接，用目标字符的数目除以字符串总长就行。

2. 代码实现

给出python代码实现如下：

class Solution:
    def percentageLetter(self, s: str, letter: str) -> int:
        n = len(s)
        cnt = Counter(s)
        return int(cnt[letter] / n * 100)

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

2. 题目二

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

2279. Maximum Bags With Full Capacity of Rocks

1. 解题思路

这一题思路同样直接，要最充分的利用其额外的石头来填满包，那么我们就要用它们来填充最贴近装满的包。

因此，我们计算出各个包的差值，然后进行一下排序即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def maximumBags(self, capacity: List[int], rocks: List[int], additionalRocks: int) -> int:
        delta = [c - r for c, r in zip(capacity, rocks)]
        delta = sorted(delta)
        s, n = 0, len(delta)
        for i in range(n):
            s += delta[i]
            if s > additionalRocks:
                return i
        return n

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

3. 题目三

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

2280. Minimum Lines to Represent a Line Chart

1. 解题思路

这一题我的思路依然很直接，就是计算一下需要多少直线。

我们首先对给出的点按照x坐标进行一下排序，然后分别计算一下每两个点之间的直线参数，比较一下是否是同一条直线即可。

2. 代码实现

给出python代码实现如下：

class Solution:
    def minimumLines(self, stockPrices: List[List[int]]) -> int:
        def cal_line(p1, p2):
            k = (p2[1] - p1[1]) / (p2[0] - p1[0])
            b = p1[1] - k * p1[0]
            return k, b
        
        stockPrices = sorted(stockPrices)
        n = len(stockPrices)
        if n == 1:
            return 0
        res = 1
        k, b = cal_line(stockPrices[0], stockPrices[1])
        for i in range(1, n-1):
            k1, b1 = cal_line(stockPrices[i], stockPrices[i+1])
            if k1 != k or b1 != b:
                res += 1
            k, b = k1, b1
        return res

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

4. 题目四

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

2281. Sum of Total Strength of Wizards

1. 解题思路

这一题我的思路分成两步，首先就是依次找到每一个元素作为最小的元素时可以组成的所有的子串。

然后，我们就是要找到这些子串的总和。

而关于这件事，会稍微复杂一点，我们用一个累积数组的累积数组来进行实现。

具体来说，假设某一位置k 下的元素作为最小元素时，其左右两侧的边界分别是i, j 。

记累积数组为s ，则有对于该元素能够组成的所有的子串的和的总和为：

\begin{aligned} tot &= \sum_{i=i}^{k}\sum_{j=k}^{j} (s_j - s_{i-1}) \\ &= \sum_{i=i}^{k}\sum_{j=k}^{j}s_j - \sum_{i=i}^{k}\sum_{j=k}^{j}s_{i-1} \\ &= \sum_{i=i}^{k}(\sum_{j=k}^{j}s_j) - \sum_{j=k}^{j}(\sum_{i=i}^{k}s_{i-1}) \\ &= (k-i+1)(S_{j} - S_{k-1}) - (j-k+1)(S_{k-1} - S_{i-1}) \end{aligned}

其中，S 就是原始数组的累积数组的累积数组。

因此，我们将其翻译成python代码如下。

2. 代码实现

给出python代码实现如下：

class Solution:
    def totalStrength(self, strength: List[int]) -> int:
        MOD = 10**9 + 7
        wizards = [(s, i) for i, s in enumerate(strength)]
        wizards = sorted(wizards)
        accum_str = [0] + list(accumulate(strength))
        accum_str = list(accumulate(accum_str))
        
        n = len(strength)
        index = [-1, n]
        res = 0
        for s, i in wizards:
            idx = bisect.bisect(index, i)
            bg, ed = index[idx-1], index[idx]
            index.insert(idx, i)
            a, b = i - bg, ed - i
            sj, si = accum_str[ed] - accum_str[i], accum_str[i] - accum_str[max(bg, 0)]
            tmp = (a * sj - b * si) * s
            res = (res + tmp) % MOD
        return res

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

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-05-22，如有侵权请联系 cloudcommunity@tencent.com 删除

python

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

python

编程算法

登录后参与评论

0 条评论

热度