力扣第 476 场周赛(A~D)-尧图网站建设

📅 发布时间：2026/6/18 18:19:22

A:3745. 三元素表达式的最大值
签到题，直接排序，首尾分别取两个和一个就可以了。

1 class Solution {
2 public:
3     int maximizeExpressionOfThree(vector<int>& nums) {
4         sort(nums.begin(),nums.end(),greater<int>());
5         return nums[0]+nums[1]-nums.back();
6     }
7 };

B:3746. 等量移除后的字符串最小长度

脑筋急转弯。当字符串中存在a和b两种字符的时候，一定可以进行一个操作，选择一个子串ab或者ba，将其移除。

那么最后停止条件则为只剩下一种字符，答案也即为两种元素个数的差值。

1 class Solution:
2     def minLengthAfterRemovals(self, s: str) -> int:
3         cnt=Counter(s)
4         return abs(cnt['a']-cnt['b'])

C:3747. 统计移除零后不同整数的数目
要统计小于等于n的数中删除0后还有多少种数字，删除0的含义是比如1002删除0后为12.

可以发现，某个含0的数字删除0后位数会变少，那么也就和位数更少的某种情况重合了，也就是说含0的数字是直接不计数的，问题也就变成了1~n有多少个不含0的数字。

设n的长度为L，那么对于1~L-1长度的数字，1~9能够任选，也即共有9+9^2+9^3+..+9^(L-1)。

那么对于长度等于L的数字呢？假设n=2341，第一位取1时，后面的随便取有9^3个，第一位取2，且第二位取1~2时，后面的随便取有9^2个。

 1 class Solution:
 2     def countDistinct(self, n: int) -> int:
 3         s=str(n)
 4         l=len(s)
 5         t=9
 6         ans=0
 7         for _ in range(0,l-1):
 8             ans+=t
 9             t*=9
10         for i,c in enumerate(s):
11             x=int(c)
12             if x==0:
13                 break
14             v=x-1
15             if i==l-1:
16                 v+=1
17             ans+=v*(9**(l-i-1))
18         return ans

D:3748. 统计稳定子数组的数目

给定长1e5的数组，以及1e5的query，每个query一个l,r，问l~r内非递减子数组有多少个。

对于一个长为k的非递减数组，他的非递减子数组有多少个呢？

长为k的有一个，长为k-1的有2个....长为1的有k个。总共有(k+1)*k/2个。

那么我们可以把原数组分为多个非递减子数组，记录他们的起始位置。l，r普遍的情况是跨段，即左半和右半是非递减的一部分，中间是多个非递减子数组。

中间段的我们可以提前用前缀和维护好，在O(1)的时间复杂度内查询到，左右两段用二分找到分界点，计算一遍即可，这题主要难在下标，给绕晕了。

 1 typedef long long LL;
 2 class Solution {
 3 public:
 4     vector<long long> countStableSubarrays(vector<int>& nums, vector<vector<int>>& queries) {
 5         int n=nums.size();
 6         vector<int> left;
 7         vector<LL> s={0};
 8         int start=0;
 9         for(int i=0;i<n;i++){
10             if(i==n-1 || nums[i]>nums[i+1]){
11                 left.push_back(start);
12                 LL m=i-start+1;
13                 s.push_back(s.back()+m*(m+1)/2);
14                 start=i+1;
15             }
16         }
17         vector<LL> ans;
18         ans.reserve(queries.size());
19         for(auto q:queries){
20             int l=q[0],r=q[1];
21             int i=lower_bound(left.begin(),left.end(),l)-left.begin();
22             int j=upper_bound(left.begin(),left.end(),r)-left.begin()-1;
23             if(i>j){
24                 long long m=r-l+1;
25                 ans.push_back(m*(m+1)/2);
26                 continue;
27             }
28             long long m1=left[i]-l;
29             long long m2=r-left[j]+1;
30             ans.push_back(m1*(m1+1)/2+m2*(m2+1)/2+(s[j]-s[i]));
31         }
32         return ans;
33     }
34 };

力扣 第 476 场周赛(A~D)

力扣第 476 场周赛(A~D)