Algorithm LinkedList Problems How to Reduce the Common Intermediate Complex-CodePudding

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();
    }
}

input example
```
2
<<BP<A>>Cd-
ThIsIsS3Cr3t
```
output example
```
BAPC
ThIsIsS3Cr3t
```

The time limit is 2 seconds.

I used the BufferedReader instead of Scanner to speed up the performance and used BufferedWriter instead of System.out.println (). However, the correct answer was a timeout problem. Is there a way to reduce time complexity while using a linkedlist?

CodePudding user response：

get() on a LinkedList is an O(N) operation, so if you're looking for speed, it should be avoided. You can instead use a ListIterator to get a cursor into the list that can be moved around much more efficiently compared to using an index, and used to insert or remove elements too.

You can also just use input.charAt() once and save the result in a char variable instead of calling it many times in a loop on the same index. It's a fast function call, but why call it more than you really need to, especially if working under a clock?

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');
            }
        }
    }
}

Also note the try-with-resources for the reader and writer to automatically close them when done, a for-each loop to more efficiently iterate over the entire list when printing, and using if/else if in the logic of what to do with each character you read.