讨论/题目交流/🐱 第 15 场夜喵双周赛/
🐱 第 15 场夜喵双周赛

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

image.png

2 分 - 有序数组中出现次数超过25%的元素
4 分 - 删除被覆盖区间
5 分 - 字母组合迭代器
7 分 - 下降路径最小和 II

展开讨论

5126. 有序数组中出现次数超过25%的元素

出现次数超过 25% 就返回,直接按照题意来:

某个数的出现次数总次数25%\frac{某个数的出现次数}{总次数} \geq 25\%

class Solution:
    def findSpecialInteger(self, arr: List[int]) -> int:
        cnt = len(arr)
        cc = dict(collections.Counter(arr))
        for k, v in cc.items():
            if v > cnt / 4:
                return k

5127. 删除被覆盖区间

如果区间被覆盖就替换,由于就 1000 个区间,那么就 O(n^2) 暴力出结果就可以了。

class Solution:
    def removeCoveredIntervals(self, iii: List[List[int]]) -> int:
        n, t = len(iii), iii
        ans = 0
        for i in range(n):
            ok = 1
            for j in range(n):
                if i == j:
                    continue    
                if t[i][0] >= t[j][0] and t[i][1] <= t[j][1]:
                    ok = 0
            if ok == 1:
                ans += 1        
        return ans        

5123. 字母组合迭代器

这题抖了个小机灵。由于才 15 个数字,所以先计算了一下到底最多有多少种可能结果。

C157=6435C_{15}^{7} = 6435

所以最大排列情况就这么多。因为字符串是有序的,所以我们先暴力出来所有指定数目的子集合,然后 sort 一下,记录下下标,在调用的时候输出即可。

class CombinationIterator:
    
    def sol(self, items):

        if len(items) == 0:
            return [[]]

        subsets = []
        first_elt, rest_list = items[0], items[1:]

        for partial_sebset in self.sol(rest_list):
            subsets.append(partial_sebset)
            next_subset = partial_sebset[:] +[first_elt]
            subsets.append(next_subset)
        return subsets

    def __init__(self, characters: str, ll: int):
        self.isFirst = True
        self.cnt = 0
        cc = [c for c in characters]
        sols = self.sol(cc)
        self.res = []
        for s in sols:
            if len(s) == ll:
                self.res.append("".join(s[::-1]))
        self.res = sorted(self.res)       

    def next(self) -> str:
        self.cnt += 1
        return self.res[self.cnt - 1]
        

    def hasNext(self) -> bool:
        return self.cnt < len(self.res)


# Your CombinationIterator object will be instantiated and called as such:
# obj = CombinationIterator(characters, combinationLength)
# param_1 = obj.next()
# param_2 = obj.hasNext()

5129. 下降路径最小和 II

应该是我见过最简单的第四题之一了。由于不能同一列,所以在第三次循环的时候判一下列数就好。定义 dp[i][j] 代表到达第 i 行第 j 列时候的最小下降路径和。所以状态转移方程:

dp(i,j)=min(dp(i,j),dp(i1,k))      (kj)dp(i, j) = min(dp(i, j), dp(i - 1, k)) \ \ \ \ \ \ (k \neq j)

另外,这题卡语言!! Python 相同的代码会 TLE,C++ 1A。

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& arr) {
        int dp[204][204];
        for (int i = 0; i < arr.size(); ++ i) {
            dp[0][i] = arr[0][i];
        }
        int result = 200 * 99;
        for (int i = 1; i < arr.size(); ++ i) {
            for (int j = 0; j < arr.size(); ++ j) {
                dp[i][j] = 200 * 99;
                for (int k = 0; k < arr.size(); ++ k) {
                    if (k == j) continue;
                    dp[i][j] = min(arr[i][j] + dp[i - 1][k], dp[i][j]);
                }
                if (i == arr.size() - 1) {
                    result = min(result, dp[i][j]);
                }
            }
        }
        return result;
    }
};


最后,如果大家对移动端和刷算法题感兴趣,可以微信关注我的技术公众号。

image.png

5
展开全部 9 讨论