Saya mencoba menulis kode untuk kursor bergerak sederhana di Jawa. Saya harus menggunakan daftar ditautkan dua kali lipat. Saya juga harus menerapkan kelas DoubyLinkedList sendiri. Dalam program ini pertama kita ambil integer seperti n dari pengguna sebagai jumlah garis. Lalu kita ambil n baris input. Setiap baris hanya berisi satu karakter yang bisa < atau > atau - atau salah satu huruf kecil alfabet bahasa Inggris. Untuk > atau < kita memindahkan kursor ke kanan atau kiri. Untuk - Kami menghapus karakter di tempat kursor. Untuk huruf, kami menambahkannya ke daftar ditautkan dua kali lipat. Akhirnya kami mencetak hasilnya dalam satu baris tanpa spasi. Saya telah membuat DoubylinkedLists kelas dan metode yang dibutuhkan. Saya pikir itu berfungsi dengan baik tetapi kompleksitas waktu kode harus O(n). Saya kira itu O(n^2) sekarang.

import java.util.*;
public class DoublyLinkedList {
static Node head = null;
static int size = 0;
class Node {
    String data;
    Node prev;
    Node next;
    Node(String d) {
        data = d;
    }
}
static Node deleteNode(Node del) {
    if (head == null || del == null)
        return null;
    if (head == del)
        head = del.next;
    if (del.next != null)
        del.next.prev = del.prev;
    if (del.prev != null)
        del.prev.next = del.next;
    del = null;
    size --;
    return head;
}
public String GetNth(int index) {
    Node current = head;
    int count = 0;
    while (current != null)
    { if (count == index)
        return current.data;
        count++;
        current = current.next;
    }
    assert (false);
    return null;
}
public static void deleteNodeAtGivenPos(int n) {
    size--;
    if (head == null || n <= 0)
        return;
    Node current = head;
    int i;
    for (i = 1; current != null && i < n; i++)
        current = current.next;
    if (current == null)
        return;
    deleteNode(current);
}
void insertFirst (String data){
    size++;
    Node newNode = new Node(data);
    if (head == null) {
        newNode.prev = null;
        head = newNode;
        return;
    }
    else
        head.prev= newNode;
    newNode.next=head;
    head = newNode;
}
void append(String data) {
    size++;
    Node newNode = new Node(data);
    Node last = head;
    newNode.next = null;
    if (head == null) {
        newNode.prev = null;
        head = newNode;
        return;
    }
    while (last.next != null)
        last = last.next;
    last.next = newNode;
    newNode.prev = last;
}
public void insertAtGivenPos(String s , int index){
    Node newNode= new Node(s);
    Node current= head;
    if (index==0)
        insertFirst(s);
    else if(index==size)
        append(s);
    else{
        for(int j = 0; j < index && current.next != null; j++){
            current = current.next;
        }
        newNode.next = current;
        current.prev.next = newNode;
        newNode.prev = current.prev;
        current.prev = newNode;
        size++;
    }
}
public void print(Node node) {
    while (node != null) {
        System.out.print(node.data + "");
        node = node.next;
    }
}
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = Integer.parseInt(sc.nextLine());
    String [] arr= new String[n];
    for (int i=0; i< n; i++)
        arr[i] = sc.nextLine();
    DoublyLinkedList dll = new DoublyLinkedList();
    int cursor= 0;
    for (int i=0; i< n; i++){
        if (arr[i].matches("[a-z]")){
            dll.insertAtGivenPos(arr[i], cursor);
            cursor++;
        }
        else if (arr[i].contains("-")&& dll.GetNth(cursor-1)!= null) {
            dll.deleteNodeAtGivenPos(cursor);
            cursor--;
        }
        else if (arr[i].contains("<") && dll.GetNth(cursor-1)!= null)
            cursor--;
        else if (arr[i].contains(">") && dll.GetNth(cursor+1)!= null)
            cursor++;
    }
    dll.print(dll.head);
}
}

Bagaimana saya dapat meningkatkan kode saya untuk mengurangi kompleksitas waktu?

Edit : Saya juga mengerti bahwa kode saya memberikan jawaban yang salah untuk beberapa kasus. Bisakah Anda membantu saya men-debug?

0
user1238777 4 April 2021, 16:20

2 jawaban

Jawaban Terbaik

Jika Anda tidak dipaksa mengikuti detail implementasi, saya sarankan untuk tidak memiliki kursor. Sebaliknya, simpan variabel currentNode yang merupakan simpul bahwa cursor akan menunjuk. Jadi untuk setiap perintah (atau data) dalam loop input, Anda memiliki operasi satu O (1) seperti di bawah ini dan karenanya akan mendapatkan kompleksitas waktu O (n).

1 - untuk >: ubah currentNode ke currentNode.next}

2 - untuk < lakukan sebaliknya

3 - untuk - Ubah node sebelumnya dan berikutnya currentNode untuk Tunjukkan satu sama lain (jadi arus dihapus)

4 - dan akhirnya untuk penyisipan: Buat node dan seperti 3, ubah node samping untuk menunjuk ke sana

1
fmatt 4 April 2021, 15:21

Anda tidak perlu loop dalam. memproses input segera setelah Anda menerimanya.

for (int i=0; i< n; i++)
    arr[i] = sc.nextLine();
    DoublyLinkedList dll = new DoublyLinkedList();
    int cursor= 0;
    if (arr[i].matches("[a-z]")){
        dll.insertAtGivenPos(arr[i], cursor);
        cursor++;
    }
    else if (arr[i].contains("-")&& dll.GetNth(cursor-1)!= null) {
        dll.deleteNodeAtGivenPos(cursor);
        cursor--;
    }
    else if (arr[i].contains("<") && dll.GetNth(cursor-1)!= null)
        cursor--;
    else if (arr[i].contains(">") && dll.GetNth(cursor+1)!= null)
        cursor++;
}
0
Vishal Maral 4 April 2021, 13:36