-1

我正在嘗試解決UVa problem 458 - decoder，並提出了以下算法，它爲我提供了正確的輸出樣本輸入數據，但運行時間超出了允許的範圍。UVa在線裁判＃458超出時間限制

public class Decoder { 

    public void decoder() { 
     Scanner sc = new Scanner(System.in); 

     while (sc.hasNext()) { 

      String line = sc.nextLine(); 

      for (int i = 0; i < line.length(); i++) { 

       if(line.charAt(i)>=32 && line.charAt(i)<=126) 
       System.out.print((char) (line.charAt(i) - 7)); 

      } 
      System.out.println(); 
     } 
    } 

}

我已經看了什麼爲

嗯，我已經閱讀了forums和大多數解決方案都非常相似，如果有避免爲一種方法，我一直在研究循環正在貫穿字符串並打印出新字符。但是這個循環是不可避免的，這個算法的時間複雜度總是會是n^2。

該問題還提到只更改ASCII可打印值，這就是爲什麼我設置條件來檢查它是否大於或等於32和126.根據Wikipedia這是可打印值的範圍。

http://ideone.com/XkByW9

來源

2014-06-27 Eduardo Dennis

也許處理整行，然後纔打印它將比單獨解碼和打印每個字符更快。 – Artyom

你確定你正在生成正確的輸出 - 這就是你的程序失敗的原因，對吧？我要問的原因是，您不僅限制將更改值更改爲ASCII可打印字符，而且還會將*打印*限制爲ASCII可打印字符，減去7.應該先減去，然後打印，如果結果在正確範圍內？ – Patrick87

@ Patrick87它超過了時間限制的答案是正確的 –

避免流的字符進行解碼。如果您只需要支持ASCII，則可以使用字節。
以大塊讀取和寫入數據以避免函數/系統調用開銷。
避免不必要的分配。目前，您正在爲每一行分配新的字符串。
不要將輸入拆分成行，以避免對於非常小的行造成不良的性能。

例子：

public static void main(String[] args) throws IOException { 
    byte[] buffer = new byte[2048]; 
    while (true) { 
     int len = System.in.read(buffer); 
     if (len <= 0) { 
      break; 
     } 
     for (int i = 0; i < len; i++) { 
      ... 
     } 
     System.out.write(buffer, 0, len); 
    } 
}

將處理輸入，你通常會處理的二進制文件。對於每一次迭代，它都會將最多2048個字節讀入緩衝區，處理它們並將它們寫入標準輸出。程序將在達到EOF時結束，並且read返回-1。 2048通常是一個很好的緩衝區大小，但您可能想嘗試不同的大小，並查看哪一個效果最好。

來源

2014-06-27 15:30:26

嘿，代碼真的很有趣，但我不確定它到底在做什麼。所以你基本上把一個字節數組設置爲（你選擇2048有max還是？），然後你用緩衝區大小讀入系統？我玩它，它運作得很好，但我不知道如何？ –

'Scanner'使用4096字節的緩衝區，在大多數情況下效率更高... –

@LuiggiMendoza如何添加新行？ –

長時間輸入時不要使用Scanner。掃描儀比其他讀取Java輸入的手段（例如BufferedReader）慢得令人難以置信。這個UVa問題看起來像是一個很長的輸入。

來源

2014-06-27 15:44:27 Marwin

UVa在線裁判＃458超出時間限制

我已經看了什麼爲

回答

相關問題