On the shoulders of giants.

biweekly-contest-15

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

给你一个非递减的 有序 整数数组,已知这个数组中恰好有一个整数,它的出现次数超过数组元素总数的 25%。

请你找到并返回这个整数

示例:

输入:arr = [1,2,2,6,6,6,6,7,10]
输出:6

提示:

  • 1 <= arr.length <= 10^4
  • 0 <= arr[i] <= 10^5
题解

因为数组具有单调性,所以直接遍历。

时间复杂度:\(O(n)\)

class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int num = arr.size() * 0.25 + 1, k;

        for(k = 0; k + num - 1 < arr.size(); k++) {
            if(arr[k] == arr[k+ num - 1]) break;
        }

        return arr[k];
    }
};

删除被覆盖区间

给你一个区间列表,请你删除列表中被其他区间所覆盖的区间。

只有当 c <= a 且 b <= d 时,我们才认为区间 [a,b) 被区间 [c,d) 覆盖。

在完成所有删除操作后,请你返回列表中剩余区间的数目。

示例:

输入:intervals = [[1,4],[3,6],[2,8]]
输出:2
解释:区间 [3,6] 被区间 [2,8] 覆盖,所以它被删除了。

提示:​​​​​​

  • 1 <= intervals.length <= 1000
  • 0 <= intervals[i][0] < intervals[i][1] <= 10^5
  • 对于所有的 i != jintervals[i] != intervals[j]
题解

枚举当前区间有哪些区间能够覆盖,被覆盖的区间之后不再操作。

时间复杂度:\(O(n^2)\)

class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size(), cnt = n;
        vector<bool> vis(n);

        for(int i = 0; i < n; i++) {
            if(vis[i]) continue;
            int a = intervals[i][0], b = intervals[i][1];
            for(int j = 0; j < n; j++) {
                if(i == j || vis[j]) continue;
                int c = intervals[j][0], d = intervals[j][1];
                if(a <= c && d <= b) {
                    vis[j] = true;
                    cnt--;
                }
            }
        }
        
        return cnt;
    }
};

字母组合迭代器

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

  • 一个构造函数,输入参数包括:一个 有序且字符唯一 的字符串 characters(该字符串只包含小写英文字母)和一个数字 combinationLength 。
  • 函数 next() ,按 字典序 返回长度为 combinationLength 的下一个字母组合。
  • 函数 hasNext() ,只有存在长度为 combinationLength 的下一个字母组合时,才返回 True;否则,返回 False

示例:

CombinationIterator iterator = new CombinationIterator("abc", 2); // 创建迭代器 iterator

iterator.next(); // 返回 "ab"
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 "ac"
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 "bc"
iterator.hasNext(); // 返回 false

提示:

  • 1 <= combinationLength <= characters.length <= 15
  • 每组测试数据最多包含 10^4 次函数调用。
  • 题目保证每次调用函数 next 时都存在下一个字母组合。
题解

直接深搜回溯找出所有合法字符串,用指针指向当前字符串,当遇到最后一个返回 false

时间复杂度:\(O(n!)\)

class CombinationIterator {
private:
    vector<string> h;
    int pos, n, m;
    string tmp;
    
    void search(int p, int k, string ans) {
        if(k == m) {
            h.push_back(ans);
            return;
        }
        for(int i = p; i < n; i++) {
            search(i + 1, k + 1, ans + tmp[i]);
        }
    }
public:
    CombinationIterator(string characters, int combinationLength) {
        n = characters.size();
        m = combinationLength;
        tmp = characters;
        pos = 0;
        search(0, 0, "");
    }
    
    string next() {
        return h[pos++];
    }
    
    bool hasNext() {
        return pos != h.size();
    }
};

/**
 * Your CombinationIterator object will be instantiated and called as such:
 * CombinationIterator* obj = new CombinationIterator(characters, combinationLength);
 * string param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

下降路径最小和 II

给你一个整数方阵 arr ,定义「非零偏移下降路径」为:从 arr 数组中的每一行选择一个数字,且按顺序选出来的数字中,相邻数字不在原数组的同一列。

请你返回非零偏移下降路径数字和的最小值。

示例 1:

输入:arr = [[1,2,3],[4,5,6],[7,8,9]]
输出:13
解释:
所有非零偏移下降路径包括:
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
下降路径中数字和最小的是 [1,5,7] ,所以答案是 13 。

提示:

  • 1 <= arr.length == arr[i].length <= 200
  • -99 <= arr[i][j] <= 99
题解

动态规划:设 \(dp_{x,y}\) 为:走到 \((x,y)\) 时的最小值。

转移方程:\(dp_{x,y}=\min (dp_{x-1,k}), y \not= k\)

时间复杂度:\(O(nm^2)\)

class Solution {
private:
    const int INF = 1E9;
public:
    int minFallingPathSum(vector<vector<int>>& arr) {
        int n = arr.size(), m = arr[0].size();
        vector<vector<int>> dp(n, vector<int> (m));
        int result = INF;
        
        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++) {
                dp[i][j] = INF;
                for(int k = 0; k < m; k++) {
                    if(j == k) continue;
                    dp[i][j] = min(dp[i][j] , dp[i - 1][k] + arr[i][j]);
                }
            }
        }
        
        for(int i = 0; i < m; i++) {
            result = min(result, dp[n - 1][i]);
        }
        
        return result;
    }
};
Share

You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注