算法：数字与位数问题-白红宇

算法：数字与位数问题

阅读量：4060 次

发布时间：2019-05-25

本文共 2348 字，大约阅读时间需要 7 分钟。

问题A：

1～N整数中，包含位数1的个数。

dp算法，时间O(log10(N))

假设数字N各个位置上的数组成Arr[n]，

dp[i] 表示位置i上的1可以出现的次数。

当Arr[i] > 1 时，i 位置上1出现的次数只与Arr[i]前面的数字有关。
例如，N=21045中数字4所在位置1出现次数。
从 00010 到 21019 都是可行的数字，一共2110次，
可以发现 2110 = (210 + 1)*10
其中，210是数字4前数字的代数和，10是数字4所在的位数等级。

当Arr[i] == 0时，i 位置上1出现的次数只与Arr[i]前面的数字有关。
例如，N=21045中数字0所在位置1出现次数。
从 00100 到 20199 都是可行的数字，一共2100次，
可以发现 2100 = (21 + 0)*100
其中，21 是数字0前数字的代数和， 100是数字0所在的位数等级。

当Arr[i] == 1时，i位置上1出现的次数和Arr[i]前后数字都有关系。
例如，N = 21045 中数字 1 所在位置 1 出现次数。
从 01000 到 21045 都是可行的数字，一共2045次，
可以发现，2045 = (2 + 0)*1000 + 45
其中，2 是数字 1 前数字的代数和， 1000是数字1所在的位数等级，45 是数字1后数字的代数和。

可以加三个辅助数组加速计算：

sumFront记录位数i之前数字的代数和。

sumBack记录位数i之后位数的代数和。

Base记录位数i的等级。

对于例子N=21045

N	2	1	0	4	5
Base	10000	1000	100	10	1
sumFront	0	2	21	210	2104
sumBack	1045	45	45	5	0

代码如下：

问题B：

数字从0开始首尾相接拼成长字符串，求第n位置上的数字是几？

例如0123456789101112…中第13位数字是1

模拟做法，时间O(log10(N))

当前位数个数k个，k=1

步骤：

1，计算k位数字拼接后的长度L，判断n是否在内，不在n减去长度L，并k++。

2，当n在k位数拼接之内，则n位置一定是100…0到99…9之间某一位数，n/k大致定位n位置所在的数字，通过n%k进一步判断位置。

问题C：

数组中有n个数，把n个数首尾拼接后获得最小的数。

贪心做法，时间O(NlogN)

例如，3，32，321，拼接最小数321323

预处理，把所有数字变一样长，333，322，321，其中，后面缺的数用最后一位补齐，然后排序，将所有数首尾拼接。

问题D：

一个数二进制表示中1的个数

直接位运算，
正数，减1，&本身，计数一次，直到为0
负数，看如何处理补码，是否需要换成正数计算。

超自然算法之平行算法：

public int fun1(int n){	n = ( n & 0x55555555 ) + ( ( n >> 1 ) & 0x55555555 );	n = ( n & 0x33333333 ) + ( ( n >> 1 ) & 0x33333333 );	n = ( n & 0x0f0f0f0f ) + ( ( n >> 1 ) & 0x0f0f0f0f );	n = ( n & 0x00ff00ff ) + ( ( n >> 1 ) & 0x00ff00ff );	n = ( n & 0x0000ffff ) + ( ( n >> 1 ) & 0x0000ffff );	return n;}