那些年，面试中常见的数据结构基础和算法题（下） (16)

十位数上出现1的次数类似，如果N的十位数字等于1，则十位数上出现1的次数为各位数字加1；如果N的十位数字大于1，则十位数上出现1的次数为10。

当 N 为 3 位数时，同样分析可得1的个数。如 N=123，可得 1出现次数 = 13+20+24 = 57。

当 N 为 4,5...K 位数时，我们假设 N=abcde，则要计算百位上出现1的数目，则它受到三个因素影响：百位上的数字，百位以下的数字，百位以上的数字。

如果百位上数字为0，则百位上出现1的次数为更高位数字决定。如 N=12013，则百位出现1的数字有100~199， 1000~1199， 2100~2199...11100~111999 共 1200 个，等于百位的更高位数字(12)*当前位数(100)。

如果百位上数字为1，则百位上出现1的次数不仅受更高位影响，还受低位影响。如12113，则百位出现1的情况共有 1200+114=1314 个，也就是高位影响的 12 * 100 + 低位影响的 113+1 = 114 个。

如果百位上数字为其他数字，则百位上出现1的次数仅由更高位决定。如 12213，则百位出现1的情况为 (12+1)*100=1300。

有以上分析思路，写出下面的代码。其中 low 表示低位数字，curr 表示当前考虑位的数字，high 表示高位数字。一个简单的分析，考虑数字 123，则首先考虑个位，则 curr 为 3，低位为 0，高位为 12；然后考虑十位，此时 curr 为 2，低位为 3，高位为 1。其他的数字可以以此类推，实现代码如下：

/** * 1-N正整数中1的个数 */ int numOfOne(int n) { int factor = 1, cnt = 0; //factor为乘数因子 int low = 0, curr = 0, high = 0; while (n / factor != 0) { low = n - n/factor * factor; //low为低位数字，curr为当前考虑位的数字，high为高位数字 curr = n/factor % 10; high = n/(factor * 10); switch(curr) { <span>case</span> 0: //当前位为0的情况 cnt += high * factor; <span>break</span>; <span>case</span> 1: //当前位为1的情况 cnt += high * factor + low + 1; <span>break</span>; default: //当前位为其他数字的情况 cnt += (high+1) * factor; <span>break</span>; } factor *= 10; } <span>return</span> cnt;

}
复制代码

4.和为N的正整数序列

题： 输入一个正整数数N，输出所有和为N连续正整数序列。例如输入 15，由于 1+2+3+4+5=4+5+6=7+8=15，所以输出 3 个连续序列 1-5、4-6和7-8。

解1：运用数学规律

假定有 k 个连续的正整数和为 N，其中连续序列的第一个数为 x，则有 x+(x+1)+(x+2)+...+(x+k-1) = N。从而可以求得 x = (N - k*(k-1)/2) / k。当 x<=0 时，则说明已经没有正整数序列的和为 N 了，此时循环退出。初始化 k=2，表示2个连续的正整数和为 N，则可以求出 x 的值，并判断从 x 开始是否存在2个连续正整数和为 N，若不存在则 k++，继续循环。

/** * 查找和为N的连续序列 */ int findContinuousSequence(int n) { int found = 0; int k = 2, x, m, i; // k为连续序列的数字的数目，x为起始的值，m用于判断是否有满足条件的值。 while (1) { x = (n - k*(k-1)/2) / k; // 求出k个连续正整数和为n的起始值x m = (n - k*(k-1)/2) % k; // m用于判断是否有满足条件的连续正整数值 <span>if</span> (x &lt;= 0) <span>break</span>; // 退出条件，如果x&lt;=0，则循环退出。 <span>if</span> (!m) { // m为0，表示找到了连续子序列和为n。 found = 1; <span>print</span>ContinuousSequence(x, k); } k++; } <span>return</span> found;

}

/**

打印连续子序列
*/
void printContinuousSequence(int x, int k)
{
int i;
for (i = 0; i < k; i++) {
printf("%d ", x++);
}
printf("\n");
}
复制代码

解2：序列结尾位置法

因为序列至少有两个数，可以先判定以数字2结束的连续序列和是否有等于 n 的，然后是以3结束的连续序列和是否有等于 n 的，...以此类推。此解法思路参考的何海涛先生的博文，代码如下：

/** * 查找和为N的连续序列-序列结尾位置法 */ int findContinuousSequenceEndIndex(int n) { if (n < 3) return 0; int found = 0; int begin = 1, end = 2; int mid = (1 + n) / 2; int sum = begin + end; <span>while</span> (begin &lt; mid) { <span>if</span> (sum &gt; n) { sum -= begin; begin++; } <span>else</span> { <span>if</span> (sum == n) { found = 1; <span>print</span>ContinuousSequence(begin, end-begin+1); } end++; sum += end; } } <span>return</span> found;

}
复制代码

扩展： 是不是所有的正整数都能分解为连续正整数序列呢？