On the shoulders of giants.

biweekly-contest-31

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

给你两个非负整数 low 和 high 。请你返回lowhigh之间(包括二者)奇数的数目。

示例 1:

输入:low = 3, high = 7
输出:3
解释:3 到 7 之间奇数数字为 [3,5,7] 。

示例 2:

输入:low = 8, high = 10
输出:1
解释:8 到 10 之间奇数数字为 [9] 。

提示:

  • 0 <= low <= high <= 10^9
题解

简单模拟可以发现规律。

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

class Solution {
public:
    int countOdds(int low, int high) {
        int n = high - low + 1;
        return (low & 1 ? (n + 1) / 2 : n / 2);
    }
};

和为奇数的子数组数目

给你一个整数数组 arr 。请你返回和为 奇数 的子数组数目。

由于答案可能会很大,请你将结果对 10^9 + 7 取余后返回。

示例 1:

输入:arr = [1,3,5]
输出:4
解释:所有的子数组为 [[1],[1,3],[1,3,5],[3],[3,5],[5]] 。
所有子数组的和为 [1,4,9,3,8,5].
奇数和包括 [1,9,3,5] ,所以答案为 4 。

示例 2 :

输入:arr = [2,4,6]
输出:0
解释:所有子数组为 [[2],[2,4],[2,4,6],[4],[4,6],[6]] 。
所有子数组和为 [2,6,12,4,10,6] 。
所有子数组和都是偶数,所以答案为 0 。

示例 3:

输入:arr = [1,2,3,4,5,6,7]
输出:16

示例 4:

输入:arr = [100,100,99,99]
输出:4

示例 5:

输入:arr = [7]
输出:1

提示:

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

我们记录从左到右遍历过多少个 奇数和 和 偶数和。

通过 奇数 – 偶数 为奇数的形式,计算出结果。

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

const int MOD = 1E9 + 7;
class Solution {
public:
    int numOfSubarrays(vector<int>& arr) {
        int sum = 0, a = 0, b = 1, result = 0;
        for(auto num : arr) {
            sum += num;
            if(sum & 1) {
                result = (result + b) % MOD;
                a++;
            } else {
                result = (result + a) % MOD;
                b++;
            }
        }
        return result;
    }
};

字符串的好分割数目

给你一个字符串 s ,一个分割被称为 「好分割」 当它满足:将 s 分割成 2 个字符串 p 和 q ,它们连接起来等于 s 且 p 和 q 中不同字符的数目相同。

请你返回 s 中好分割的数目。

示例 1:

输入:s = "aacaba"
输出:2
解释:总共有 5 种分割字符串 "aacaba" 的方法,其中 2 种是好分割。
("a", "acaba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。
("aa", "caba") 左边字符串和右边字符串分别包含 1 个和 3 个不同的字符。
("aac", "aba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。
("aaca", "ba") 左边字符串和右边字符串分别包含 2 个和 2 个不同的字符。这是一个好分割。
("aacab", "a") 左边字符串和右边字符串分别包含 3 个和 1 个不同的字符。

示例 2:

输入:s = "abcd"
输出:1
解释:好分割为将字符串分割成 ("ab", "cd") 。

示例 3:

输入:s = "aaaaa"
输出:4
解释:所有分割都是好分割。

示例 4:

输入:s = "acbadbaada"
输出:2

提示:

  • s 只包含小写英文字母。
  • 1 <= s.length <= 10^5
题解

预处理后,遍历判断即可。

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

class Solution {
public:
    int numSplits(string s) {
        vector<int> lef(26), rig(26);
        for(auto c : s) rig[c - 'a']++;
        int result = 0, count_lef = 0, count_rig = 0;
        for(auto num : rig) {
            if(num != 0) count_rig++;
        }
        for(int i = 0; i < s.length(); i++) {
            if(lef[s[i] - 'a']++ == 0) count_lef++;
            if(--rig[s[i] - 'a'] == 0) count_rig--;
            if(count_lef == count_rig) result++;
        }
        return result;
    }
};

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

给你一个整数数组 target 和一个数组 initial ,initial 数组与 target  数组有同样的维度,且一开始全部为 0 。

请你返回从 initial 得到  target 的最少操作次数,每次操作需遵循以下规则:

  • initial 中选择 任意 子数组,并将子数组中每个元素增加 1 。

答案保证在 32 位有符号整数以内。

示例 1:

输入:target = [1,2,3,2,1]
输出:3
解释:我们需要至少 3 次操作从 intial 数组得到 target 数组。
[0,0,0,0,0] 将下标为 0 到 4 的元素(包含二者)加 1 。
[1,1,1,1,1] 将下标为 1 到 3 的元素(包含二者)加 1 。
[1,2,2,2,1] 将下表为 2 的元素增加 1 。
[1,2,3,2,1] 得到了目标数组。

示例 2:

输入:target = [3,1,1,2]
输出:4
解释:(initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (target) 。

示例 3:

输入:target = [3,1,5,4,2]
输出:7
解释:(initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1] 
                                  -> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target)。

示例 4:

输入:target = [1,1,1,1]
输出:1

提示:

  • 1 <= target.length <= 10^5
  • 1 <= target[i] <= 10^5
题解

把原数组处理成差分数组,然后我们要做的就是让差分数组全为零的最小代价。

通过简单的数学证明可以得到答案:\(\max(a, b)\) a 为差分数组正数和,b 为差分数组负数和。

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

class Solution {
public:
    int minNumberOperations(vector<int>& target) {
        int n = target.size(), a = 0, b = 0;
        vector<int> sub(n);
        sub[0] = target[0];
        for(int i = 1; i < n; i++) {
            sub[i] = target[i] - target[i - 1];
        }
        for(int i = 0; i < n; i++) {
            if(sub[i] > 0) a += sub[i];
            if(sub[i] < 0) b -= sub[i];
        }
        return max(a, b);
    }
};
Share

You may also like...

发表评论

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