java - UVa 11616 Roman Numerals Time Limit Exceeded - 我一直收到 Time Limit Exceeded

Question

我正在为通用编程实践解决一个关于 UVa 的问题，因为我想在有竞争力的编程方面做得更好。但是我遇到了这个问题 - 罗马数字。在这个问题中，目标是接受罗马数字或阿拉伯数字形式的输入，然后我必须从一个转换为另一个。根据网上的判断，我觉得我的代码处理速度应该没有问题，它处理速度不够快。我需要帮助找出如何优化我的代码，以便它运行得更快并且不接收 TLE。

以下是我的程序，任何帮助解释我为什么收到超出时间限制的任何帮助将不胜感激。提前致谢。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


class Main {
    private static String order = "IVXLCDM";
    private static String order2 = "IXCM";  // These chars are the result of 10^n (n depending on index in the string)
    private static String order3 = "VLD";   // These chars are products of 5*10^n (n depending on index in the string)

    public static void main(String[] args) {
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);
        String ans = "";
        while (true) {
            String read = "";
            int aNum = 0;
            String rNum = "";
            try {
                read = br.readLine();
                if (read=="") 
                    break;
            } catch (IOException e) {
                if (read=="")
                    break;
                e.printStackTrace();
            }
            try {
                aNum = Integer.parseInt(read);
//                  System.out.println(aNum);

                int thousands = aNum/1000;
//                  System.out.println(thousands);

                int hundreds = aNum/100;
                hundreds = hundreds%10;
//                  System.out.println(hundreds);

                int tens = aNum%100;
                tens = tens/10;
//                  System.out.println(tens);

                int ones = aNum%10;
//                  System.out.println(ones);           

                rNum+= a2R(thousands,"M");
                rNum+= a2R(hundreds,"C");
                rNum+= a2R(tens,"X");
                rNum+= a2R(ones,"I");

//              System.out.println(rNum);
                ans+=(rNum+"\n");
//              System.out.print(ans);

            } catch (NumberFormatException c) {
                rNum = read;
                if (rNum.equals(""))
                    break;
                aNum = r2A(rNum);
//              System.out.println(aNum);
                ans+=(aNum+"\n");
//              System.out.print(ans);
            }
        }
        System.out.print(ans);


    }

    private static int r2A(String rNum) {
        int aNum = 0;
        for (int i = order.length()-1; i >= 0; i--) {
            char curChar = order.charAt(i);
            while (rNum.indexOf(curChar)!=-1) {
                if (rNum.indexOf(curChar)==0) {
                    if (order2.indexOf(curChar)!=-1) {
                        aNum+=((int)Math.pow(10, order2.indexOf(curChar)));
                    }
                    else if (order3.indexOf(curChar)!=-1) {
                        aNum+=(5*((int)Math.pow(10, order3.indexOf(curChar))));
                    }
                    rNum = rNum.substring(1);
                }
                else if (rNum.indexOf(curChar)==1) {
                    if (order2.indexOf(curChar)!=-1) {
                        aNum+=((int)(Math.pow(10, order2.indexOf(curChar))-Math.pow(10, order2.indexOf(curChar)-1)));
                    }
                    else if (order3.indexOf(curChar)!=-1) {
                        aNum+=((int)((5*Math.pow(10, order3.indexOf(curChar)))-Math.pow(10,order3.indexOf(curChar))));
                    }
                    rNum = rNum.substring(2);
                }
            }
        }
        return aNum;
    }

    private static String a2R(int num, String theNum) {
        // num is the digit of an Arabic digit number to be replaced by Roman Numerals for that digit
        // theNum is the value of Roman Numerals that would go into the specific digit place (tens, ones,...)
        String rNum = "";
        if (!theNum.equals("M")) {
            if (num==9) {
                rNum = theNum + order.charAt(order.indexOf(theNum)+2);
            }
            else if (num==4) {
                rNum = theNum + order.charAt(order.indexOf(theNum)+1);
            }
            else if (num>=5) {
                rNum+= order.charAt(order.indexOf(theNum)+1);
                for (int i = 0; i < num-5; i++) {
                    rNum+=theNum;
                }
            }
            else {
                for (int i = 0; i < num; i++) {
                    rNum+=theNum;
                }
            }
        }
        else {
            for (int i = 0; i < num; i++) {
                rNum+=theNum;
            }
        }
        return rNum;
    }

}

`

score 1 · Accepted Answer

我预计 TLE 是由您的程序永不终止引起的。

目前你有一个while (true)循环，break当你看到一个空行时。
但是根据问题...

The input consists of several lines, each one containing 
either an Arabic or a Roman number n, where 0 < n < 4000.

它没有说明会有一个额外的空白行终止输入。
所以你的程序不会终止，永远等到输入一个额外的空白行。

而不是像这样阅读您的输入

    while (true) {
        String read = "";
        int aNum = 0;
        String rNum = "";
        try {
            read = br.readLine();
            if (read=="") 
                break;
        } catch (IOException e) {
            if (read=="")
                break;
            e.printStackTrace();
        }
        //etc

试试这个

    String read = "";
    while ((read = br.readLine()) != null) {
        int aNum = 0;
        String rNum = "";
        //etc

score 0 · Accepted Answer

我以不同的方式解决了我的问题，我使用了几个 HashMap 将罗马数字值映射到阿拉伯数字值，反之亦然。我有四种辅助方法：一种是设置哈希图，另一种是从罗马数字转换为阿拉伯数字，另外两种将一起从阿拉伯数字转换为罗马数字。

从罗马转换为阿拉伯语的方法将在 for 循环中从字符串的开头开始遍历字符串。它会检查字符串的长度是否大于 1，如果是，它会检查前两个值的子字符串是否在罗马到阿拉伯语的 hashmap 中。如果是这样，它会将罗马数字值等于的值添加到 int 变量。该方法还将检查长度为 1 的子字符串。

在从阿拉伯语转换为罗马语的方法中，输入的整数首先会被分析，然后会被撕成小块。在第一种方法中，首先会产生四个整数值：千位值、百位值、十位值，然后是个位值。第二种方法将这些值组织成正确的罗马数字形式。

感谢所有帮助我解决这个问题的人，我没有意识到我犯的一些错误，可能是因为我没有编程经验，所以这对我自己来说是一次很棒的学习经历。

以下是我的解决方案：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;


class Main {
private static HashMap<String,Integer> r2A = new HashMap<String,Integer>();
private static HashMap<Integer,String> a2R = new HashMap<Integer,String>();

public static void main(String[] args) throws IOException {
    InputStreamReader isr = new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(isr);
    makeMaps();
    String read;
    StringBuilder answers = new StringBuilder("");
    while ((read=br.readLine())!=null) {
        int aNum = 0;
        String rNum = "";
        try {
            aNum = Integer.parseInt(read);
            System.out.println(arab2Roman(aNum));
        } catch (NumberFormatException c) {

            rNum = read;

            int ans = roman2Arab(rNum);
            System.out.println(ans);

        }
    }
}

private static int roman2Arab(String rNum) {
    int aNum = 0;
    for (int i = 0; i < rNum.length(); i++) {
        boolean done = false;
        String theNum = rNum.substring(i,i+1);
        if (i < rNum.length()-1) {
            String part = rNum.substring(i, i+2);
            if (r2A.containsKey(part)) {
                aNum+=r2A.get(part);
                i++;
                done = true;
            }
        }
        if (!done) {
            if (r2A.containsKey(theNum)) {
                aNum+=r2A.get(theNum);
            }
        }

    }
    return aNum;
}

private static String arab2Roman(int num) {
    StringBuilder rNum = new StringBuilder("");
    int thousands = num-(num%1000);

    int hundreds = ((num/100)%10)*100;

    int tens = ((num/10)%10)*10;

    int ones = num%10;

    rNum.append(simpleConv(thousands,"thousands"));
    rNum.append(simpleConv(hundreds,"hundreds"));
    rNum.append(simpleConv(tens,"tens"));
    rNum.append(simpleConv(ones,"ones"));

    return rNum.toString();
}

private static String simpleConv(int num, String place) {
    StringBuilder ans = new StringBuilder("");
    int pNum = (place.equals("thousands")) ? 1000 : (place.equals("hundreds")) ? 100 : (place.equals("tens")) ? 10 : 1;
    if (a2R.containsKey(num)) {
        ans.append(a2R.get(num));
    }
    else {
        if (num/pNum>=5) {
            ans.append(a2R.get(5*pNum));
            for (int i = 0; i < ((num/pNum)-5); i++) {
                ans.append(a2R.get(pNum));
            }
        }
        else {
            for (int i = 0; i < num/pNum; i++) {
                ans.append(a2R.get(pNum));
            }
        }
    }
    return ans.toString();
}

private static void makeMaps() {
    // First r2A
    r2A.put("I", 1);
    r2A.put("IV", 4);
    r2A.put("V", 5);
    r2A.put("IX", 9);
    r2A.put("X", 10);
    r2A.put("XL", 40);
    r2A.put("L", 50);
    r2A.put("XC", 90);
    r2A.put("C", 100);
    r2A.put("CD", 400);
    r2A.put("D", 500);
    r2A.put("CM", 900);
    r2A.put("M", 1000);

    // Second a2R
    a2R.put(1, "I");
    a2R.put(4, "IV");
    a2R.put(5, "V");
    a2R.put(9, "IX");
    a2R.put(10, "X");
    a2R.put(40, "XL");
    a2R.put(50, "L");
    a2R.put(90, "XC");
    a2R.put(100, "C");
    a2R.put(400, "CD");
    a2R.put(500, "D");
    a2R.put(900, "CM");
    a2R.put(1000, "M");

}
}

java - UVa 11616 Roman Numerals Time Limit Exceeded - 我一直收到 Time Limit Exceeded

2 回答 2

Related

Reference