Sprawdzenie algorytmu

Odpowiedz Nowy wątek
2012-02-27 23:30

Rejestracja: 13 lat temu

Ostatnio: 7 lat temu

0

Mam takie zadanie ze SPOJ-a: http://www.spoj.pl/problems/PHONELST/

I próbowałem je zrobić na kilka różnych sposobów. Niestety ciągle dostaję błąd wykonania i nie mam pojęcia dlaczego.

Oto mój kod z użyciem drzewa Trie:

import java.io.DataInputStream;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;

class Glowna {

    static class Parser
    {
       final private int BUFFER_SIZE = 1 << 16;

       private DataInputStream din;
       private byte[] buffer;
       private int bufferPointer, bytesRead;

       public Parser(InputStream in)
       {
          din = new DataInputStream(in);
          buffer = new byte[BUFFER_SIZE];
          bufferPointer = bytesRead = 0;
       }

       public int nextInt() throws Exception
       {
          int ret = 0;
          byte c = read();
          while (c <= ' ') c = read();
          boolean neg = c == '-';
          if (neg) c = read();
          do
          {
             ret = ret * 10 + c - '0';
             c = read();
          } while (c > ' ');
          if (neg) return -ret;
          return ret;
       }

       public String nextString() throws Exception
       {
           String ret = "";
           byte c=read();
           ArrayList<Byte> bytes=new ArrayList<Byte>();
           while(c <= ' ') c=read();
           do {
               bytes.add(c);
               c=read();
           }
           while(c>' ');
           byte[] d=new byte[bytes.size()];
           for(int a=0; a<bytes.size(); a++) d[a]=bytes.get(a);
           ret=new String(d);
           return ret.trim();
       }

       public String nextLine() throws Exception {
           byte c=read();
           while(c==10 || c==13) c=read();
           ArrayList<Byte> bytes=new ArrayList<Byte>();
           do {
               bytes.add(c);
               c=read();
           }
           while(c != 13 && c != 10 && c!=-1);
           byte[] d=new byte[bytes.size()];
           for(int a=0; a<bytes.size(); a++) d[a]=bytes.get(a);
           String ret=new String(d);
           return ret.trim();
       }

       public String readAll() throws Exception {
           byte c=read();
           while(c==10 || c==13) c=read();
           ArrayList<Byte> bytes=new ArrayList<Byte>();
           do {
               bytes.add(c);
               c=read();
           }
           while(c!=-1);
           byte[] d=new byte[bytes.size()];
           for(int a=0; a<bytes.size(); a++) d[a]=bytes.get(a);
           String ret=new String(d);
           return ret.trim();
       }

       private void fillBuffer() throws Exception
       {
          bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
          if (bytesRead == -1) buffer[0] = -1;
       }

       private byte read() throws Exception
       {
          if (bufferPointer == bytesRead) fillBuffer();
          return buffer[bufferPointer++];
       }

    }

    public static class Node {
         char content;
         boolean marker;
         Collection<Node> child;

         public Node(char c){
          child = new LinkedList<Node>();
          marker = false;
          content = c;
         }

         public String toString() {
             String ret=String.valueOf(content);
             for(Node n: child) ret+=n.toString();
             return ret;
         }

         public Node subNode(char c){
          if(child!=null){
           for(Node eachChild:child){
            if(eachChild.content == c){
             return eachChild;
            }
           }
          }
          return null;
         }
        }

    public static class Trie{
         private Node root;

         public Trie(){
          root = new Node(' ');
         }

         public void insert(String s){
          Node current = root;
          if(s.length()==0) //For an empty character
           current.marker=true;
          for(int i=0;i<s.length();i++){
           Node child = current.subNode(s.charAt(i));
           if(child!=null){
            current = child;
           }
           else{
            current.child.add(new Node(s.charAt(i)));
            current = current.subNode(s.charAt(i));
           }
           // Set marker to indicate end of the word
           if(i==s.length()-1)
            current.marker = true;
          }
         }

         public boolean search(String s){
          Node current = root;
          while(current != null){
           for(int i=0;i<s.length();i++){   
            if(current.subNode(s.charAt(i)) == null)
             return false;
            else
             current = current.subNode(s.charAt(i));
           }
           /*
            * This means that a string exists, but make sure its
            * a word by checking its 'marker' flag
            */
           if (current.marker == true)
            return true;
           else
            return false;
          }
          return false;
         }

         public boolean contains(String s){
              Node current = root;
              while(current != null){
               for(int i=0;i<s.length();i++){   
                if(current.subNode(s.charAt(i)) == null) return false;
                else
                 current = current.subNode(s.charAt(i));
               }
               /*
                * This means that a string exists, but make sure its
                * a word by checking its 'marker' flag
                */
               if(current!=null) return true;
               else return false;
              }
              return false;
             }

         public boolean isUnique() {
             for(Node n: root.child) {
                 if(!isUnique(n)) return false;
             }
             return true;
         }

         public boolean isUnique(Node n) {
             if(n.marker && n.child.size()>0) return false;
             else for(Node k: n.child) return isUnique(k);
             return true;
         }

         public String toString() {
             String ret="";
             for(Node n: root.child) if(n.marker) ret+=n.toString();
             return ret;
         }

        }

    public static void main(String[] args) throws Exception {
        Parser br = new Parser(System.in);
        int x=br.nextInt();
        for(int i=0; i<x; i++) {
        Trie drzewo=new Trie();
        int numerow=br.nextInt();
        boolean consistent=true;
        for(int t=0; t<numerow && consistent; t++) {
            String slowo=br.nextString();
            drzewo.insert(slowo);
        }
        consistent=drzewo.isUnique();
        if(consistent) System.out.println("YES");
        else System.out.println("NO");
        }
    }

}

Będę wdzięczny za każdą pomoc

Pozostało 580 znaków

2012-02-28 20:02

Rejestracja: 12 lat temu

Ostatnio: 2 minuty temu

0

Od sprawdzania takich rzeczy są testy!
Stwórz sobie jakiś plik z testami o różnych warunkach brzegowych i uruchom swój program za pomocą debuggera (najlepiej jeden plik z testami tylko na tak i drugi z testami tylko na nie).
Swoją drogą problem jest tak prosty, że aż dziw bierze, że twój kod jest aż tak długi.

Czy drzewo nie jest przekombinowaniem? Każdy węzeł to alokacja, a to kosztuje i to dość dużo nie mówiąc o dodatkowej pracy dla gc.
Ja bym po prostu posortował leksykograficznie numery telefonów, a potem porównał sąsiadów.
To daje złożoność o(n * log n), ale przy minimalnym narzucie na manipulowanie pamięcią, więc będzie szybsze od twojego rozwiązania.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 1x, ostatnio: MarekR22, 2012-02-28 20:21

Pozostało 580 znaków

2012-02-29 23:55

Rejestracja: 13 lat temu

Ostatnio: 7 lat temu

0

Próbowałem tak, ale jednak to nie dało efektu (nie mieściło się w czasie).

Natomiast teraz wykodziłem coś trochę innego, a mianowicie już w trakcie dodawania wychodzi, że dana lista jest consistent lub nie jest. I potem od razu można wypisać wynik po dodaniu wszystkich numerów z listy, nie trzeba już sprawdzać tego.

Testuję różne przypadki i szczerze mówiąc nie mogę dostrzec błędu dlatego poprosiłem tutaj o pomoc.

Mój aktualny kod:

import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Collection;
import java.util.LinkedList;

class Glowna {

    static boolean unique=true;

    public static class Node {
         long content;
         boolean marker;
         Collection<Node> child;

         public Node(long c){
          child = new LinkedList<Node>();
          marker = false;
          content = c;
         }

         public String toString() {
             String ret=String.valueOf(content);
             for(Node n: child) ret+=n.toString();
             return ret;
         }

         public Node subNode(long c){
          if(child!=null){
           for(Node eachChild:child){
            if(eachChild.content == c){
             return eachChild;
            }
           }
          }
          return null;
         }
        }

    public static class Trie{
         private Node root;

         public Trie(){
          root = new Node(' ');
         }

         public void insert(String s){
          Node current = root;
          if(s.length()==0) //For an empty character
           current.marker=true;
          for(int i=0;i<s.length();i++){
           Node child = current.subNode(s.charAt(i));
           if(child!=null){
            current = child;
            if(current.marker) unique=false;
           }
           else{
            current.child.add(new Node(s.charAt(i)));
            current = current.subNode(s.charAt(i));
            if(current.marker) unique=false;
           }
           // Set marker to indicate end of the word
           if(i==s.length()-1)
            if(current.marker || current.child.size()>0) unique=false;
            else current.marker = true;
          }
         }

         public boolean search(String s){
          Node current = root;
          while(current != null){
           for(int i=0;i<s.length();i++){   
            if(current.subNode(s.charAt(i)) == null)
             return false;
            else
             current = current.subNode(s.charAt(i));
           }
           /*
            * This means that a string exists, but make sure its
            * a word by checking its 'marker' flag
            */
           if (current.marker == true)
            return true;
           else
            return false;
          }
          return false;
         }

         public boolean isUnique() {
             return unique;
         }

         public String toString() {
             String ret="";
             for(Node n: root.child) if(n.marker) ret+=n.toString();
             return ret;
         }

        }

    public static void main(String[] args) throws Exception {
        StreamTokenizer br = new StreamTokenizer(new InputStreamReader(System.in));
        br.nextToken();
        int x=(int) br.nval;
        for(int i=0; i<x; i++) {
        unique=true;
        Trie drzewo=new Trie();
        br.nextToken();
        int numerow=(int) br.nval;
        boolean consistent=true;
        for(int t=0; t<numerow && consistent; t++) {
            br.nextToken();
            drzewo.insert(String.valueOf((long) br.nval));
        }
        consistent=drzewo.isUnique();
        if(consistent) System.out.println("YES");
        else System.out.println("NO");
        }
    }

}

Próbowałem również powyższą metodą, ale dalej błędna odpowiedź, oto mój kod dla powyższej metody, którą Mark zasugerował:

import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class Glowna {

    public static class Sortowanie implements Comparator<Long> {

        public int compare(Long l1, Long l2) {
            String s1=String.valueOf(l1);
            String s2=String.valueOf(l2);
            return s1.compareTo(s2);
        }

    }

    public static void main(String[] args) throws Exception {
        StreamTokenizer br=new StreamTokenizer(new InputStreamReader(System.in));
        br.nextToken();
        int testy=(int) br.nval;
        boolean znaleziono=false;
        for(int i=0; i<testy; i++) {
            br.nextToken();
            long n=(long) br.nval;
            ArrayList<Long> lista = new ArrayList<Long>();
            for(long k=0; k<n; k++) {
                br.nextToken();
                lista.add((long) br.nval);
            }
            Collections.sort(lista,new Sortowanie());
            znaleziono=false;
            if(lista.size()==2) {
                String s1=String.valueOf(lista.get(0));
                String s2=String.valueOf(lista.get(1));
                znaleziono=s2.startsWith(s1);
            }
            else if(lista.size()>2) {
            String str1="";
            String str2="";
            for(long x=1; x<lista.size() && !znaleziono; x++) {
            str1=String.valueOf(lista.get((int) (x-1)));
            str2=String.valueOf(lista.get((int) x));
            znaleziono=str2.startsWith(str1);
            }
            }
            if(znaleziono) System.out.println("NO");
            else System.out.println("YES");
        }
    }

}
edytowany 1x, ostatnio: pawel_d, 2012-03-01 00:19

Pozostało 580 znaków

2012-03-01 10:38

Rejestracja: 12 lat temu

Ostatnio: 2 minuty temu

za dużo tych konwersji! Po co konwertujesz do Long skoro i tak porównanie w sortowaniu robisz w string? Co jeśli numer ma wiodące zera (pewnie dlatego masz złą odpowiedź)?
Najprostsze rozwiązanie to wczytać string i je posortować bezpośrednio, a potem sprawdzić czy i-ty element zaczyna się od elementu i-1. Zero konwersji między int a string!

Ja zrobiłem konwersję do long, ale pomnażałem liczby przez potęgę 10 zależnie ile brakowało do pełnej długości numeru i zapamiętywałem ten czynnik. ... dalej się domyśl.


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.

Pozostało 580 znaków

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0