算法链表问题如何减少共同的中间复数

Question

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 ()。但是，正确答案是超时问题。有没有办法在使用链表时降低时间复杂度？

Answer 1

get() 在 LinkedList 上是一个 O(N) 操作，所以如果你正在寻找速度，应该避免它。您可以改为使用 ListIterator 将游标放入列表中，与使用索引相比，游标可以更有效地移动，并且也可以用于插入或删除元素。

您也可以只使用 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 reader 和编写器在完成后自动关闭它们，for-each 循环更有效地迭代打印时遍历整个列表，如果按照你阅读的每个字符的逻辑，使用 if/else。

算法链表问题如何减少共同的中间复数

Algorithm LinkedList Problems How to Reduce the Common Intermediate Complex

java

algorithm

linked-list

time-complexity