题目

设计一个支持在平均 时间复杂度 O(1) 下， 执行以下操作的数据结构。

注意: 允许出现重复元素。

1. insert(val)：向集合中插入元素 val。
2. remove(val)：当 val 存在时，从集合中移除一个 val。
3. getRandom：从现有集合中随机获取一个元素。每个元素被返回的概率应该与其在集合中的数量呈线性相关。

示例:

// 初始化一个空的集合。
RandomizedCollection collection = new RandomizedCollection();

// 向集合中插入 1 。返回 true 表示集合不包含 1 。
collection.insert(1);

// 向集合中插入另一个 1 。返回 false 表示集合包含 1 。集合现在包含 [1,1] 。
collection.insert(1);

// 向集合中插入 2 ，返回 true 。集合现在包含 [1,1,2] 。
collection.insert(2);

// getRandom 应当有 2/3 的概率返回 1 ，1/3 的概率返回 2 。
collection.getRandom();

// 从集合中删除 1 ，返回 true 。集合现在包含 [1,2] 。
collection.remove(1);

// getRandom 应有相同概率返回 1 和 2 。
collection.getRandom();

思路

用一个vector保存所有的键。
用一个哈希表保存键和对应的在vector的下标。
插入：在键对应的下标中加入一个
随机获得：生成随机数在vector中获取一个。
删除：
将vector最后一个元素key取出来，key对应的下标end也取出来。
首先把要删除val的元素在vector中的一个位置idx赋给key，之后在哈希表key的下标中删除end，添加上val的下标idx。从val的下标中删除idx即可。
**这里不太明白的事为什么要有if(idx<end) m[keys[idx]].emplace(idx)一句，如果这句换了位置就不对了，一直没明白`

代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

class RandomizedCollection {
public:
    unordered_map<int,unordered_set<int>> m;
    vector<int> keys;

    /** Initialize your data structure here. */
    RandomizedCollection() {

    }
    
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    bool insert(int val) {
        keys.push_back(val);
        if(m.find(val)==m.end()){
            m[val].emplace(int(keys.size()-1));
            return true;
        }else{
            m[val].emplace(int(keys.size()-1));
            return false;
        }
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    bool remove(int val) {
        if(m.find(val)==m.end()) return false;
        //取得最后一个key对应的下标end，要删除的元素所有下标的第一个        
        int end = keys.size() - 1;
        int idx = *m[val].begin();
        //最后一个key赋值到要删除的位置上，并且最后一个key要删除end这个下标。
        keys[idx] = keys.back();
        m[keys[idx]].erase(end);
        //要删除的元素删除一个下标，如果是最后一个，就把元素从哈细表中删除。
        m[val].erase(idx);
        if(m[val].empty()) m.erase(val);
        //如果删除元素的下标不是最后一个，就把删除的下标赋给原来最后一个key。
        if(idx<end) m[keys[idx]].emplace(idx);

        keys.pop_back();
        return true;
    }
    
    /** Get a random element from the collection. */
    int getRandom() {
        return keys[rand()%keys.size()];
    }
};

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * RandomizedCollection* obj = new RandomizedCollection();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */

题目

给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含 **连续的1 **的个数。

示例 1:

输入: 5
输出: 5
解释:
下面是带有相应二进制表示的非负整数<= 5：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。

说明: 1 <= n <= 109

思路

说实话没怎么懂，看 @宫水三叶 的讲解，抄了抄代码。
@宫水三叶的 讲解

这是一道典型的「数位 DP」题。

对于「数位 DP」题，都存在「询问 [ a , b ] [a, b] [a,b]（ a a a 和 b b b 均为正整数，且 a < b a < b a<b）区间内符合条件的数值个数为多少」的一般形式，通常我们需要实现一个查询 [ 0 , x ] [0, x] [0,x] 有多少合法数值的函数 int dp(int x)，然后应用「容斥原理」求解出 [ a , b ] [a, b] [a,b] 的个数： d p ( b ) − d p ( a − 1 ) dp(b) - dp(a - 1) dp(b)−dp(a−1)。
对于本题，虽然只需要求解 [ 0 , n ] [0, n] [0,n] 范围内数的个数，但其实拓展到求 [ a , b ] [a, b] [a,b] 区间个数的也不会增加难度。

具体的，对于「数位 DP」问题通常是「从高位到低位」的分情况讨论。

不失一般性的考虑数值 n n n 的某一位 c u r cur cur 是如何被处理的：

1. 如果当前位 c u r = 1 cur = 1 cur=1 的话，由于我们需要满足「小于等于 n n n」的要求，因此如果该位填 0 0 0 的话，后面的低位填什么都是满足要求的，因此我们期望能够查表得出「长度为 i + 1 i + 1 i+1，且二进制位置 i i i 数值为 0 0 0 时」有多少合法数值，将其累加到答案中；
   与此同时，我们需要确保当前位选 1 1 1 是合法的，即我们需要记录上一位 p r e v prev prev 是什么，确保 c u r cur cur 和 p r e v prev prev 不同时为 1 1 1。
2. 如果当前位 c u r = 0 cur = 0 cur=0 的话，我们只能选 0 0 0，并决策下一位。

当出现「当前位无法填入 c u r cur cur」或者「决策到最低位」时，则完成了所有合法答案的统计。

至于流程 1 1 1 中的查表操作，我们可以使用 static 预处理出 f 数组，定义 f [ i ] [ j ] f[i][j] f[i][j] 为考虑二进制长度为 i i i，且最高位为 j j j（ 0 0 0 or 1 1 1）时的合法数个数。

注意：为了防止重复计数问题，我们在不失一般性的计算 f [ i ] [ 0 ] f[i][0] f[i][0] 和 f [ i ] [ 1 ] f[i][1] f[i][1] 时，不能采用诸如 f [ i ] [ c u r ] + = f [ i − 1 ] [ p r e v ] f[i][cur] += f[i - 1][prev] f[i][cur]+=f[i−1][prev] 的 “后向查找依赖” 的方式进行转移，而要采用 f [ i + 1 ] [ c u r ] + = f [ i ] [ p r e v ] f[i + 1][cur] += f[i][prev] f[i+1][cur]+=f[i][prev] “前向主动更新” 的方式进行转移。

不失一般性的考虑 f [ i ] [ 0 ] f[i][0] f[i][0] 和 f [ i ] [ 1 ] f[i][1] f[i][1] 能够更新哪些状态：

• 如果期望当前位填 0 0 0 的话，需要统计所有满足 ( 0… ) 2 (0…)_2 (0…)2​ 形式的合法数值，当前位的低一位只能填 1 1 1（填 0 0 0 会出现重复计数，即需要忽略前导零的数值），此时有： f [ i + 1 ] [ 0 ] = f [ i ] [ 1 ] f[i + 1][0] = f[i][1] f[i+1][0]=f[i][1]；

• 如果期望当前位填 1 1 1 的话，需要统计所有满足 ( 1… ) 2 (1…)_2 (1…)2​ 和 ( 0… ) 2 (0…)_2 (0…)2​ 形式的合法数值：

• ( 1… ) 2 (1…)_2 (1…)2​ 时，当前位的低一位只能填 0 0 0；此时有： f [ i + 1 ] [ 1 ] + = f [ i ] [ 0 ] f[i + 1][1] += f[i][0] f[i+1][1]+=f[i][0]； * ( 0… ) 2 (0…)_2 (0…)2​ 时，当前位的低一位只能填 1 1 1；此时有： f [ i + 1 ] [ 1 ] + = f [ i ] [ 1 ] f[i + 1][1] += f[i][1] f[i+1][1]+=f[i][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

class Solution {
public:
    int findIntegers(int n) {
        if(!n) return 1;
        int N = 32;
        int dp[N][2];
        memset(dp,0,sizeof(int)*N*2);
        dp[1][0] = 1;
        dp[1][1] = 2;
        for(int i=1;i<N-1;++i){
            dp[i+1][0] = dp[i][1];
            dp[i+1][1] = dp[i][0]+dp[i][1];
        }
        int pre = 0,ans=0,idx=31;
        for(;idx>=0;--idx){
            if(((n>>idx)&1)==1) break;
        }
        for(;idx>=0;--idx){
            int cur = (n>>idx)&1;
            if(cur==1) ans+=dp[idx+1][0];
            if(pre==1&&cur==1) break;
            pre=cur;
            if(idx==0) ans++;
        }
        return ans;
    }
};

题目

假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。

给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。

最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。

总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。

答案保证在 32 位有符号整数范围内。

示例 1：

输入：k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
输出：4
解释： 由于你的初始资本为 0，你仅可以从 0 号项目开始。
在完成后，你将获得 1 的利润，你的总资本将变为 1。
此时你可以选择开始 1 号或 2 号项目。
由于你最多可以选择两个项目，所以你需要完成 2 号项目以获得最大的资本。
因此，输出最后最大化的资本，为 0 + 1 + 3 = 4。

示例 2：

输入：k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
输出：6

提示：

• 1 <= k <= 105
• 0 <= w <= 109
• n == profits.length
• n == capital.length
• 1 <= n <= 105
• 0 <= profits[i] <= 104
• 0 <= capital[i] <= 109

  思路

• 银行家算法*
  将capital和profits配对，并按照captial从小到大进行排序。
  每次对比w和capitali，如果w比capitali大，则将对应的profitsi加入到优先队列中。
  全部加完后，从优先队列中选择最大的profits加到w中。
  重复上述k次。

  代码

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

  class Solution { public: int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) { int n = profits.size(); vector<pair<int,int>> arr(n); priority_queue<int,vector<int>,less<int>> pq; for(int i=0;i<n;++i){ arr[i] = {capital[i],profits[i]}; } int idx = 0; sort(arr.begin(),arr.end()); for(int i=0;i<k;++i){ while(idx<n&&arr[idx].first<=w){ pq.push(arr[idx++].second); } if(!pq.empty()){ w+=pq.top(); pq.pop(); }else{ break; } } return w; } }

题目

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