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

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

image.png

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

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

第一题:

求出数量超过25%的那个数,统计即可,至于怎么统计,见仁见智,用平衡树的,用哈希表的,用桶的,等等

class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        map<int, int> count;
        for (auto a: arr) {
            count[a]++;
        }
        for (auto it = count.begin();it != count.end();it++) {
            if (it->second * 4 > arr.size()) {
                return it->first;
            }
        }
        return -1;
    }
};

第二题:

这数据范围,才1000个,o(n2)o(n^2)的暴力检测妥妥就能过

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

第三题:

python有这个题的生成函数,详情请百度“itertools.combinations”

另:

知道前一个组合,如何求后一个组合?

例子:给定字母abcd,前一个组合是abc,下一个组合?

从组合的最后一个字母开始寻找,c有下一个字母d,所以将c换成d,返回下一个组合abd

d没有下一个字母,往前寻找,b有下一个字母c,所以将b换成c,最后一个字母赋值为c的下一个字母d,返回下一个组合acd

d没有下一个字母,往前寻找,c有下一个字母d,但是换成d后,最后一个字母没有字母赋值,所以继续往前寻找,a的下一个字母是b,所以a换成b,后面两个字母依次赋值为c和d,返回下一个组合bcd

按照这种方法,b虽然有下个字母c,但换成c后,最后一个字母没有字母可以赋值,所以bcd没有下一个组合

class CombinationIterator {
public:
    string res;
    vector<int> index;
    string allc;
    
    CombinationIterator(string characters, int combinationLength) {
        allc = characters;
        res = characters.substr(0, combinationLength);
        index = vector<int>(combinationLength, 0);
        for (int i = 0;i < index.size();i++) {
            index[i] = i;
        }
    }
    
    string next() {
        if (res == "") {
            return "";
        }
        string ret = string(res);
        int i = index.size() - 1;
        while (i >= 0) {
            index[i]++;
            if (index[i] + index.size() < allc.size() + i + 1) {
                res[i] = allc[index[i]];
                break;
            } else {
                i--;
            }
        }
        if (i < 0) {
            res = "";
        } else {
            i++;
            while (i < index.size()) {
                index[i] = index[i - 1] + 1;
                res[i] = allc[index[i]];
                i++;
            }
        }
        return ret;
    }
    
    bool hasNext() {
        return res != "";
    }
};

第四题:

动态规划,令dp[i][j]dp[i][j]为arr前i行中,并且第i行第j列这个元素位于下降路径的最后一个节点的最小路径,
则有转移方程,dp[i][j]=min(dp[i1][k])+arr[i][j],k!=jdp[i][j]=min(dp[i - 1][k])+arr[i][j], k != j

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