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

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

image.png

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

Rank

  • 31/791。

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

  • 题意:给你一个非递减的有序整数数组,已知这个数组中恰好有一个整数,它的出现次数超过数组元素总数的 25%。请你找到并返回这个整数。
  • 数据范围:
    • 1<=arr.length<=1041 <= arr.length <= 10^4
    • 0<=arr[i]<=1050 <= arr[i] <= 10^5
  • 思路:开一个长度为1e5的数组,扫描一遍,统计每个数出现的次数,然后从0遍历到1e5,如果某个数出现次数大于数组总长度除以4,就直接输出这个数。
  • 复杂度:O(arr.length)O(arr.length)
  • 代码:
class Solution {
public:
    int cnt[100010];
    int findSpecialInteger(vector<int>& arr) {
        memset(cnt, 0, sizeof(cnt));
        for(int i=0; i<arr.size(); i++){
            cnt[arr[i]]++;
        }
        int ans = -1;
        for(int i=0; i<100010; i++){
            if(cnt[i]*4>arr.size()){
                ans = i;
                break;
            }
        }
        return ans;
    }
};

5127. 删除被覆盖区间

  • 题意:给你一个区间列表,请你删除列表中被其他区间所覆盖的区间。只有当 c <= ab <= d 时,我们才认为区间 [a,b) 被区间 [c,d) 覆盖。在完成所有删除操作后,请你返回列表中剩余区间的数目。
  • 数据范围:
    • 1<=intervals.length<=10001 <= intervals.length <= 1000
    • 0<=intervals[i][0]<intervals[i][1]<=1050 <= intervals[i][0] < intervals[i][1] <= 10^5
    • 对于所有的 i!=jintervals[i]!=intervals[j]i != j:intervals[i] != intervals[j]
  • 思路:数据范围才1000,直接for循环暴力标记即可。
  • 复杂度:O(n^2)
  • 代码:
class Solution {
public:
    struct node{
        int l,r;
        node(){}
        node(int l_, int r_):l(l_),r(r_){}
    }a[1010];
    bool vis[1010];
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();
        for(int i=0; i<n; i++){
            a[i].l=intervals[i][0];
            a[i].r=intervals[i][1];
        }
        memset(vis, false, sizeof(vis));
        for(int i=0; i<n; i++){
            if(vis[i]) continue;
            for(int j=0; j<n; j++){
                if(j==i) continue;
                if(a[j].l<=a[i].l&&a[j].r>=a[i].r){
                    vis[i]=true;
                    break;
                }
            }
        }
        int ans=0;
        for(int i=0; i<n; i++){
            if(!vis[i]) ans++;
        }
        return ans;
    }
};

5123. 字母排列迭代器

  • 题意:请你设计一个迭代器类,包括以下内容:

    • 一个构造函数,输入参数包括:一个 有序且字符唯一 的字符串 characterscharacters(该字符串只包含小写英文字母)和一个数字 combinationLengthcombinationLength
    • 函数 next()next() ,按 字典序 返回长度为 combinationLengthcombinationLength 的下一个字母排列。
    • 函数 hasNext()hasNext() ,只有存在长度为combinationLengthcombinationLength 的下一个字母排列时,才返回 TrueTrue;否则,返回FalseFalse
  • 数据范围:

    • 1<=combinationLength<=characters.length<=151 <= combinationLength <= characters.length <= 15
    • 每组测试数据最多包含10410^4次函数调用。
    • 题目保证每次调用函数nextnext时都存在下一个字母排列。
  • 思路:这个题本质就是从n个数中取k个数,但是需要满足不降原则,直接使用回溯法搜索一下就可以了,注意搜索的起点就行。我们在搜索的时候可以把所有字符串都存入到一个vector<string>ans里面,后续就直接回答就可以了。

  • 复杂度:C(n,k),代表组合数。

  • 代码:

class CombinationIterator {
public:
    vector <string> ans;
    int n, k;
    bool vis[20];
    char re[20];
    char a[20];
    void dfs(int step,int start)
    {
        if(step==k)
        {
            string t="";
            for(int i=0;i<k;i++)
            {
                t+=re[i];
            }
            ans.push_back(t);
            return;
        }
        for(int i=start;i<n;i++) 
        {
            if(vis[i]==1)
                continue;
            vis[i]=1;
            re[step]=a[i];
            dfs(step+1,i+1);
            vis[i]=0;
        }
        return;
    }

    CombinationIterator(string characters, int combinationLength) {
        n = characters.size();
        k = combinationLength;
        ans.clear();
        memset(vis, false, sizeof(vis));
        for(int i=0; i<n; i++){
            a[i]=characters[i];
        }
        dfs(0, 0);
        reverse(ans.begin(), ans.end());
    }

    string next() {
        string t = ans[ans.size()-1];
        ans.pop_back();
        return t;
    }

    bool hasNext() {
        if(ans.size()) return true;
        else return false;
    }
};

5129. 下降路径最小和 II

  • 题意:给你一个整数方阵arr ,定义「非零偏移下降路径」为:从arr 数组中的每一行选择一个数字,且按顺序选出来的数字中,相邻数字不在原数组的同一列。请你返回非零偏移下降路径数字和的最小值。
  • 数据范围:
    • 1<=arr.length==arr[i].length<=2001 <= arr.length == arr[i].length <= 200
    • 99<=arr[i][j]<=99-99 <= arr[i][j] <= 99
  • 思路:简单DP,设dp[i][j]dp[i][j]表示选择第ii行第jj个数的时候获得的 非零偏移下降路径数字和的最小值,那么转移就很明显了。dp[i][j]=min(dp[i][j],dp[i1][k]+arr[i][j])dp[i][j]=min(dp[i][j], dp[i-1][k]+arr[i][j]),其中kk要和jj不相等。注意一下边界条件就可以了。
  • 复杂度:O(arr.lengtharr[0].length2)O(arr.length*arr[0].length^2)
  • 代码:
class Solution {
public:
    int dp[210][210];
    int minFallingPathSum(vector<vector<int>>& arr) {
        int n = arr.size();
        int m = arr[0].size();
        memset(dp, 0x3f, sizeof(dp));
        for(int i=0; i<m; i++){
            dp[0][i]=arr[0][i];
        }
        for(int i=1; i<n; i++){
            for(int j=0; j<m; j++){
                for(int k=0; k<m; k++){
                    if(k==j) continue;
                    dp[i][j] = min(dp[i][j], dp[i-1][k]+arr[i][j]);
                }
            }
        }
        int ans=0x3f3f3f3f;
        for(int i=0; i<m; i++){
            ans = min(ans, dp[n-1][i]);
        }
        return ans;
    }
};
1
展开全部 9 讨论