题目

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

• 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

• 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

示例 1：

输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。

示例 2：

输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

示例 3：

输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2

提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

  思路

  既然可以删除，那么只要记录下上升和下降的趋势，每次下降时，就在上省得基础上+1，每次上升时，就在下降的基础上+1，最后选择最大值即可。

  代码

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

  class Solution { public: int wiggleMaxLength(vector<int>& nums) { int n = nums.size(); if(n<2) return n; int p=1,d=1; for(int i=1;i<n;++i){ if(nums[i]>nums[i-1]) p=d+1; if(nums[i]<nums[i-1]) d=p+1; } return max(p,d); } };

题目

给定两个以升序排列的整数数组 nums1 和 nums2, 以及一个整数 k。

定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2。

请找到和最小的 k 个数对 (u1,v1),  (u2,v2)  …  (uk,vk) 。

示例 1:

输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
输出: [1,2],[1,4],[1,6]
解释: 返回序列中的前 3 对数：
[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]

示例 2:

输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
输出: [1,1],[1,1]
解释: 返回序列中的前 2 对数：
  [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]

示例 3:

输入: nums1 = [1,2], nums2 = [3], k = 3
输出: [1,3],[2,3]
解释: 也可能序列中所有的数对都被返回:[1,3],[2,3]

提示:

• 1 <= nums1.length, nums2.length <= 104
• -109 <= nums1[i], nums2[i] <= 109
• nums1, nums2 均为升序排列
• 1 <= k <= 1000

  思路

  抄的题解的思路
  使用最大堆来对已经保存的数据对排序。
  最大堆保存两者的值之和，在两个数组中对应的下标。
  首先将一个数组A的第一个和另一个数组B的全部进行组合，记录下数组A、B的下标（这里对于数组A都是0），第一个最小的对一定在这两个之间。
  之后每取出一个对（i，j），就以数组B的下标j为不变，数组A的下标后移一个加入到当前的优先队列中。
  每次新增的数组，下标一定与其中某一个已有下标，一定为之和相差1的关系
  因此每次选一个，加一个，能够把所有情况都考虑到。

  代码

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

  class Solution { public: vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) { if(k>nums1.size()*nums2.size()) k = nums1.size()*nums2.size(); if(!nums2.size()||!nums1.size()) return {}; priority_queue<pair<int,pair<int,int>>> h; for(int i=0;i<nums1.size();++i) h.push({-nums1[i]-nums2[0],{i,0}}); vector<vector<int>> res; while(res.size()<k){ auto t = h.top(); h.pop(); int i = t.second.first,j=t.second.second; res.push_back({nums1[i],nums2[j++]}); if(j<nums2.size()) h.push({-nums1[i]-nums2[j],{i,j}}); } return res; } };

题目

给定一个整数数组 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++]; } } };

题目

1109. 航班预订统计

难度中等 236

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，其中 answer[i] 是航班 i 上预订的座位总数。

示例 1：

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号 1 2 3 4 5
预订记录 1 ： 10 10
预订记录 2 ： 20 20
预订记录 3 ： 25 25 25 25
总座位数： 10 55 45 25 25
因此，answer = [10,55,45,25,25]

示例 2：

输入：bookings = [[1,2,10],[2,2,15]], n = 2
输出：[10,25]
解释：
航班编号 1 2
预订记录 1 ： 10 10
预订记录 2 ： 15
总座位数： 10 25
因此，answer = [10,25]

提示：

• 1 <= n <= 2 * 104
• 1 <= bookings.length <= 2 * 104
• bookings[i].length == 3
• 1 <= firsti <= lasti <= n
• 1 <= seatsi <= 104

思路

• 暴力

  时间复杂度为O(N^2^)。

• 观察实例：

  航班编号 1 2 3 4 5
  预订记录 1 ： 10 10
  预订记录 2 ： 20 20
  预订记录 3 ： 25 25 25 25
  总座位数： 10 55 45 25 25

  如果是对于bookings或者n分别进行嵌套循环的话，复杂度也是O(N^2^)，不可接受。因此思考O(N)的方法。

  对于firsti ,lasti ，可以发现每个seati都要加载firsti的位置，之后复制就可以了，在lasti之后的位置减去seati。因此可以先对数组进行遍历使得结果数组res在每个first出现的位置都加上seat，在每个last的后一个位置减去seat。最后进行前缀累加即可。

代码

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

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        vector<int> res(n+1,0);
        for(int i=0;i<bookings.size();++i){
            res[bookings[i][0]-1] += bookings[i][2];
            res[bookings[i][1]] -= bookings[i][2];
        }
        for(int j=1;j<n;j++){
            res[j] += res[j-1];
        }
        res.resize(n);
        return res;
    }
};

528. 按权重随机选择

给定一个正整数数组 w ，其中 w[i] 代

表下标 i 的权重（下标从 0 开始），请写一个函数 pickIndex ，它可以随机地获取下标 i，选取下标 i 的概率与 w[i] 成正比。

例如，对于 w = [1, 3]，挑选下标 0 的概率为 1 / (1 + 3) = 0.25 （即，25%），而选取下标 1 的概率为 3 / (1 + 3) = 0.75（即，75%）。

也就是说，选取下标 i 的概率为 w[i] / sum(w) 。

示例 1：

输入：
[“Solution”,”pickIndex”]
[[[1]],[]]
输出：
[null,0]
解释：
Solution solution = new Solution([1]);
solution.pickIndex(); // 返回 0，因为数组中只有一个元素，所以唯一的选择是返回下标 0。

示例 2

输入：
[“Solution”,”pickIndex”,”pickIndex”,”pickIndex”,”pickIndex”,”pickIndex”]
[[[1,3]],[],[],[],[],[]]
输出：
[null,1,1,1,1,0]
解释：
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // 返回 1，返回下标 1，返回该下标概率为 3/4 。
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 1
solution.pickIndex(); // 返回 0，返回下标 0，返回该下标概率为 1/4 。**

由于这是一个随机问题，允许多个答案，因此下列输出都可以被认为是正确的:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
……
诸若此类。

提示：

• 1 <= w.length <= 10000
• 1 <= w[i] <= 10^5
• pickIndex 将被调用不超过 10000 次

思路

随机+二分查找

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    vector<int> presum;
    Solution(vector<int>& w) {
        presum.resize(w.size()+1,0);
        for(int i=1;i<=w.size();i++) presum[i] = presum[i-1]+w[i-1];
    }
    
    int pickIndex() {
        int rnum = rand()%presum.back()+1;
        int left = 1, right = presum.size()-1,mid;
        while(left<right){
            mid=(left+right)/2;
            if(presum[mid]>=rnum) right=mid;
            else left=mid+1;
        }
        return right-1;
    }
};

题目

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;
    }
};