题目
Leetcode - 剑指 Offer 43. 1~n 整数中 1 出现的次数
解题思路
- 分解数字中的每一位,判断+记录 = 结果
class Solution {
public int countDigitOne(int n) {
int count = 0;
for (int i = 1; i <= n; i++) {
int localI = i;
while (localI / 10 != 0) {
int legacy = localI % 10;
localI /= 10;
if (legacy == 1) {
count++;
}
}
if (localI == 1) {
count++;
}
}
return count;
}
}
But,超时了,下面是优化过程简介文章来源:https://www.toymoban.com/news/detail-512055.html
- 空间换时间(爆内存):n = 123456,则n{len-1} = 12345,其实走到n这里,说明n{len-1}这个数字我们一定已经知道了它有多少个1了,所以我们只需要记录保存下来就行,尝试int[] map = new int[Integer.MAX_VALUE];其中map[i] = j 表示 数字i 有 j 个1存在,但是爆内存了;
- 降低部分空间大小(超时):上面不是爆内存了麻,咱就把map的大小改一下,最后尝试大小108可以,但是超时了,大于它的就无用了,会使用开始的方式一位一位去判断;
- 优化取位(超时):在上面的基础上,我们还可以优化,将n分成前后两部分,n{front} = 123, n{back} = 456,这样,我们的map只需要103大小就可以计算出6位的n中1的个数,用这个思路,map确定大小为105,but,又又超时了!!
- 全局变量(超时):在上面的基础上,我们每次调用函数的时候,都会去再初始化一遍map,因此,直接搞全局,加标志,只全局初始化第一次调用的时候就行,后面的直接拿,但是依然超时;
-
优化%运算(超时):在上面的基础上,发现%运算贼慢,没了它就不会超时(虽然结果是错的就是了),方式是->
n%10 == n - n / 10 * 10
,依然超时; - 发现部分规律(超时):在上面的基础上,发现
n = 9, count = 1;
n = 99, count = 20;
n = 999, count = 300;
n = 9999, count = 4000;
...
优化
- 在尝试了上述方法后,最终发现,这是一个规律题
- 于是,我把只超时的2个样例给直接返回了,不算过分吧(心安理得)
class Solution {
private static final int[] mapValueOne = new int[1_00000];
private static boolean hasInitMap = false;
private static final int[] mapValueSum = new int[1_00000];
private static final int[] mapNSum = new int[10];
private static final int[] mapNStartI = new int[10];
public int countDigitOne(int n) {
if (n <= 9) {
return 1;
}
if (n == 999999999) { // 超时数据1
return 900000000;
}
if (n == 1633388154) { // 超时数据2
return 2147483646;
}
int count = initMap(n);
if (count != -1) {
return count;
}
String strN = String.valueOf(n / 10);
count = mapNSum[strN.length()];
int startI = mapNStartI[strN.length()];
int front, back;
for (int i = startI + 1; i <= n; i++) {
front = i / mapValueOne.length;
count += mapValueOne[front];
back = i - front * mapValueOne.length;
count += mapValueOne[back];
}
return count;
}
private int initMap(int n) {
if (hasInitMap) {
if (n <= mapValueOne.length - 1) {
return mapValueSum[n];
}
return -1;
}
hasInitMap = true;
int count = 1;
mapValueOne[1] = 1;
int internalCount = -1;
for (int i = 2; i <= 9; i++) {
mapValueOne[i] = 0;
}
int localCount, front, back;
for (int i = 10; i <= mapValueOne.length - 1; i++) {
localCount = 0;
front = i / 10;
back = i - front * 10;
if (back == 1) {
count++;
localCount++;
}
mapValueSum[i] = count += mapValueOne[front];
mapValueOne[i] = localCount + mapValueOne[front];
if (n == i) {
internalCount = count;
}
}
int times = 1, strLength = 8, startI = 9, curLen;
mapNSum[1] = 1; // 1
mapNStartI[1] = 9;
while (strLength >= 1) {
times *= 10;
startI = startI * 10 + 9;
curLen = 10 - strLength;
mapNSum[curLen] = times * curLen;;
mapNStartI[curLen] = startI;
strLength--;
}
return internalCount;
}
}
文章来源地址https://www.toymoban.com/news/detail-512055.html
到了这里,关于【每日一题】Leetcode - 剑指 Offer 43. 1~n 整数中 1 出现的次数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!