Biweekly Contest 15

Posted on | In , | |
Words count in article: 412 | Reading time ≈ 2

1287. Element Appearing More Than 25% In Sorted Array

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int findSpecialInteger(vector<int>& arr) {
        int a[100005] = {0};
        for(int i=0; i<arr.size(); i++){
            a[arr[i]]++;
            if(a[arr[i]] >= arr.size()/4+1)
                return arr[i];
        }
        return 0;
    }
};

1288. Remove Covered Intervals

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        int count = intervals.size();
        int cur_left = intervals[0][0];
        int cur_right_max = intervals[0][1];
        for(auto i=intervals.begin()+1; i!=intervals.end(); ){
            if((*i)[1] <= cur_right_max){
                i = intervals.erase(i);
                count--;
                continue;
            }
            if((*i)[1] > cur_right_max){
                cur_right_max = (*i)[1];
                i++;
                continue;
            }
        }
        return count;
    }
};

1286. Iterator for Combination

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class CombinationIterator {
public:
    vector<string> ret;
    int size;
    CombinationIterator(string ch, int Len) {
        string t = "";
        dfs(ch, 0, 0, Len, t);
        size = 0;
        //sort(ret.begin(), ret.end());
        //for(auto i: ret) cout << i << endl;
    }
    
    void dfs(string ch, int curi, int cur_size, int Len, string cur_str){
        if(Len == cur_size){
            ret.push_back(cur_str);
            return;
        }
        else if(ch.size() - curi + cur_size < Len) return;
        else if(curi >= ch.size()) return;
        for(int i=curi; i<ch.size(); i++){
            dfs(ch, i+1, cur_size+1, Len, cur_str + ch[i]);
        }
    }
    
    string next() {
        string r = ret[size++];
        return r;
    }
    
    bool hasNext() {
        return !(size == ret.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();
 */

1289. Minimum Falling Path Sum II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int dp[205][205];
    
    int dfs(vector<vector<int>>& arr, int i, int j){
        if(i == arr.size()) return 0;
        if(dp[i][j] != INT_MIN) return dp[i][j];
        int ans = INT_MAX;
        for(int cc=0; cc<arr.size(); cc++){
            if(cc == j) continue;
            ans = min(ans, dfs(arr, i+1, cc)+arr[i][cc]);
        }
        return dp[i][j] = ans;
    }
    
    int minFallingPathSum(vector<vector<int>>& arr) {
        for(int i=0; i<205; i++){
            for(int j=0; j<205; j++)
                dp[i][j] = INT_MIN;
        }
        int ret =  dfs(arr, 0, arr[0].size());
        return ret;
    }
};
Donate? comment?