本文共 3718 字，大约阅读时间需要 12 分钟。

1. 比赛结果

全国排名： 273 / 2767，9.87%；全球排名： 819 / 8677，9.44%

2. 题目

1. LeetCode 5456. 在区间范围内统计奇数数目 easy

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

示例 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

解题：

• 超时解，数据太大了，不能模拟

class Solution {
   public:    int countOdds(int low, int high) {
       	int s = 0;    	for(int i = low; i <= high; ++i)    		if(i%2==1)    			s++;		return s;    }};

• 正解，按奇偶讨论

class Solution {
   public:    int countOdds(int low, int high) {
       	if(low%2 || high%2)    		return (high-low)/2+1;    	else    		return (high-low)/2;    }};

2. LeetCode 5457. 和为奇数的子数组数目 medium

给你一个整数数组 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^51 <= arr[i] <= 100

解题：

• 记录和为奇数、偶数的次数，注意初始时偶数次数为1个（和为0）

class Solution {
   public:    int numOfSubarrays(vector
   
    & arr) {
       	int odd = 0, even = 1, ans = 0, sum = 0, i;    	for(i = 0; i < arr.size(); ++i)    	{
       		sum += arr[i];    		if(sum&1)//奇数    		{
       			ans += even%1000000007;    			odd++;    		}    		else    		{
       			ans += odd%1000000007;    			even++;    		}    		ans %= 1000000007;    	}    	return ans;    }};
   

3. LeetCode 5458. 字符串的好分割数目 medium

给你一个字符串 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

解题：

• 先左边1个字符计数，右边剩下的字符计数
• 双指针遍历字符串，左边+，右边-，种类相同时 ans+1

class Solution {
   public:    int numSplits(string s) {
       	unordered_map
   
     l, r;    	int i, ans = 0;    	l[s[0]] = 1;    	for(i = 1; i < s.size(); ++i)    		r[s[i]]++;    	for(i = 1; i < s.size(); ++i)    	{
       		if(l.size() == r.size())    			ans++;    		l[s[i]]++;    		if(--r[s[i]] == 0)    			r.erase(s[i]);    	}    	return ans;    }};
   

4. LeetCode 5459. 形成目标数组的子数组最少增加次数 hard

给你一个整数数组 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^51 <= target[i] <= 10^5

解题：

• 数组末尾添加个最小值0
• 遍历数组遇到下降的，次数+下降的差值

class Solution {
   public:    int minNumberOperations(vector
   
    & target) {
       	int s = 0;        target.push_back(0);    	for(int i = 1; i < target.size(); ++i)    	{
   			if(target[i-1] > target[i])    			s += target[i-1]-target[i];    	}    	return s;    }};
   

我的CSDN

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

转载地址：https://michael.blog.csdn.net/article/details/107587115 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！