题目链接：233. 数字 1 的个数 - 力扣（LeetCode）
解析：
这道题我是用排列组合做的，可以看题目注释
// 整体思想：// 1、从左到右，针对第k位数减一后，后边的n - k位子可以0~9排列组合// 2、先用总的排列组合 - 没有1的排列组合// 3、这总共n - k + 1位中，如果一个数有j个1，那么结果就需要多加 j - 1，因为排列组合只算了一个1// 所以需要把有多个1的情况算一下，范围一般是1 ~ n - k （如果这个第k位数减1后还大于等于1的话就是 n - k + 1）// 第k位处理完之后，接着定住第k位原来的数，然后处理k - 1位，依次到最后一位// “定住k位原来的数”这个操作要注意，如果原来是1，那么处理下面几位进行第2、3步时要加上这些1的个数class Solution { public:int C(int a, int b) {int child = 1;for (int i = a; i > a - b; i--) {child *= i;}int father = 1;for (int i = b; i > 0; i--) {father *= i;}return child / father;}int get_extra_ones(const int& extra, const int& high, const int& pre_one_cnt) {int total = 0;// for (int j = 1; j <= extra; j++) {// 第一位不为1int has_one_cnt = C(extra, j) * pow(9, extra - j) * (high == 0 ? 1 : high);if (high > 0) {// 第一位为1has_one_cnt += C(extra, j - 1) * pow(9, extra - j + 1);}total += (j - 1 + pre_one_cnt) * has_one_cnt;}// 如果高位减一的数还大于等于1，全为1的情况，应该再加上这些if (high > 0)// 还需要加上前面几位有1的个数total += (extra + pre_one_cnt);return total;}int get_one_cnt(const string& str) {int n = str.size();int ret = 0;int pre_one_cnt = 0;for (int i = 0; i < n; i++) {if (str[i] == '0') {continue;}int high = str[i] - '0' - 1;int extra = n - i - 1;int total = pow(10, extra) * (high + 1);int no_one = pow(9, extra) * (high == 0 ? 1 : high);// 减没有1的排列组合时，要加上前面几位有1的个数total += no_one * (pre_one_cnt - 1);total += get_extra_ones(extra, high, pre_one_cnt);if (str[i] == '1') pre_one_cnt++;ret += total;}ret += pre_one_cnt;return ret;}int countDigitOne(int n) {string str = to_string(n);return get_one_cnt(str);} };