本文涉及的基础知识点
题目
给定一个按 非递减顺序 排列的数字数组 digits 。你可以用任意次数 digits[i] 来写的数字。例如，如果 digits = [‘1’,‘3’,‘5’]，我们可以写数字，如 ‘13’, ‘551’, 和 ‘1351315’。
返回 可以生成的小于或等于给定整数 n 的正整数的个数 。
示例 1：
输入：digits = [“1”,“3”,“5”,“7”], n = 100
输出：20
解释：
可写出的 20 个数字是：
1, 3, 5, 7, 11, 13, 15, 17, 31, 33, 35, 37, 51, 53, 55, 57, 71, 73, 75, 77.
示例 2：
输入：digits = [“1”,“4”,“9”], n = 1000000000
输出：29523
解释：
我们可以写 3 个一位数字，9 个两位数字，27 个三位数字，
81 个四位数字，243 个五位数字，729 个六位数字，
2187 个七位数字，6561 个八位数字和 19683 个九位数字。
总共，可以使用D中的数字写出 29523 个整数。
示例 3:
输入：digits = [“7”], n = 8
输出：1
参数范围：
1 <= digits.length <= 9
digits[i].length == 1
digits[i] 是从 ‘1’ 到 ‘9’ 的数
digits 中的所有值都 不同
digits 按 非递减顺序 排列
1 <= n <= 109
分析
假定n是m位数，digits.length的长度是k。
[1,m)位数显然都小于n。x位数都可以任意选择，所以可能是pow(k,x)。
x大于m，显然大于n，直接淘汰。
x等于m，则要分情况讨论。
| 最高位的数小于n的最高位 |
| 最高位的数等于n的最高位，次高位小于n的次高位 |
| 最高位、次高位等于n，第三高位小于n的第三高位 |
| … |
| 高位和n的高位相等，个位小于n |
| 和n相等 |
注意
和n相等的数不一定存在。
digits[i]没重复数据，没有0，已经按升序排序。
代码
核心代码
class Solution { public: int atMostNGivenDigitSet(vector& digits, int n) { vector vValues; for (const auto& s : digits) { vValues.emplace_back(s[0] - ‘0’); } string strN = std::to_string(n); int iRet = 0; //假定n是m位数，那么[1,m)位一定符合 int iCur = vValues.size(); for (int i = 1; i < strN.length(); i++) { iRet += iCur; iCur *= vValues.size(); } iCur /= vValues.size(); for (int i = 0; i < strN.length(); i++) { const int iLessNum = std::lower_bound(vValues.begin(), vValues.end(), strN[i]-‘0’) - vValues.begin(); const int iLessEqualNum = std::upper_bound(vValues.begin(), vValues.end(), strN[i] - ‘0’) - vValues.begin(); iRet += iCur * iLessNum;//从左到右第i位小于n的数的数量 if (iLessNum == iLessEqualNum) { break; } iCur /= vValues.size(); if (i + 1 == strN.length()) { iRet++;//完全相等 } } return iRet; } };
测试用例
template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector digits; int n; int res; { digits = { “1”, “3”, “5”, “7” }; int n = 100; res = Solution().atMostNGivenDigitSet(digits,n); Assert(20, res); } { digits = { “1”, “4”, “9” }; int n = 1000000000; res = Solution().atMostNGivenDigitSet(digits, n); Assert(29523, res); } { digits = { “7” }; int n = 8; res = Solution().atMostNGivenDigitSet(digits, n); Assert(1, res); }
//CConsole::Out(res);
}
2023年8月代码
class Solution { public: int atMostNGivenDigitSet(vector& digits, int n) { int iBitNum = 0; int tmp = n; while (tmp > 0) { iBitNum++; tmp /= 10; } std::set nums; for (const auto& s : digits) { nums.insert(s[0] - ‘0’); } int iMul = 1; int iMul10 = 1; int iResultNum = 0; for (int i = 0; i+1 < iBitNum; i++) { iMul *= nums.size(); iResultNum += iMul; iMul10 = 10; } for (int i = 0; i < iBitNum; i++) { int iCurBitNum = n / iMul10%10; auto it = nums.equal_range(iCurBitNum); iResultNum += iMulstd::distance(nums.begin(), it.first); if ( it.first == it.second ) { break; } else { if (iBitNum-1 == i) { iResultNum++; } } iMul10 /= 10; iMul /= nums.size(); } return iResultNum; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 洒家想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 墨家名称的来源：有所得以墨记之。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
