2018.10.5
感受到开学之后工作和课业的双重压力，加上近段时间自己出了点小事故，因此断更了许久。没事，继续。
这道题有两种复杂度为的算法。
方法1：递归（分段思想）。
所有数字出现1的个数 = 每一段数字中出现1的个数之和
1. 对于输出的数字n，其最高位为x，将其分成1-i、i+1-n两段。其中，i为n除以x的余数，i-n的数字数目为x倍数（例如n=21345，x为10000，则将n分为1-1345，1346-21345）。
2. 后半段中最高位上取1的情况分为两种：若n最高位数字>1，则最高位出现1的次数为x次；若n最高位数字=1，这最高位出现1的次数为i+1次。（例如后半段为1346-21345，则最高位万位上1出现的次数为10000次；若后半段为1346-11345，则最高位万位上1出现的次数为1346次）。
3. 后半段中其他数位上出现1的情况：将后半段等分为m份，每份数字数目为x（例如后半段为1346-21345，则将其分为1346-11345、11346-21345，每份数字数目为10000个）。除去最高位后，剩下的数字有y位。在任一一位上置1，其余y-1位上可以任取0-9，则根据排列组合，后半段其余数位总共出现1的次数为.（后半段分为01346-11345与11346-21345，去掉万位后，剩余数字有4位，根据公式，后半段数位总共出现1的次数为）
4.计算后半段，递归处理前半段。
方法2：归纳（按位考虑）。
所有数字出现1的个数 = 每一位数位上出现1的个数之和
从低到高遍历数字的每一数位loc，对于每一位loc，其当前位数字为now（1位），高位数字high（多位，若不存在则为0），低位数字low（多位，不存在则为0）。对于每一位loc上可能取1的情况：
1. now==0（次数=high*loc）
例如21045，对于百位来说，loc=100，high=21，1出现的情况有00100-00199（100次）、01100-01199（100次）……19100-19199（100次）、20100-20199（100次），一共2100次。
2. now==1（次数=high*loc + (low+1)）
例如21145，low=145，对于百位来说，除去上述的2100次，还有21100-21145，一共145+1=146次。总计2246次
3. now>=2（次数=(high+1)*loc）
例如21545，对于百位来说，除去上述的2100次，还有21100-21199，一共100次。总计2200次。
方法二还可以更一般地归纳为一条公式，具体见代码具体实现。
两种方法可拓展到整数中数字x出现的次数求解
题目描述
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
Java实现（按位考虑）：
/**
*
* @author ChopinXBP
* 求从1到n中1在数位上出现的次数
*
*/
public class NumberOf1Between1AndN_30 {
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(NumberOf1Between1AndN_Solution1(12023));
System.out.println(NumberOf1Between1AndN_Solution2(12023));
System.out.println(NumberOf1Between1AndN_Solution3(12023));
}
//归纳：按位考虑
public static int NumberOf1Between1AndN_Solution1(int n) {
if(n <= 0) return 0;
int result = 0;
int loc = 1; //当前位数
int high = 0; //高位数字（多位）
int now = 0; //当前位数字（1位）
int low = 0; //低位数字（多位）
while(n / loc > 0){
high = n / (loc * 10);
now = n / loc % 10;
low = n % loc;
if(now == 0){
result += high * loc;
}
else if(now == 1){
result += high * loc + low + 1;
}
else if(now >= 1){
result += (high + 1) * loc;
}
loc *= 10;
}
return result;
}
//简洁写法1，在C++下可归纳为一条公式
//当前位now=0/1时，+8对高位high无影响；当前位now>=2时，+8会产生进位，效果等同于high+1
public static int NumberOf1Between1AndN_Solution2(int n) {
int result = 0;
for (long loc = 1; loc <= n; loc *= 10) {
if(n / loc % 10 == 1){
result += (n / loc + 8) / 10 * loc + (n % loc + 1);
}else{
result += (n / loc + 8) / 10 * loc;
}
}
return result;
}
//简洁写法2，归纳为一条公式
//判断去掉高位后的余数，对于后半式子，若当前位小于1，输出0；若当前位等于1，输出low低位数字+1；若当前位大于1,输出一个loc当前位，等效于(high+1)*loc
public static int NumberOf1Between1AndN_Solution3(int n) {
if (n <= 0)
return 0;
int result = 0;
for (long loc = 1; loc <= n; loc *= 10) {
long high = n / (loc * 10); //高位数字
long rest = n % (loc * 10); //去掉高位数字后的余数
result += high * loc + Math.min(Math.max(rest - loc + 1, 0), loc);
}
return result;
}
}
C++实现（分段思想）：
int NumberOf1(const char* strN);
int PowerBase10(unsigned int n);
int NumberOf1Between1AndN_Solution2(int n)
{
if(n <= 0)
return 0;
char strN[50];
sprintf(strN, "%d", n);
return NumberOf1(strN);
}
int NumberOf1(const char* strN)
{
if(!strN || *strN < '0' || *strN > '9' || *strN == '\0')
return 0;
int first = *strN - '0';
unsigned int length = static_cast<unsigned int>(strlen(strN));
if(length == 1 && first == 0)
return 0;
if(length == 1 && first > 0)
return 1;
// 假设strN是"21345"
// numFirstDigit是数字10000-19999的第一个位中1的数目
int numFirstDigit = 0;
if(first > 1)
numFirstDigit = PowerBase10(length - 1);
else if(first == 1)
numFirstDigit = atoi(strN + 1) + 1;
// numOtherDigits是01346-21345除了第一位之外的数位中1的数目
int numOtherDigits = first * (length - 1) * PowerBase10(length - 2);
// numRecursive是1-1345中1的数目
int numRecursive = NumberOf1(strN + 1);
return numFirstDigit + numOtherDigits + numRecursive;
}
int PowerBase10(unsigned int n)
{
int result = 1;
for(unsigned int i = 0; i < n; ++ i)
result *= 10;
return result;
}C++实现（按位考虑）：
class Solution {
public:
int NumberOf1Between1AndN_Solution(int n){
int ones = 0;
for (long long m = 1; m <= n; m *= 10)
ones += (n/m + 8) / 10 * m + (n/m % 10 == 1) * (n%m + 1);
return ones;
}
};#Coding一小时，Copying一秒钟。留个言点个赞呗，谢谢你#