题目

给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

由于答案可能很大，因此 返回答案模 10^9 + 7 。

示例 1：

1
2
3
4
5

输入：arr = [3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。 
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。

示例 2：

1
2
3

输入：arr = [11,81,94,43,3]
输出：444

提示：

• 1 <= arr.length <= 3 * 104
• 1 <= arr[i] <= 3 * 104

思路

用一个栈保存到达i位置时左侧更小值的位置。

dp：以arr[i]为结尾的所有数组的最小值之和。

dp[i+1] = (dp[s.top()+1]+(i-s.top())*arr[i])

dp[s.top()+1]表示s.top()以及之前的所有数组，其数组最小值都是比arr[i]小的，所以前面的延伸到当前arr[i]，最小值不变，其和不变。

(i-s.top())*arr[i]表示以arr[i]为结尾并且以arr[i]为最小值的数组的和。

代码

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

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        int* dp = new int[arr.size()+1];
        int* stack = new int[arr.size()+1];
        memset(dp,0,sizeof(int)*(arr.size()+1));
        memset(stack,0,sizeof(int)*(arr.size()+1));
        int top=-1;
        int mod = 1000000007;
        stack[++top]=-1;
        for(int i=0;i<arr.size();++i){
            while(top>0&&arr[i]<=arr[stack[top]]) top--;
            dp[i+1] = (dp[stack[top]+1]+(i-stack[top])*arr[i])%mod;
            stack[++top]=i;
        }
        int res = 0;
        for(int i=0;i<=arr.size();++i){
            res=(res + dp[i])%mod;
        }
        return res;
    }
};

题目

实现RandomizedSet 类：

• RandomizedSet() 初始化 RandomizedSet 对象
• bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
• bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
• int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

示例：

输入
[“RandomizedSet”, “insert”, “remove”, “insert”, “getRandom”, “remove”, “insert”, “getRandom”]
[[], [1], [2], [2], [], [1], [2], []]
输出
[null, true, false, true, 2, true, false, 2]

解释
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomizedSet.remove(2); // 返回 false ，表示集合中不存在 2 。
randomizedSet.insert(2); // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
randomizedSet.getRandom(); // getRandom 应随机返回 1 或 2 。
randomizedSet.remove(1); // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
randomizedSet.insert(2); // 2 已在集合中，所以返回 false 。
randomizedSet.getRandom(); // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。

提示：

• -231 <= val <= 231 - 1
• 最多调用 insert、remove 和 getRandom 函数 2 * ``105 次
• 在调用 getRandom 方法时，数据结构中 至少存在一个 元素。

  思路

  一个vector保存所有的key。一个map保存key和在vector中对应的下标。
  插入：在vector中加入该值，在map中加入<该值，下标>
  随机获得：生成随机数在vector中获取一个。
  删除：
  vector最后一个元素key放到val的位置上：vector的val对应的位置设置为key，哈希表的key键对应的位置设置为val的值，之后分别删除vector的最后一个元素和哈希表的val元素即可。

  代码

  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

  class RandomizedSet { public: /** Initialize your data structure here. */ unordered_map<int,int> m; vector<int> keys; RandomizedSet() { } /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */ bool insert(int val) { if(m.find(val)!=m.end()) return false; keys.push_back(val); m[val] = keys.size()-1; return true; } /** Removes a value from the set. Returns true if the set contained the specified element. */ bool remove(int val) { if(m.find(val)==m.end()) return false; int temp = keys[keys.size()-1]; m[temp] = m[val]; keys[m[temp]] = temp; keys.pop_back(); m.erase(val); return true; } /** Get a random element from the set. */ int getRandom() { return keys[rand()%keys.size()]; } }; /** * Your RandomizedSet object will be instantiated and called as such: * RandomizedSet* obj = new RandomizedSet(); * bool param_1 = obj->insert(val); * bool param_2 = obj->remove(val); * int param_3 = obj->getRandom(); */

题目

设计一个支持在平均 时间复杂度 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();
 */

题目

给你一个字符串 s 和一个字符串数组 dictionary 作为字典，找出并返回字典中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字典序最小的字符串。如果答案不存在，则返回空字符串。

示例 1：

输入：s = “abpcplea”, dictionary = [“ale”,”apple”,”monkey”,”plea”]
输出：“apple”

示例 2：

输入：s = “abpcplea”, dictionary = [“a”,”b”,”c”]
输出：“a”

提示：

• 1 <= s.length <= 1000
• 1 <= dictionary.length <= 1000
• 1 <= dictionary[i].length <= 1000
• s 和 dictionary[i] 仅由小写英文字母组成

  思路

  暴力求解。
  对于dictionary~i~，按照顺序与s进行比较，看看dictionary~i~在s中是否能够按顺序都找到。如果能找到，就比较长度，长度相等则比较字典序。

  代码

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

  class Solution { public: string findLongestWord(string s, vector<string>& dictionary) { int res_id = -1; for(int i=0;i<dictionary.size();++i){ if(dictionary[i].length()>s.length()) continue; int j=0; for(int k=0;k<s.size();++k){ if(s[k]==dictionary[i][j]) j++; } if(j!=dictionary[i].length()) continue; if(res_id==-1|| dictionary[i].length()>dictionary[res_id].length()|| (dictionary[i].length()==dictionary[res_id].length()&&dictionary[i]<dictionary[res_id])){ res_id = i; } } if(res_id==-1) return ""; return dictionary[res_id]; } };

题目

给定平面上n 对 互不相同 的点 points ，其中 points[i] = [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。

返回平面上所有回旋镖的数量。

示例 1：

输入：points = [[0,0],[1,0],[2,0]]
输出：2
解释：两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]]

示例 2：

输入：points = [[1,1],[2,2],[3,3]]
输出：2

示例 3：

输入：points = [[1,1]]
输出：0

提示：

• n == points.length
• 1 <= n <= 500
• points[i].length == 2
• -104 <= xi, yi <= 104
• 所有点都 互不相同

  思路

  暴力的话为O(N^3^)。
  使用哈细表做到O(N^2^)。
  遍历每个点i，以i为锚点，遍历其他所有节点j。计算j与i的距离，将距离加入到哈细表中。
  对于每个i遍历之后，遍历哈希表，哈希表中如果有大于2的值，则为n*(n-1)。
• 优化**：设现在哈希表项为n，则对应的值为n(n-1)。如果增加了一个，则为(n+1)n，两者相差2n，因此每次添加到哈希表的时候，如果哈希表的值大于1，则直接将当前值加上2*n即可。这样免去了在此遍历一次哈希表的过程。

  代码

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

  class Solution { public: int numberOfBoomerangs(vector<vector<int>>& points) { int cnt = 0; for(int i=0;i<points.size();++i){ unordered_map<int,int> m; for(int j=0;j<points.size();++j){ if(i==j) continue; int k = pow(points[j][0]-points[i][0],2)+pow(points[j][1]-points[i][1],2); if(m.find(k)==m.end()) { m[k] = 1; }else { cnt += 2 * m[k]; m[k]+=1; } } } return cnt; } };

题目

给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

1. 任何左括号 ( 必须有相应的右括号 )。
2. 任何右括号 ) 必须有相应的左括号 ( 。
3. 左括号 ( 必须在对应的右括号之前 )。
4. * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
5. 一个空字符串也被视为有效字符串。

示例 1:

输入: “()”
输出: True

示例 2:

输入: “(*)”
输出: True

示例 3:

输入: “(*))”
输出: True

注意:

1. 字符串大小将在 [1，100] 范围内。

   思路

   主要是(和*的问题。
   总体思路：(和*分别按照相同和相对来看，最后比较记录的(与*相同与不同时的数量即可。
   可以用栈，也可以直接记录，毕竟栈在这里的用途也是记录(和*的数量的。
   lo记录(与*不同时的数量，hi记录(和*相同时的数量。因此当hi<0的时候一定不行（有括号大于做括号和*之和）
   整个遍历结束后，hi肯定是要>=0的，这个时候只需要看lo就可以了，如果lo<=0，那么说明(的数量小鱼等于*的数量，*经过变换可以抵消所有的(。

   代码

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

   class Solution { public: bool checkValidString(string s) { int lo = 0, hi = 0; for(char c:s){ if(c=='('){ lo++; hi++; }else if(c==')'){ lo = max(0,lo-1); hi--; if(hi<0) return false; }else{ lo = max(0,lo-1); hi++; } } return lo<=0; } };

题目

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

• 例如， [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); } };

题目

我们正在玩一个猜数游戏，游戏规则如下：

我从 **1 **到 n 之间选择一个数字，你来猜我选了哪个数字。

每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。

然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。直到你猜到我选的数字，你才算赢得了这个游戏。

示例:

n = 10, 我选择了8.

第一轮: 你猜我选择的数字是5，我会告诉你，我的数字更大一些，然后你需要支付5块。
第二轮: 你猜是7，我告诉你，我的数字更大一些，你支付7块。
第三轮: 你猜是9，我告诉你，我的数字更小一些，你支付9块。

游戏结束。8 就是我选的数字。

你最终要支付 5 + 7 + 9 = 21 块钱。

给定 n ≥ 1，计算你至少需要拥有多少现金才能确保你能赢得这个游戏

思路

刚开始没看明白，看了解析才知道。
设置数组dp，其中dp[i][j]表示从i到j所需拥有多仨后现金才能保证赢得这个游戏。
因此最后返回dp[1][n]即可。

对于dp[i][j]，其值应该为：每次猜测结果为x的时候，dp[i][x-1]与dp[x+1][j]中的最大值与猜测的x相加，这样才能保证但在dp[i][j]内所有的猜测组合都可以在某个现金之内完成。
从n->0开始遍历i，对于每个i，从i-n遍历j，对于里面的所有j，选择预测为x的时候，选择dp[i][x-1]与dp[x+1][j]中的最大值与其相加相加即可。
对于

代码

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

class Solution {
public:
    int getMoneyAmount(int n) {
        int dp[n+2][n+2];
        memset(dp,0,sizeof(int)*(n+2)*(n+2));
        for(int i=n;i>=1;--i){
            for(int j = i;j <= n;++j){
                if(i==j) dp[i][j] = 0;
                else{
                    dp[i][j] = INT_MAX;
                    for(int x=i;x<=j;++x){
                        dp[i][j] = min(dp[i][j],max(dp[i][x-1],dp[x+1][j])+x);
                    }
                }
            }
        }
        return dp[1][n];
    }
};

题目

给定两个以升序排列的整数数组 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; } };

题目

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