演算法LinkedList問題如何減少常見的中間復合體

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int testcase = Integer.parseInt(br.readLine());

        for(int i = 0; i < testcase; i  ) {
            String input = br.readLine();
            LinkedList<Character> list = new LinkedList<>();
            int idx = 0;

            for(int j = 0; j < input.length(); j  ) {
                if(input.charAt(j) != '<' && input.charAt(j) != '>' && input.charAt(j) != '-') {
                    list.add(idx, input.charAt(j));
                    idx  ;
                    continue;
                }
                if(input.charAt(j) == '<' && idx != 0) {
                    idx--;
                    continue;
                }
                if(input.charAt(j) == '>' && idx <= list.size() - 1) {
                    idx  ;
                    continue;
                }
                if(input.charAt(j) == '-' && idx != 0) {
                    list.remove(idx - 1);
                    idx--;
                }
            }

            for(int k = 0; k < list.size(); k  ) {
                bw.write(list.get(k));
            }
            bw.write('\n');
        }
        bw.flush();
        bw.close();
    }
}

• 輸入示例

  2
  <<BP<A>>Cd-
  ThIsIsS3Cr3t
  

• 輸出示例

  BAPC
  ThIsIsS3Cr3t
  

時間限制為 2 秒。

我使用 BufferedReader 代替 Scanner 來加快性能，并使用 BufferedWriter 代替 System.out.println()。但是，正確的答案是超時問題。有沒有辦法在使用鏈表時降低時間復雜度？

uj5u.com熱心網友回復：

get()on aLinkedList是一個 O(N) 操作，所以如果你正在尋找速度，應該避免它。您可以改為使用 aListIterator將游標放入串列中，與使用索引相比，它可以更有效地移動，也可以用于插入或洗掉元素。

您也可以只使用input.charAt()一次并將結果保存在char變數中，而不是在同一索引的回圈中多次呼叫它。這是一個快速的函式呼叫，但為什么要呼叫它而不是你真正需要的，尤其是在時鐘下作業時？

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.ListIterator;

public class Main {
    public static void main(String[] args) throws IOException{
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            int testcase = Integer.parseInt(br.readLine());

            for(int i = 0; i < testcase; i  ) {
                String input = br.readLine();
                LinkedList<Character> list = new LinkedList<>();
                ListIterator<Character> cursor = list.listIterator();

                for(int j = 0; j < input.length(); j  ) {
                    // I wish Strings were Iterable
                    char c = input.charAt(j);
                    if (c != '<' && c != '>' && c != '-') {
                        cursor.add(c);
                    } else if (c == '<' && cursor.hasPrevious()) {
                        cursor.previous();
                    } else if (c == '>' && cursor.hasNext()) {
                        cursor.next();
                    } else if (c == '-' && cursor.hasPrevious()) {
                        cursor.previous();
                        cursor.remove();
                    }
                }

                for (char c : list) {
                    bw.write(c);
                }
                bw.write('\n');
            }
        }
    }
}

還要注意閱讀器和撰寫器的try-with-resources在完成后自動關閉它們，for-each 回圈可以在列印時更有效地迭代整個串列，并在處理邏輯中使用 if/else if你讀到的每個字符。

標籤：

上一篇：為什么QuackSort比Data.List的隨機串列排序快2倍？

下一篇：無需6個for回圈即可端到端連接6個部分的最有效方法