算法链表问题如何减少常见的中间复杂度

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

LinkedList上的get()是一个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');
}
}
}
}

还请注意尝试使用资源，以便读取器和写入器在完成时自动关闭它们，在打印时使用for each循环更有效地迭代整个列表，并在处理读取的每个字符的逻辑中使用if/else-if。