求解一算法题~~~要求考虑效率 有这样一个函数f(n),对于任意正整数n,它表示从 0 到 n 之间出现“1”的个数, 比如 f(1)=1, f(13)=6, 请列出从 1 到 1234567890 中所有的 f(n) = n的n,要求准确快速. 解决方案 » 免费领取超大流量手机卡,每月29元包185G流量+100分钟通话, 中国电信官方发货 f(n) 表示 0~n 中 数字带有1的数字个数 import java.util.regex.Matcher;import java.util.regex.Pattern; public class NumCount{ int num; int total=0; public NumCount(int num){ this.num=num; } public int getTotal(){ Pattern p=Pattern.compile("1"); if(num<=0) return 0; else{ for(int i=1;i<=num;i++){ Matcher match=p.matcher(String.valueOf(i)); while(match.find()){ total++; } } return total; } } public static void main (String[] args) { NumCount t=new NumCount(111); System.out.println ("1的个数:"+t.getTotal()); } } 这个是数字计算的import java.lang.Math;public class NumCount{ private int num; private int total=0; public NumCount(int num){ this.num=num; } public int getTotal(){ if(num<=0) return 0; else{ for(int i=1;i<=num;i++){ int tem=i; String str=String.valueOf(i); int len=str.length(); for(int j=len-1;j>=0;j--){ if((int)(tem/(int)Math.pow(10,j))==1) total++; if(j+1>1){ tem=tem%((int)Math.pow(10,(j==0)?1:j)); } } } return total; } } public static void main (String[] args) { NumCount n=new NumCount(21); System.out.println ("1的个数:"+n.getTotal()); } } 3,4楼两个算法速度都不行~n值可能很大 比如1234567890,for(int i=1;i <=n;i++)出现这句肯定不正确 相信很多人都能立刻得出以下的解法: for(n:N) { 判断n包含1的个数; 累加计数器; }这是最直接的解法,但遗憾的是,时间复杂程度为O(N*logN)。因为还需要循环判断当前的n的各位数,该判断的时间复杂程度为O(logN)。接下来就应该思考效率更高的解法了。说实话,这道题让我想起另外一道简单的算法题:N为正整数,计算从1到N的整数和。很多人都采用了循环求解。然后利用初等数学知识就知道S=N*(N+1)/2,所以用O(1)的时间就可以处理。再回到本道题目,同理应该去寻找到结果R与N之间的映射关系。分析如下:假设N表示为a[n]a[n-1]...a[1],其中a[i](1<=i<=n)表示N的各位数上的数字。c[i]表示从整数1到整数a[i]...a[1]中包含数字1的个数。x[i]表示从整数1到10^i - 1中包含数字1的个数,例如,x[1]表示从1到9的个数,结果为1;x[2]表示从1到99的个数,结果为20;当a[1]=0时,c[1] = 0;当a[1]=1时,c[1] = 1;当a[1]>1时,c[1] = 1; 当a[2]=1时,c[2] = a[1] +1+ c[1] + x[1];当a[2]>1时,c[2] = a[2]*x[1]+c[1]+10; 当a[3]=1时,c[3] = a[2]*a[1] +1+ c[2] + x[2];当a[3]>1时,c[3] = a[3]*x[2]+c[2]+10^2;...... 以此类推当a[i]=1时,c[i] = a[i-1]*...*a[1] +1+ c[i-1]+x[i-1];当a[i]>1时,c[i] = a[i]x[i-1]+c[i-1]+10^(i-1); 实现的代码如下:Java代码 public static int search(int _n) { int N = _n/10; int a1 = _n%10,a2; int x = 1; int ten = 10; int c = a1 == 0?0:1; while(N > 0) { a2 = N%10; if(a2 == 0); else if(a2 == 1)c = a1 + 1 + x + c; else c = a2*x + c + ten; a1 = 10*a1 + a2; N /=10; x = 10*x + ten; ten *= 10; } return c; } public static int search(int _n) { int N = _n/10; int a1 = _n%10,a2; int x = 1; int ten = 10; int c = a1 == 0?0:1; while(N > 0) { a2 = N%10; if(a2 == 0); else if(a2 == 1)c = a1 + 1 + x + c; else c = a2*x + c + ten; a1 = 10*a1 + a2; N /=10; x = 10*x + ten; ten *= 10; } return c; } 而以上解法的时间复杂程度只有O(logN) 这个好总结了下1234 中的十位的个数:十位3> 1 ;(12 + 1) * 10 百位的个数:百位2> 1; (1 + 1) * 100 个位的个数: 个位4>1; (123 + 1) *1 千位的个数: 千位1 ; 234 + 1等于 130 + 200 + 124 + 235 =....这样应该是最快的 JAVA的一个问题 为什么这个tabbedpane 不显示出来呀? 请问2个JAVA实例·!请各位帮帮·!谢谢·! 设计正则表达式 关于\r,四种IDE竟然得到不同结果? 新手向大家请教一下,这个java的源码是用什么工具打开啊? 问个关于JBuilder的问题(JBuilder 6) JTree的问题!快帮我一下(在线等待) 为什么我的HTMLConverter不能用,DOS一闪就没有了 一个字符串数组,怎样把它按照字母顺序排列。 求代码执行结果 字符串拆分,输出问题
import java.util.regex.Pattern;
public class NumCount{
int num;
int total=0;
public NumCount(int num){
this.num=num;
}
public int getTotal(){
Pattern p=Pattern.compile("1");
if(num<=0)
return 0;
else{
for(int i=1;i<=num;i++){
Matcher match=p.matcher(String.valueOf(i));
while(match.find()){
total++;
}
}
return total;
}
}
public static void main (String[] args) {
NumCount t=new NumCount(111);
System.out.println ("1的个数:"+t.getTotal());
}
}
import java.lang.Math;
public class NumCount{
private int num;
private int total=0;
public NumCount(int num){
this.num=num;
}
public int getTotal(){
if(num<=0)
return 0;
else{
for(int i=1;i<=num;i++){
int tem=i;
String str=String.valueOf(i);
int len=str.length();
for(int j=len-1;j>=0;j--){
if((int)(tem/(int)Math.pow(10,j))==1)
total++;
if(j+1>1){
tem=tem%((int)Math.pow(10,(j==0)?1:j));
}
}
}
return total;
}
}
public static void main (String[] args) {
NumCount n=new NumCount(21);
System.out.println ("1的个数:"+n.getTotal());
}
}
n值可能很大 比如1234567890,for(int i=1;i <=n;i++)出现这句肯定不正确
public static int search(int _n)
{
int N = _n/10;
int a1 = _n%10,a2;
int x = 1;
int ten = 10;
int c = a1 == 0?0:1;
while(N > 0)
{
a2 = N%10;
if(a2 == 0);
else if(a2 == 1)c = a1 + 1 + x + c;
else c = a2*x + c + ten;
a1 = 10*a1 + a2;
N /=10;
x = 10*x + ten;
ten *= 10;
}
return c;
} public static int search(int _n)
{
int N = _n/10;
int a1 = _n%10,a2;
int x = 1;
int ten = 10;
int c = a1 == 0?0:1;
while(N > 0)
{
a2 = N%10;
if(a2 == 0);
else if(a2 == 1)c = a1 + 1 + x + c;
else c = a2*x + c + ten;
a1 = 10*a1 + a2;
N /=10;
x = 10*x + ten;
ten *= 10;
}
return c;
} 而以上解法的时间复杂程度只有O(logN)
这个好
总结了下
1234 中的十位的个数:十位3> 1 ;(12 + 1) * 10
百位的个数:百位2> 1; (1 + 1) * 100
个位的个数: 个位4>1; (123 + 1) *1
千位的个数: 千位1 ; 234 + 1
等于 130 + 200 + 124 + 235 =....
这样应该是最快的