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