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

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

image.png

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

展开讨论
力扣 (LeetCode)发起于 2019-12-14
最近编辑于 2019-12-15

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

首先,题目保证数组中仅有一个数字出现超过 25%,所以有很多奇怪的情况可以不用考虑了。
最直接的思路就是暴力统计每一个数字出现了多少次,然后输出满足要求的那一个。

  • 一种方法是使用 map 来实现这件事,就是 O(nlogn)O(n log n) 的复杂度。
  • 因为题目中保证数字有序排列(即相同的数字一定在一起),所以你可以线性地做到相同的事情。方法就是使用一个 cur 变量统计当前扫描到了哪一个数字, cnt 变量表示 cur 这个数字遇到了多少次。
class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int n = arr.size();
        int cur = arr[0], cnt = 1;
        if (cnt * 4 > n) return cur;
        for (int i = 1; i < n; i++){
            if (arr[i] != cur) cur = arr[i], cnt = 0;
            ++cnt;
            if (cnt * 4 > n) return cur;
        }
        return 0;
    }
};

5127. 删除被覆盖区间

因为数据范围非常小,区间的数量仅有 10001000 个,所以暴力的使用 O(n2)O(n ^ 2) 的复杂度就可以通过这道题目。
具体做法就是,顺次枚举区间 [a,b)[a, b),然后检查给定的其他所有区间 [c,d)[c, d),是否存在 [a,b)[c,d)[a, b) \in [c, d),不存在则给答案计数器加一。

class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();
        int ans = 0;
        for (int i = 0; i < n; i++){
            bool flag = true;
            for (int j = 0; j < n && flag; j++){
                if (i == j) continue;
                if (intervals[j][0] <= intervals[i][0] && intervals[i][1] <= intervals[j][1]) flag = false;
            }
            if (flag) ++ans;
        }
        return ans;
    }
};

5123. 字母排列迭代器

题目就是按顺序生成 nn 个字母中选择 combinationLengthcombinationLength 的所有子序列。
方法也非常直白,常见于小学奥数课本,初中、高中数学课本,大学组合数学中。
我们将字符串的外衣去掉,将字符串看作 1,2,3,,n1, 2, 3, \cdots, n,那么第一个排列数组一定是 1,2,3,,combinationLength1, 2, 3, \cdots, combinationLength,最后一个排列数组一定是 ncombinationLength+1,ncombinationLength+2,,nn - combinationLength + 1, n - combinationLength + 2, \cdots, n
生成下一个字符串的方法也很简单,从后往前扫描当前的数组,判断位置是否可以增加 11(增加后不超过最后一个排列这个位置上的值),如果找不到可以增大的数字,说明已经生成完毕,否则将此位置增加 11, 然后这个位置之后的所有位置升序递增 11

class CombinationIterator {
public:
    int cur[20], lim[20], len;
    string ch;
    bool nxt;
    CombinationIterator(string characters, int combinationLength) {
        int n = characters.size();
        ch = characters;
        len = combinationLength;
        nxt = true;
        for (int i = 0; i < len; i++) cur[i] = i, lim [i] = n - len + i;
    }
    
    string next() {
        string ret = "";
        for (int i = 0; i < len; i++) ret += ch[cur[i]];
        
        int j = len - 1;
        while(j >= 0 && cur[j] == lim[j]) --j;
        if (j == -1) nxt = false; else{
            ++cur[j];
            for (int i = j + 1; i < len; i++) cur[i] = cur[i - 1] + 1;
        }
        
        return ret;
    }
    
    bool hasNext() {
        return nxt;
    }
};

5129. 下降路径最小和 II

简单的一个动态规划,令 dp[i][j]dp[i][j] 表示当前路径走到了第 ii 行第 jj 个位置的最小权值和。(讨论中坐标均从 11 开始 ,矩阵 arrarrnnmm 列)
边界情况就是 dp[0][i]=0,i[1,n]dp[0][i] = 0, i \in [1, n],即未出发还在第 00 行的某个位置,权值和为 00
转移就是对于第 i 行第 j 个位置,我们可以从第 i1i - 1 行第 kk 个位置移动过来,满足 kj,k[1,m]k \neq j , k \in [1, m]。对于所有的 dp[i1][k]dp[i - 1][k] 找一个最小的转移到当前位置就可以了,即 dp[i][j]=minkj,k[1,m]dp[i1][k]+arr[i][j]dp[i][j] = \mathop{min}\limits_{k\neq j, k \in [1, m]}{dp[i-1][k] + arr[i][j]}
最终答案就是在第 nn 行的所有情况中找一个最小的。

int dp[250][250];

class Solution {
public:    
    int minFallingPathSum(vector<vector<int>>& arr) {
        int n = arr.size(), m = arr[0].size();
        memset(dp[0], 0, sizeof(dp[0]));
        
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                dp[i][j] = 4000000;
                for (int k = 1; k <= m; k++){
                    if (j == k) continue;
                    dp[i][j] = min(dp[i][j], dp[i - 1][k] + arr[i - 1][j - 1]);
                }
            }
        }
        
        int ans = 4000000;
        for (int i = 1; i <= m; i++) ans = min(ans, dp[n][i]);
        
        return ans;
    }
};
11
展开全部 9 讨论