1. 题目列表

• 十进制整数的反码(进制转换）
• 总持续时间可被 60 整除的歌曲（数组hash以及简单的排列组合）
• 在 D 天内送达包裹的能力（二分查找，贪心策略，）重要
• 至少有 1 位重复的数字（问题转换，排列组合）重要

2. 十进制整数的反码

简单进制转换。

代码：

class Solution {
public:
    int bitwiseComplement(int N) {
        if (N == 0) return 1;
        vector<int> bits;
        while (N){
            bits.push_back(N % 2);
            N /= 2;
        }
        for (int i = 0; i < bits.size(); i++)
            bits[i] = bits[i] ? 0 : 1;
        int res = 0, base = 1;
        for (int i = 0; i < bits.size(); i++){
            res += bits[i] * base;
            base *= 2;
        }
        return res;
    }
};

3. 总持续时间可被 60 整除的歌曲

先用hashtable记录每个整数出现的次数，再用set记录所有的不重复整数。
遍历set，对于元素e，枚举e ~ 500所有的整数i，判断(e + i)是否能被60整除，如果能整除，计算整数对数。

整数对数的讨论：
当e == i，对数 = C(n,2), n为元素e出现的次数
当e != i，对数 = C(n1,1) + C(n2,1)，n1和n2分别为e和i出现的次数。

代码：

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        int hashtable[510];
        unordered_set<int> t;
        memset(hashtable, 0, sizeof(hashtable));
        for (int i = 0; i < time.size(); i++){
            hashtable[time[i]]++;
            t.insert(time[i]);
        }
        int res = 0;
        unordered_set<int>::iterator iter;
        for (iter = t.begin(); iter != t.end(); iter++){
            int e = *iter;
            for (int i = e; i <= 500; i++){
                if ((e + i) % 60 == 0){
                    if (i == e)
                        res += (hashtable[i] * (hashtable[i] - 1)) / 2;
                    else
                        res += hashtable[i] * hashtable[e];
                }
            }
        }
        return res;
    }
};

4. 在 D 天内送达包裹的能力

二分搜索 + 贪心模拟：

要有敏锐的嗅觉，输出答案存在明显的范围，很有可能可用二分查找。

二分查找的关键是：如何寻找贪心策略。本题的贪心是尽可能在D天内使得船的载重量最小，船的载重范围[max(weights), sum(weights)]

这样，思路很明了，给定船的当前载重为mid，判断能否在D天内装满所有的货物，如果能，则搜索[l,mid]，否则搜索[mid + 1, r]

代码：

class Solution {
public:
    int shipWithinDays(vector<int>& weights, int D) {
        int sum = 0, MAX = -1;
        for (int i = 0; i < weights.size(); i++){
            sum += weights[i];
            MAX = max(MAX, weights[i]);
        }
        int l = MAX, r = sum, mid;
        while (l < r){
            mid = (l + r) / 2;
            int temp = 0, days = 1;
            for (int i = 0; i < weights.size(); i++){
                temp += weights[i];
                if (temp > mid){
                    days++;
                    temp = weights[i];
                }
            }
            if (days <= D){
                r = mid;
            }else l = mid + 1;
        }
        return r;
    }
};

5. 至少有 1 位重复的数字

排列组合：
注意转换思路，当讨论重复位过于复杂时，转换问题为计算1~N的不重复位数有多少个。

具体步骤：
假设N的位数为p，先计算1~p-1位的不重复位的个数。如97783，p = 5，设位数为i
i = 1时， 共9种
i = 2时， 共9 * 9 = 81种
i = 3时， 共9 * 9 * 8种
i = 4时， 共9 * 9 * 8 * 7种
i = 5时， 需要逐位讨论，设讨论的当前位为j
j = 1时，计算第一位小于N[1]的个数，_ _ _ _ _ 共8 * 9 * 8 * 7 * 6种
j = 2时，计算第二位小于N[2]的个数，9_ _ _ _ _ 共 7 * 8 * 7 * 6种，
j = 3时，计算第三位小于N[3]的个数，97_ _ _ 共7 * 7 * 6种，
j = 4时，计算第四位小于N[4]的个数，977_ _ _，此时出现重复位，则不用计算剩下的位数。
res = N - sum
注意：特判N < 10，return 0

代码：

class Solution {
public:
    int numDupDigitsAtMostN(int N) {
        if (N < 10) return 0;
        int a = N; // 拷贝N
        int p = 0;
        vector<int> digits;
        while (N){
            p++;
            digits.push_back(N % 10);
            N /= 10;
        }
        int sum = 0;
        for (int i = 1; i < p; i++){
            int cnt = 9;
            for (int j = 1; j < i; j++)
                cnt = cnt * (10 - j);
            sum += cnt;
        }
        reverse(digits.begin(), digits.end());
        int len = digits.size();
        int hash[11];
        memset(hash, 0, sizeof(hash));
        for (int i = 0; i < len; i++){
            int cnt = 0;
            if (i == 0){
                cnt = digits[i] - 1;
                hash[digits[i]] = 1;
                if (cnt <= 0) continue;
                for (int j = 1; j <= len - 1; j++)
                    cnt *= (10 - j);
                sum += cnt;
            }else if(i == len - 1){
                for (int j = 0; j <= digits[i]; j++){
                    if (!hash[j]) cnt++;
                }
                sum += cnt;
            }else{
                int cf = 0; // 定义当前位与前导位重复位的个数
                for (int j = 0; j < digits[i]; j++){
                    if (hash[j]) cf++;
                }
                cnt = digits[i] - cf; // 当前位的可选个数 = 0 ~ (digits[i] - 1) - 重复位个数 
                for (int j = i + 1; j < len; j++){
                    cnt *= (10 - j); // 剩余位可选择的个数
                }
                sum += cnt;
                if (hash[digits[i]] == 1){ // 如果当前位与前导位存在重复位，那么后续位不存在满足条件的数
                    break;
                }
                hash[digits[i]] = 1; // 记录当前位已存在
            }
        }
        return a - sum;
    }
};