leetcode31场双周赛
稳稳的三题选手
T1:在区间范围内统计奇数数目
给你两个非负整数 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从low到high若共有偶数个数，则其肯定奇偶占半，若奇数个数，只需判断其开始的那个数是否为奇数，若为奇数则为一半加一，否则为一半。
class Solution {
public int countOdds(int low, int high) {
int num = high - low + 1;
if(num % 2 == 0){
return num / 2;
}else{
if(low % 2 == 1){
return num / 2 + 1;
}else{
return num / 2;
}
}
}
}T2:和为奇数的子数组数目
给你一个整数数组 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大体思路为找以当前位置结尾的和为奇数子数组的数目，我们发现其的取值依赖于以前一个位置结尾和为偶/奇数子数组的数目。
定义dp0[i]为以i结尾和为偶数子数组的数目，dp1[i]为以i结尾和为奇数子数组的数目，sum(dp1)即为所求。
转移方程如下：
偶数=奇数+奇数
偶数=偶数+偶数 = 0 + 偶数
奇数=偶数+奇数 = 0 + 奇数
偶数=奇数 + 偶数
class Solution {
public int numOfSubarrays(int[] arr) {
int N = arr.length;
int mod = (int)Math.pow(10, 9) + 7;
int[] dp0 = new int[N]; // i结尾偶数数组的数目
int[] dp1 = new int[N];
if(arr[0] % 2 == 0){
dp0[0] = 1;
}else{
dp1[0] = 1;
}
int ans = dp1[0];
for(int i = 1; i < N; i++){
if(arr[i] % 2 == 0){
dp0[i] = dp0[i - 1] + 1;
dp1[i] = dp1[i - 1];
}else{
dp0[i] = dp1[i - 1];
dp1[i] = dp0[i - 1] + 1;
}
ans += dp1[i];
ans %= mod;
}
return ans;
}
}T3:和为奇数的子数组数目
给你一个字符串 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^2）的题目。
定义pre, next两数组，其中pre[i]为以i结尾不同字符的数目，next[i]为i开头不同字符的数目。
如此只需pre[i] 等于next[i + 1]，该分割就为好分割。
class Solution {
public int numSplits(String s) {
int N = s.length();
int[] pre = new int[N]; // 以0~i 不同元素的数目
int[] next = new int[N]; // i ~ n - 1
int[] set = new int[26];
pre[0] = 1;
set[s.charAt(0) - 'a'] = 1;
for(int i = 1; i < N; i++){
if(set[s.charAt(i) - 'a'] == 0){
set[s.charAt(i) - 'a'] = 1;
pre[i] = pre[i - 1] + 1;
}else{
pre[i] = pre[i - 1];
}
}
int[] set1 = new int[26];
next[N - 1] = 1;
set1[s.charAt(N - 1) - 'a'] = 1;
for(int i = N - 2; i >= 0; i--){
int cur = s.charAt(i) - 'a';
if(set1[cur] == 0){
set1[cur] = 1;
next[i] = next[i + 1] + 1;
}else{
next[i] = next[i + 1];
}
}
int ans = 0;
for(int i = 1; i < N; i++){
if(pre[i - 1] == next[i]){
ans++;
}
}
return ans;
}
}我的博客即将同步至腾讯云+社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=kon63o2aaa89
举报
腾讯云开发者
