时间戳

首页 > 解决方案 > Java 性能大

java - Java 性能大

问题描述

我必须找到第 100 位数字（不包括数字 3、4、7），但这需要很长时间，大约 9 秒才能找出如何提高性能。

import java.sql.Date;
import java.text.DecimalFormat;
import java.text.SimpleDateFormat;

public class FirstChallange {

    private static int removedNumbers;
    private static int numberQuantity;
    private static int lastNumberFound; 
    private static int cont;
    private static int pos3;
    private static int pos4;
    private static int pos7;    

    public static void main(String[] args) 
    { 

        long inicio = System.currentTimeMillis();  

        removedNumbers = 0;
        numberQuantity = 10000000;


        for (cont = 1; removedNumbers <= numberQuantity; cont++) {      
            String str = new String(); 
            str = String.valueOf(cont);     

            pos3 = str.indexOf("3");
            pos4 = str.indexOf("4");
            pos7 = str.indexOf("7");

            if((pos3 == -1) && (pos4 == -1) && (pos7 == -1)) {
                removedNumbers++; 
                if(removedNumbers == numberQuantity){ // can not find numbers (3, 4, 7)
                    lastNumberFound = cont; 
                }
            } 
        }       

        DecimalFormat dfmt = new DecimalFormat("0");

        System.out.println(dfmt.format(lastNumberFound)); 

        long fim  = System.currentTimeMillis();   
        System.out.println(new SimpleDateFormat("ss.SSS").format(new Date(fim - inicio)));  


    }
}

是否将数字转换为字符串并使用 indexOf 最佳模式删除它们？还是有什么比 indexOf 更好的东西，比如 RabinKarp？

预期结果：5/4 秒内 180999565

标签： javaalgorithmperformancenumbers

解决方案

你应该以不同的方式思考这个问题。

“生成numberQuantity以下不包含 3、4、7 的所有数字”

或者换句话说：“创建仅包含 0,1,2,5,6,8,9 作为数字的数字”。

这是 7 个不同的数字。

因此，一种方法可以是从 1 开始递增一个计数器并将其转换为一个以 7 为基数的表示，您可以在其中映射每个数字，如下所示：

0->0
1->1
2->2
3->5
4->6
5->8
6->9

推荐阅读