第 31 场双周赛

Posted on | In , | |
Words count in article: 295 | Reading time ≈ 1

在区间范围内统计奇数数目

1
2
3
4
5
6
7
class Solution {
public:
    int countOdds(int low, int high) {
        int res=(high-low)/2;
        return low%2||high%2?res+1: res;
    }
};

和为奇数的子数组数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int numOfSubarrays(vector<int>& arr) 
    {
        int odd = 0, even = 1;  
        long long res = 0;
        int sum = 0;
        for (int num: arr)
        {
            sum += num;
            res += (sum % 2 == 0? odd: even);
            if (sum % 2 == 0)   even++;
            else                odd++;
        }
        return res % 1000000007;
    }
};

字符串的好分割数目

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
class Solution {
public:
    int numSplits(string s) {
        int ans = 0;

        vector<int> l_dic(26, 0);
        vector<int> r_dic(26, 0);
        int left = 0;
        int right = 0;

        for (int i = 0; i < s.size(); i++) {
            int c = s[i] - 'a';
            right += (r_dic[c] == 0);
            r_dic[c]++;
        }

        for (int i = 0; i < s.size() - 1; i++) {
            int c = s[i] - 'a';
            left += (l_dic[c] == 0);
            l_dic[c]++;
            r_dic[c]--;
            right -= (r_dic[c] == 0);
            ans += (left == right);
        }

        return ans;
    }
};

形成目标数组的子数组最少增加次数

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 minNumberOperations(vector<int>& target) {
        target.push_back(0);

        int ans = 0;
        stack<int> st;
        st.push(0);

        for (int i = 0; i < target.size(); i++) {
            while (st.top() > target[i]) {
                int t = st.top();
                st.pop();
                ans += t - max(st.top(), target[i]);
            }
            if (st.top() == target[i]) continue;

            if (st.top() < target[i]) {
                st.push(target[i]);
            }
        }
        return ans;
    }
};
Donate? comment?