给定一个正整数n,请返回0到n(包括n)的数字中2出现了几次。
10
返回:1
class Count2 { public: int countNumberOf2s(int n) { if (n <= 1) return 0; long res = 0, m; for (m = 1;m <= n;m *= 10) { int tmp1 = n / m, tmp2 = n%m; res += (tmp1 + 7) / 10 * m + (tmp1 % 10 == 2)*(tmp2 + 1); } return res; } };很经典的题目,leetcode上有数一的个数,可以推广至求任意数字的个数。
import java.util.*; public class Count2 { public int countNumberOf2s(int n) { int count = 0; for (int i = 1; i <= n; i *= 10) { int a = n / i,b = n % i; //之所以补8,是因为当百位为0,则a/10==(a+8)/10, //当百位>=2,补8会产生进位位,效果等同于(a/10+1) count += (a + 7) / 10 * i + ((a % 10 == 2) ? b + 1 : 0); } return count; } }
import java.util.*; /* 我们假设dp[i]表示正整数i的时候出现2的次数 *///那里越界了,我想不明白 public class Count2 { public int countNumberOf2s(int n) { // write code here int[] dp = new int[n+1]; dp[0] = 0; for(int i = 1;i<=n;i++){ if(isContain2(i)) dp[i] = dp[i-1] + 1; else dp[i] = dp[i-1]; } return dp[n]; } public boolean isContain2(int n){ String str = String.valueOf(n); if(str.contains("2")) return true; return false; } }跪求大神知道,为啥说我越界了呢
class Count2 { public: int countNumberOf2s(int n) { int cnt=0, low=0, high=0, cur=0, w=1; while(n/w){ low = n - (n/w)*w; cur = (n/w)%10; high = n/(w*10); if(cur<=1) cnt += high*w; if(cur==2) cnt += high*w + low + 1; if(cur>2) cnt += (high+1)*w; w *= 10; } return cnt; } };
class Count2 { public: int countNumberOf2s(int n) { int hig, w, low,i=-1; //i等于-1是因为do...while的原因 int result = 0; do{ i++; int m=pow(10,i); hig = n/m; w = hig%10; hig/=10; if(i == 0) low=0; else low=n%m; if( w < 2) result+=hig*pow(10,i); else if( w== 2)result+=hig*pow(10,i)+low+1; else result+=(hig+1)*pow(10,i); }while(hig != 0); //这里用do...while是因为最高位也需要被计算,即使它的hig为0. return result; } };
//方法1 时间复杂度太大,不可取 /* public class Count2 { public static int countthisnum(int n){ int temp=0; while(n>0){ if(n%10==2) temp++; n/=10; } return temp; } public int countNumberOf2s(int n) { int count=0; for (int i = 0; i <= n; i++) { count+=countthisnum(i); } return count; } } */ //方法二 // >2 (高位+1)*iFactor // =2 (高位)*iFactor+低位+1 // <2 高位*iFactor public class Count2 { public int countNumberOf2s(int n) { int iCount=0; int iFactor=1; int iLowerNum=0; int iCurrNum=0; int iHigherNum=0; while(n/iFactor!=0){ iLowerNum=n-(n/iFactor)*iFactor; iCurrNum=(n/iFactor)%10; iHigherNum=n/(iFactor*10); switch(iCurrNum){ case 0: iCount+=iHigherNum*iFactor; break; case 1: iCount+=iHigherNum*iFactor; break; case 2: iCount+=iHigherNum*iFactor+iLowerNum+1; break; default: iCount+=(iHigherNum+1)*iFactor; break; } iFactor*=10; } return iCount; } }
//通过遍历数字n的每一位,按照当前位跟2的关系判断该位置出现2的次数,累计即可 class Count2 { public: int countNumberOf2s(int n) { int count = 0; int low,high,cur; for(int m=1;m<=n;m*=10) { high = (n/m)/10; low = n % m; cur = (n/m)%10; if(cur < 2) { count += high * m; }else if(cur > 2) { count += (high+1)*m; }else if(cur == 2) { count += high*m + low + 1; } } return count; } };
class Count2 { public: int countNumberOf2s(int n) { vector<int> dp(10,0); dp[1] = 1; int res = 0; for (int i = 2; i <= 9; ++i) dp[i] = 10 * dp[i - 1] + (int)pow(10, i - 1); int i = 1; int sz = to_string(n).size(); while (n > 0) { int times = (int)pow(10, sz - 1); int end = n / times; res += end * dp[sz - 1]; n %= times; if (end > 2) res += times; else if (end == 2) res += n + 1; --sz; } return res; } };
import java.util.*; public class Count2 { public int countNumberOf2s(int n) { // write code here int count=0,i; if(n<2) return 0; else if(n<=10) return 1; else for(int j=2;j<=n;j++){ i=j; while(i>0){ if(i%10==2) count++; i/=10; if(i==0) break; } } return count; } } //最直接的做法,但超时,OMG
class Count2 { public: int countNumberOf2s(int n) { // write code here int cnt = 0, k; for (int i = 1;k = n / i;i *= 10) { // k / 10 为高位的数字。 cnt += (k / 10) * i; // 当前位的数字。 int cur = k % 10; if (cur > 2) { cnt += i; } else if (cur == 2) { // n - k * i 为低位的数字。 cnt += n - k * i + 1; } } return cnt; } };
如果要找包含5的个数,有三种情况:
一、每一位都小于5,如: n = 22222
(1)个位上:
每10个一组,即:1~10, 11~20, ..., 100~110, 111~120, ..., 22211~22220,共2222组,每组个位上是5的只有一个,所以共出现了2222 * 1次
剩下的数字22221、22222中个位数上不包含5,所以个位为5的为0个。
因此:总数为2222 + 0 = 2222。
(2)十位上:
每100个一组,即:1~100, 101~200, ..., 1001~1100, 1101~1200, ..., 22101~22200,共222组,每组数字中十位上是5的有10个,所以共出现了222 * 10 = 2220次
剩余22201 ~ 22222,十位数上不包含5。
因此:总数为2220 + 0 = 2220
二、每一位都等于5,如: n = 55555
(1)个位上:
每10个一组,即:1~10, 11~20, ..., 100~110, 111~120, ..., 55541~55550,共5555组,每组个位上是5的只有一个,所以共出现了5555 * 1次
剩下的数字55551 ~ 55555中个位数上包含5的为55555,所以是1个。
因此:总数为5555 + 1 = 5556。
(2)十位上:
每100个一组,即:1~100, 101~200, ..., 1001~1100, 1101~1200, ..., 55401~55500,共555组,每组数字中十位上是5的有10个,所以共出现了555 * 10 = 5550次
剩余55501 ~ 55555,十位数上包含5的为55550 ~ 55555,共6个。
因此:总数为5550 + 6 = 5556
三、每一位都大于5,如: n = 88888
(1)个位上:
每10个一组,即:1~10, 11~20, ..., 100~110, 111~120, ..., 88871~88880,共8888组,每组个位上是5的只有一个,所以共出现了8888 * 1次
剩下的数字88881 ~ 88888中个位数上包含1个5。
因此:总数为8888 + 1 = 8889。
(2)十位上:
每100个一组,即:1~100, 101~200, ..., 1001~1100, 1101~1200, ..., 88701~88800,共888组,每组数字中十位上是5的有10个,所以共出现了888 * 10 = 8880次
剩余88801 ~ 88888,十位数上包含5的为88851 ~ 88859,共10个。
因此:总数为8880 + 10 = 88890
所以,当要找到数字为D时,按照每一位进行计算,并且每位包含2部分组成,分组中的个数,和剩余的个数。
对于每一位K:
1、分组中:
D的个数 = 分组数 * 每组个数 = 总数 / (10 ^ 位数) * (10 ^ 位数)
2、剩余:
K < D时,剩余为0
K > D时,为1 * (10 ^ 位数)
K = D时,为 总数 % (10 ^ 位数)+ 1
程序如下(Rust):
fn calculate_count(maxn: u32, digit: u32) -> u32 {
let mut base_num: u32 = 1;
let mut total: u32 = 0;
while maxn > base_num {
let group_count = maxn / 10 / base_num * base_num;
let mut remained_count: u32 = 0;
let bit_num: u32 = maxn % (base_num * 10) / base_num;
if bit_num > digit {
remained_count = 1 * base_num;
} else if bit_num == digit {
remained_count = maxn % base_num + 1;
}
total += group_count + remained_count;
base_num *= 10;
println!("{}: {} {}", base_num, group_count, remained_count);
}
return total;
}
class Count2 { public: /* 依次计算个位、十位、百位、...、最高位出现2的数的次数 将n分为三段 higher now_bit lower if(now_bit>2) { 出现2的情况有 [0,higher] 2 [9,...,9] 9的个数时lower的长度 (higher+1)*(10^lower_bits) }则n等价于 if(now_bit==2){ 出现2的情况有 higher 2 [0,lower] lower+1 [0,higher-1] 2 [0,9....9] = higher*(10^lower_bits) } if(now_bit<2){ [0,higher-1] 2 [0,9....9] = higher*(10^lower_bits) } 从个位开始依次统计即可 */ int countNumberOf2s(int n) { // write code here if(n<2) return 0; int ans = 0; //求每一位固定为2时的情况数目 //将n分为 当前位,高位部分,低位部分 int higher=n/10,now_bit = n%10,lower=0; int t = 1;//pow计算是浮点型,有误差,pow(10,i); while(higher>0&nbs***bsp;now_bit>0){ if(now_bit==2){ ans+=lower+1;//higher 2 lower 的2数目,higher不变,lower从0变为lower } //当前位>2时,等价于higher now_bit 99..99, lower从0-99.999 if(now_bit>2){ ans+=t; } ans+=t*higher; // higher从0变为higher-1 low_bit为2 lower从0-99.999 lower+=now_bit*t; now_bit = higher%10; higher/=10; t*=10; } return ans; } };
package com.qy.bz.bb; import java.util.Scanner; public class Count2 { public static void main(String args[]) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); Count2 count2=new Count2(); System.out.println(count2.countNumberOf2s(n)); sc.close(); } public int countNumberOf2s(int n) { int count=0; for(int i=1;i<=n;i++) { String temp = String.valueOf(i); char ch[] = temp.toCharArray(); for (int j=0;j<ch.length;j++) { if(ch[j]=='2') { count++; } } } return count; } } 我这样写也提示超时。
class Count2 { public: int countNumberOf2s(int n) { // write code here int count = 0; for (int i = 1; n >= i; i = i * 10) { //count += n / (10 * i) * i; count += n / (10 * i) * i; int k = n % (10 * i); if (k >= 3 * i - 1) { count += i; } else if (k <= 2 * i - 1) { count += 0; } else { count += k - 2 * i + 1; } } return count; } };
运行时间:3ms
占用内存:476k
class Count2 { public: //3ms 492k 之前剑指offer有道数1个数的,改两个数字即可,可以去那看哈我的回答,有详细思路 int countNumberOf2s(int n) { // write code here if(n<=0)return 0; int round=n,weight,base=1; int count=0; while(round){ weight=round%10; round/=10; count+=round*base; if(weight==2) count+=(n%base)+1; if(weight>2) count+=base; base*=10; } return count; } };
class Count2 {
public:
int countNumberOf2s(int n) {
// write code here
if(n<2)
return 0;
if(n<=10)
return 1;
int cnt=1;
while(n/(cnt*10)>0)
cnt*=10;
int out=0;
int bf=0;
while (cnt)
{
int cur = n / cnt;
int tp = bf*cnt;
if (cur > 2)
tp += cnt;
else if (cur == 2)
tp += n%cnt+1;
out += tp;
bf = bf * 10 + cur;
n %= cnt;
cnt /= 10;
}
return out;
}
};