Weekly Contest 149

Posted on | In , | |
Words count in article: 804 | Reading time ≈ 5

Day of the Year

Given a string date representing a Gregorian calendar date formatted as YYYY-MM-DD, return the day number of the year.

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
class Solution {
public:
    int dayOfYear(string data){
        int mm[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        int year = 0;
        int month = 0;
        int day = 0;
        year = (data[0]-'0') * 1000 + (data[1]-'0') * 100 +(data[2]-'0') * 10 +(data[3]-'0'); 
        month = (data[5]-'0') * 10 + (data[6]-'0');
        day = (data[8]-'0') * 10 + (data[9]-'0');
        int ret = 0;
        if(year % 100 != 0 && year % 4 == 0 || year % 400 == 0){
            for(int i=0; i<month-1; i++){
                ret += mm[i];
            }
            ret += day;
            if(month > 2){
                ret++;
            }
        }
        else
        {
            for(int i=0; i<month-1; i++){
                ret += mm[i];
            }
            ret += day;
        }
        return ret;
    }
};

Number of Dice Rolls With Target Sum

You have d dice, and each die has f faces numbered 1, 2, …, f.

Return the number of possible ways (out of fd total ways) modulo 10^9 + 7 to roll the dice so the sum of the face up numbers equals target.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<vector<int>> dpp = vector<vector<int>>(35, vector<int>(1005, -1));
    int helper(int d, int f, int target, int ans){
        if(dpp[d][target] > -1)
            return dpp[d][target];
        if(d == 0)
            return dpp[d][target] = static_cast<int>(target == 0);
        for(int i=1; i<=f; i++)
        {
            if(target-i >= 0)
                ans = (ans + helper(d-1, f, target-i, 0)) % static_cast<int>(1e9+7);
        }
        return dpp[d][target] = ans;
    }
    int numRollsToTarget(int d, int f, int target){
        return helper(d, f, target, 0);
    }
};

Swap For Longest Repeated Character Substring

Given a string text, we are allowed to swap two of the characters in the string. Find the length of the longest substring with repeated characters.

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
    int maxRepOpt1(string text) {
        int ans = 1;
        int n = text.size();
        int cur = 0;
        vector<int> count(26, 0);
        for(int i=0; i<n; i++)
        {
        	count[text[i]-'a']++;
        }

        vector<int> left(n, 1);
        vector<int> right(n, 1);

        cur = 1;

        for(int i=1; i<n; i++)
        {
        	if(text[i] == text[i-1])
        		cur++;
        	else
        		cur = 1;

        	left[i] = max(cur, left[i]);
        	ans = max(cur, ans);
        }

        cur = 1;

        for(int i=n-2; i>=0; i--)
        {
        	if(text[i] == text[i+1])
        		cur++;
        	else
        		cur = 1;
        	right[i] = max(cur, right[i]);
        	ans = max(cur, ans);
        }

        for(int i=1; i<n-1; i++)
        {
        	if(count[text[i-1]-'a'] > left[i-1])
        		ans = max(ans, left[i-1] + 1);
        	if(count[text[i+1]-'a'] > right[i+1])
        		ans = max(ans, right[i+1] + 1);
        	if( text[i-1] == text[i+1] && text[i-1] != text[i])
        		if(count[text[i-1]-'a'] > (left[i-1] + right[i+1]))
        			ans = max(ans, left[i-1] + right[i+1] + 1);
        		else
        			ans = max(ans, left[i-1] + right[i+1]);
        }
        return ans;
    }
};

Online Majority Element In Subarray

Implementing the class MajorityChecker, which has the following API:

  • MajorityChecker(int[] arr) constructs an instance of MajorityChecker with the given array arr;
  • int query(int left, int right, int threshold) has arguments such that:
    • 0 <= left <= right < arr.length representing a subarray of arr;
    • 2 * threshold > right - left + 1, ie. the threshold is always a strict majority of the length of the subarray

Each query(…) returns the element in arr[left], arr[left+1], …, arr[right] that occurs at least threshold times, or -1 if no such element exists.

1
2
3
4
MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);
majorityChecker.query(0,5,4); // returns 1
majorityChecker.query(0,3,3); // returns -1
majorityChecker.query(2,3,2); // returns 2
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
class MajorityChecker {
public:
    unordered_map<int, vector<int>> idx;
    MajorityChecker(vector<int>& arr) {
        for(int i=0; i<arr.size(); i++)
        {
            idx[arr[i]].push_back(i);
        }
    }
    
    int query(int left, int right, int threshold) {
        for(auto &i: idx)
        {
            if(i.second.size() < threshold)
                continue;
            auto t1 = lower_bound(i.second.begin(), i.second.end(), left);
            auto t2 = upper_bound(i.second.begin(), i.second.end(), right);
            if(t2 - t1 >= threshold)
                return i.first;
        }
        return -1;
    }
};

/**
 * Your MajorityChecker object will be instantiated and called as such:
 * MajorityChecker* obj = new MajorityChecker(arr);
 * int param_1 = obj->query(left,right,threshold);
 */
Donate? comment?