leetcode 刷题周报（9.3-9.10）

leetcode_93910_0">leetcode 刷题周报（9.3-9.10）

2708.一个小组的最大实力值

题意：

给你一个下标从 0 开始的整数数组 nums ，它表示一个班级中所有学生在一次考试中的成绩。老师想选出一部分同学组成一个非空小组，且这个小组的 实力值 最大，如果这个小组里的学生下标为 i0, i1, i2, … , ik ，那么这个小组的实力值定义为 nums[i0] * nums[i1] * nums[i2] * ... * nums[ik] 。

请你返回老师创建的小组能得到的最大实力值为多少。

示例 1：

输入：nums = [3,-1,-5,2,5,-9]
输出：1350
解释：一种构成最大实力值小组的方案是选择下标为 [0,2,3,4,5] 的学生。实力值为 3 * (-5) * 2 * 5 * (-9) = 1350 ，这是可以得到的最大实力值。

示例 2：

输入：nums = [-4,-5,-4]
输出：20
解释：选择下标为 [0, 1] 的学生。得到的实力值为 20 。我们没法得到更大的实力值。

提示：

1 <= nums.length <= 13
-9 <= nums[i] <= 9

题解：

这道题实际上是求所有元素都为整数的数组的子序列的最大积，从最大积的正负性入手。

当数组仅有 1 个元素且为负数时，最大积为负数。
当数组不包含正数，且负数元素小于等于 1 个时，最大积为 0。
其他情况下，最大积为正数。那么如何求这个最大积呢？可以将所有非 0 元素求积，如果乘积为正数，则为最大积。如果乘积为负数，则说明乘积中包含奇数个负数，此时将这个乘积除以最大负数则为最大积。

class Solution {
public:long long maxStrength(vector<int>& nums) {long long negtive=-10;long long result=1;long long negtive_count=0;long long positive_count=0;long long zero_count=0;for(int i=0;i<nums.size();i++){if(nums[i]<0){negtive_count++; if(nums[i]>negtive){negtive=nums[i];}result*=nums[i];}else if(nums[i]==0){zero_count++;}else{positive_count++;result*=nums[i];}}if(zero_count==0 && positive_count==0 && negtive_count==1){return negtive;}else if(negtive_count<=1 && positive_count==0){return 0;}else{return result>0?result:result/negtive;}}
};

2860.让所有学生保持开心的分组方法数

题意：

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，其中 n 是班级中学生的总数。班主任希望能够在让所有学生保持开心的情况下选出一组学生：

如果能够满足下述两个条件之一，则认为第 i 位学生将会保持开心：

这位学生被选中，并且被选中的学生人数 严格大于 nums[i] 。
这位学生没有被选中，并且被选中的学生人数 严格小于 nums[i] 。

返回能够满足让所有学生保持开心的分组方法的数目。

示例 1：

输入：nums = [1,1]
输出：2
解释：
有两种可行的方法：
班主任没有选中学生。
班主任选中所有学生形成一组。 
如果班主任仅选中一个学生来完成分组，那么两个学生都无法保持开心。因此，仅存在两种可行的方法。

示例 2：

输入：nums = [6,0,3,3,6,7,2,7]
输出：3
解释：
存在三种可行的方法：
班主任选中下标为 1 的学生形成一组。
班主任选中下标为 1、2、3、6 的学生形成一组。
班主任选中所有学生形成一组。

提示：

1 <= nums.length <= 105
0 <= nums[i] < nums.length

题解：

根据题意可知，假设数组 nums 的长度为 n，此时设选中学生人数为 k，此时 k∈[0,n]，k 应满足如下：

所有满足 nums[i]<k 的学生应被选中；
所有满足 nums[i]>k 的学生不应被选中；
不能存在 nums[i]=k 的学生；

这意味着在确定当前已择中学生人数的前提下，则此时选择方案是唯一的，为方便判断，我们把 nums 从小到大排序。我们枚举选中的人数 k，由于 nums 已有序，此时最优分组一定是前 k 个学生被选中，剩余的 n−k 个学生不被选中，此时只需要检测选中的 k 个学生中的最大值是否满足小于 k，未被选中的学生中的最小值是否满足大于 k 即可，如果同时满足上述两个条件，则该分配方案可行，最终返回可行的方案计数即可，需要注意处理好边界 0 与 n。

class Solution {
public:int countWays(vector<int>& nums) {int n=nums.size();int res=0;sort(nums.begin(),nums.end());for(int k=0;k<=n;k++){//前k个元素是最大值是否小于kif(k>0 && nums[k-1]>=k){continue;}//后n-k个元素的最小值是否大于kif(k<n && nums[k]<=k){continue;}res++;}return res;}
};

88. 合并两个有序数组

题意：

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

**注意：**最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109

**进阶：**你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

题解：

1.简单解法：
直接插入到后面，然后排序：|

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {for(int i=0;i<nums2.size();i++){nums1[m++]=nums2[i];}sort(nums1.begin(),nums1.end());}
};

2.进阶解法：
O(m+n)，

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int i=0,j=0;vector<int> ans;while(i<m && j<n){if(nums1[i] <= nums2[j]){ans.push_back(nums1[i]);i++;}else{ans.push_back(nums2[j]);j++;}}if(i==m){while(j<n){ans.push_back(nums2[j++]);}}if(j==n){while(i<m){ans.push_back(nums1[i++]);}}for(int k=0;k<m+n;k++){nums1[k]=ans[k];}}
};

3174. 清除数字

题意：

给你一个字符串 s 。

你的任务是重复以下操作删除所有数字字符：

删除 第一个数字字符 以及它左边最近的 非数字 字符。

请你返回删除所有数字字符以后剩下的字符串。

示例 1：

**输入：**s = “abc”

输出：“abc”

解释：

字符串中没有数字。

示例 2：

**输入：**s = “cb34”

输出：“”

解释：

一开始，我们对 s[2] 执行操作，s 变为 "c4" 。

然后对 s[1] 执行操作，s 变为 "" 。

提示：

1 <= s.length <= 100
s 只包含小写英文字母和数字字符。
输入保证所有数字都可以按以上操作被删除。

题解：

很简单，没什么值得说的

class Solution {
public:string clearDigits(string s) {string res;for(int i=0;i<s.size();i++){if(s[i]>='a' && s[i]<='z'){res.push_back(s[i]);}else{res.pop_back();}}return res;}
};

977. 有序数组的平方

题意：

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非递减顺序 排序

进阶：

请你设计时间复杂度为 O(n) 的算法解决本问题

题解：

类似于归并+分类讨论，要注意mark的位置

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int mark=-1;vector<int> ans;for(int i=0;i<nums.size()-1;i++){if(nums[i]<0){mark=i;}else{break;}}int i=mark,j=mark+1;while(i>=0 && j<nums.size()){if(nums[i]*nums[i] < nums[j]*nums[j]){ans.push_back(nums[i]*nums[i]);i--;}else{ans.push_back(nums[j]*nums[j]);j++;}}if(i<0){while(j<nums.size()){ans.push_back(nums[j]*nums[j]);j++;}}if(j==nums.size()){while(i>=0){ans.push_back(nums[i]*nums[i]);i--;}}return ans;}
};