题目

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。
示例：

输入： nums = [5,2,6,1]
输出：[2,1,1,0]
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

提示：

• 0 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

  思路

  其实除了暴力没有特别好的思路，后来看了看别人的题解，自己又写了一遍。

  整体思路

  对下标进行归并排序，并且在排序时记录下每个位置后面数字的个数

  详细思路

  首先对整个数组进行归并。
  在每个归并段内，通过比较nums[idx[i]]来对idx[i]进行归并排序。并且在排序出现：nums[idx[i]]>nums[idx[j]]的时候，在idx[i]这个位置对应的最终结果（也即比nums中下标为idx[i]的元素右侧比这个元素大的元素个数）上面，加上该归并段内比nums[idx]大的数的个数：e-j+1。

  代码

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

  class Solution { public: vector<int> countSmaller(vector<int>& nums) { int n = nums.size(); vector<int> res(n,0),helper(n,0),idxs(n,0); for(int i=0;i<n;i++) idxs[i] = i; mergeAndSort(nums,res,idxs,helper,0,n-1); return res; } void mergeAndSort(vector<int>& nums,vector<int>& res,vector<int>& idxs,vector<int>& helper,int s,int e){ if(s>=e) return; int mid = s+(e-s)/2; mergeAndSort(nums,res,idxs,helper,s,mid); mergeAndSort(nums,res,idxs,helper,mid+1,e); mergeAndCount(nums,res,idxs,helper,s,mid,e); } void mergeAndCount(vector<int>& nums,vector<int>& res,vector<int>& idxs, vector<int>& helper,int s,int mid,int e){ for(int i=s;i<=e;i++){ helper[i] = idxs[i]; } int i=s,j=mid+1,idx=s; while(i<=mid&&j<=e){ if(nums[helper[i]]<=nums[helper[j]]){ idxs[idx++] = helper[j++]; }else{ res[helper[i]]+= e-j+1; idxs[idx++]=helper[i++]; } } while(i<=mid){ idxs[idx++] = helper[i++]; } while(j<=e){ idxs[idx++] = helper[j++]; } } };

题目

927. 三等分

难度困难 51

给定一个由 0 和 1 组成的数组 A，将数组分成 3 个非空的部分，使得所有这些部分表示相同的二进制值。

如果可以做到，请返回任何 [i, j]，其中 i+1 < j，这样一来：

• A[0], A[1], ..., A[i] 组成第一部分；
• A[i+1], A[i+2], ..., A[j-1] 作为第二部分；
• A[j], A[j+1], ..., A[A.length - 1] 是第三部分。
• 这三个部分所表示的二进制值相等。

如果无法做到，就返回 [-1, -1]。

注意，在考虑每个部分所表示的二进制时，应当将其看作一个整体。例如，[1,1,0] 表示十进制中的 6，而不会是 3。此外，前导零也是被允许的，所以 [0,1,1] 和 [1,1] 表示相同的值。

示例 1：

输入：[1,0,1,0,1]
输出：[0,3]

示例 2：

输出：[1,1,0,1,1]
输出：[-1,-1]

提示：

1. 3 <= A.length <= 30000
2. A[i] == 0 或 A[i] == 1

思路

每组1的数目肯定相等。于是先统计1的位置并保存为bit，之后看bit的长度是否大于3、是否能被3整除。

能被3整除的情况下，分成三分，每份为t。每一份中1肯定都是t个，前缀0可以忽略，因此应该看后缀0有多少。前两份的前缀0和后面的后缀0混合在一起，可以自由组合，因此先不看。只看第3份的后缀0。如果第3份的后缀0个数比前两份之间的都多，也是不行的。在第三分的后缀0个数小于1、2和2、3之间的0的个数的时候，分别从第1份最后一个1后面延伸相应个数的0、第2份最后一个1后面延伸相应个数的0，返回位置即为答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    vector<int> threeEqualParts(vector<int>& arr) {
        vector<int> bit;
        int len = arr.size();
        for(int i=0;i<arr.size();i++)
        if(arr[i]==1)
        bit.push_back(i);
        if(bit.size()%3) return {-1,-1};
        if(bit.empty()) return {0,2};
        int t = bit.size()/3;
        int back_zero = len - 1 - bit.back();
        if(back_zero>bit[2*t]-bit[2*t-1]-1||back_zero>bit[t]-bit[t-1]-1)
        return {-1,-1};
        vector<int> first(bit.begin(),bit.begin()+t);
        vector<int> second(bit.begin()+t,bit.begin()+2*t);
        vector<int> third(bit.begin()+2*t,bit.end());
        for(int i=t-1;i>0;--i){
            if(first[i]-first[i-1]!=second[i]-second[i-1]||
            first[i]-first[i-1]!=third[i]-third[i-1]) 
            return {-1,-1};
        }
        int i = bit[t-1]+back_zero;
        int j = bit[2*t-1]+back_zero+1;
        return {i,j};
    }
};

题目

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。

子数组 定义为原数组中的一个连续子序列。

请你返回 arr 中 所有奇数长度子数组的和 。

示例 1：

输入：arr = [1,4,2,5,3]
输出：58
解释：所有奇数长度子数组和它们的和为：
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

示例 2：

输入：arr = [1,2]
输出：3
解释：总共只有 2 个长度为奇数的子数组，[1] 和 [2]。它们的和为 3 。

示例 3：

输入：arr = [10,11,12]
输出：66

提示：

1 <= arr.length <= 100
1 <= arr[i] <= 1000

思路

• 暴力

• 统计次数，运用乘法

  对于arr[i] ，在包含arr[i]的前提下，其左侧有i+1个数字，右侧有arr.size()-i个数字。

  如果左边分别取0、2、4、8……等偶数个临近数字作为一组，右边则也应该取偶数长度的数字作为一组，这样合并后正好是奇数个长度。因此arr[i]在这种条件下会加(i+1+1)/2*(arr.size()-i+1)/2次。这个公式可以通过带入几个数字找到规律。

  如果左边分别取1、3、5、7……等奇数个临近数字作为一组，右边也应该取奇数长度的数字作为一组，这样合并吼正好是奇数个长度。因此arr[i]在这种条件下会加(i+1)/2*(arr.size()-i)/2次。这个公式可以通过带入几个数字找到规律。

  解释下(i+1+1)/2*(arr.size()-i+1)/2：

  • 对于i为奇数的情况：左边可以有0、2、4……i+1总共(i+2)/2个情况。
  • 对于i为偶数的情况：左边可以有0、2、4……i个总共i/2+1个。

  以上可以统一为(i+2)/2。

  奇数同理。

代码

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        int s = 0;
        for(int i=0;i<arr.size();i++){
            int leftOdd = (i+2)/2,leftEven = (i+1)/2;
            int rightOdd = (arr.size()-i+1)/2,rightEven=(arr.size()-i)/2;
            s+=(leftOdd*rightOdd+leftEven*rightEven)*arr[i];
        }
        return s;
    }
};