【JAVA】LeetCode力扣第31场双周赛题解+代码

红太狼 2023-03-01 12:46 22阅读 0赞

### 目录 ###

*  一、5456. 在区间范围内统计奇数数目 Easy
 *   *  方法一：暴力（错误：超时了）
     *  方法二：对low和high为奇还是偶进行讨论
 *  二、5457. 和为奇数的子数组数目 显示英文描述
 *   *  方法：记录和为奇数、偶数的次数，注意初始时偶数次数为1个（和为0）
 *  三、5458. 字符串的好分割数目 Medium
 *   *  方法：双指针，双哈希表
 *  四、5459. 形成目标数组的子数组最少增加次数 Hard
 *   *  方法：

# 一、5456. 在区间范围内统计奇数数目 Easy #

通过的用户数2009
    尝试过的用户数2044
    用户总通过次数2029
    用户总提交次数3849
    题目难度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 count = 0;
            for (int i = low; i <= high; i++) { 
                if (i % 2 == 1) { 
                    count++;
                }
            }
            return count;
        }
    }

## 方法二：对low和high为奇还是偶进行讨论 ##

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

# 二、5457. 和为奇数的子数组数目 显示英文描述 #

通过的用户数882
    尝试过的用户数1529
    用户总通过次数914
    用户总提交次数3474
    题目难度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^5  
1 <= arr\[i\] <= 100

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

**代码**

class Solution { 
        public int numOfSubarrays(int[] arr) { 
            int sum=0,ans=0;
            int[] count = new int[2];
            count[0]++;
            for(int i=0;i<arr.length;i++){ 
                sum+=arr[i];
                count[sum%2]++;
                ans+=count[sum%2==0 ? 1 : 0];
                ans%=1000000007;
            }
            return ans;
            
        }
    }

# 三、5458. 字符串的好分割数目 Medium #

通过的用户数1253
    尝试过的用户数1447
    用户总通过次数1271
    用户总提交次数1961
    题目难度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

## 方法：双指针，双哈希表 ##

class Solution { 
        public int numSplits(String s) { 
            Map<Character,Integer> leftMap=new HashMap<Character,Integer>();
            Map<Character,Integer> rightMap=new HashMap<Character,Integer>();
            int i,j,k,ans=0;
            for(i=0;i<s.length();i++){ 
                rightMap.put(s.charAt(i),rightMap.getOrDefault(s.charAt(i),0)+1);
            }
            for(i=0;i<s.length();i++){ 
                leftMap.put(s.charAt(i),leftMap.getOrDefault(s.charAt(i),0)+1);
                rightMap.put(s.charAt(i),rightMap.getOrDefault(s.charAt(i),0)-1);
                if(rightMap.get(s.charAt(i))==0){ 
                    rightMap.remove(s.charAt(i));
                }
                if(leftMap.size()==rightMap.size()){ 
                    ans++;
                }
            }
            return ans;
        }
    }

# 四、5459. 形成目标数组的子数组最少增加次数 Hard #

通过的用户数574
    尝试过的用户数827
    用户总通过次数606
    用户总提交次数1372
    题目难度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^5  
1 <= target\[i\] <= 10^5

## 方法： ##

class Solution { 
        public int minNumberOperations(int[] target) { 
            int ans=0,previous=0,i;
            for(i=0;i<target.length;i++){ 
                if(i==0){ 
                    ans+=target[0];
                }
                else if(target[i]>target[i-1]){ 
                    ans+=target[i]-target[i-1];
                }
            }
            return ans;
    
        }
    }