getLastIndexOf (int element) Linked

stemmer
0

Jeg er for tiden en freshman komp sci student arbeider med å lære datastrukturer både gjennom min klasse og også på nettet.

Jeg er ny på stable også, men det har hjulpet meg mye i det siste.

Min nåværende problem er å søke gjennom en Linked å returnere den siste indeksen som nummer vises i listen.

Jeg føler at dette har å gjøre noe med rekursjon og kontinuerlig søke til du kan liksom sjekke sikkert at det er den siste forekomsten av dette elementet, deretter tilbake sin indeks.

Men min første semester Java selvfølgelig ikke dekke rekursjon i det hele tatt, og jeg er liksom på et tap.

Å være i disse kursene jeg ikke ber om det flate ut svaret, jeg trenger bare noen retning. Eller forsikre meg om at jeg er på rett vei med å se inn rekursjon i det hele tatt?

Også her er det jeg har forsøkt så langt. Takk for hjelpen!

public int getLastIndexOf(int lastItem) { //goal is to return the lastindex at which that number appears last
    Node current;
    current = head;
    int count = 0; //count variable 
    while (current.next != null) { //go through list
        if (current.dataItem == lastItem) { 
            //check rest of the list for if that number exists beyond
        }
        count++; //increment count for every time loop executes
        current = current.next; //moves onto next node to check
    }
    return -1;
}
Publisert på 25/02/2017 klokken 16:06
bruker
På andre språk...                            


3 svar

stemmer
1

Du kan bare lagre og overskrive indeksen når du har en kamp som så:

public int getLastIndexOf(int lastItem) { //goal is to return the lastindex at which that number appears last
    Node current;
    current = head;
    int count = 0; //count variable
    int lastIndex = 0;
    while (current.next != null) { //go through list
        if (current.dataItem == lastItem) { 
                lastIndex = count;
        }
        count++; //increment count for every time loop executes
        current = current.next; //moves onto next node to check
    }
return lastIndex;

Så du vil lagre posisjonen til kampen i lastIndex, og hvis det er mer enn ett treff, vil du bare overskrive den med den "siste" verdi.

Svarte 25/02/2017 kl. 16:21
kilden bruker

stemmer
0

Tenk på listen for å være en node etterfulgt av en annen liste, kalt halen. Dette er pseudokode, merk at du trenger to metoder, privateman tar en node, er dette sub-listen.

public int getLastIndexOf(value) {
    return getLastIndexOf(head, value);
}

private int getLastIndexOf(sublist, value) {
    //check the tail first (because we want last index)
    if (sublist.tail != null) {//list has a tail
        int lastIndexInTail = getLastIndexOf(sublist.tail, value); //recursion
        if(lastIndexInTail != -1)
          return lastIndexInTail + 1; //it's in the sub list, the sub list starts at idx 1
    }

    // it's not in the tail, check this head
    if (sublist.data == value){
      return 0; //it's at the front of this list
    }

    return -1; //it's not in the head or in the tail of sublist
}
Svarte 25/02/2017 kl. 16:21
kilden bruker

stemmer
0

Hvis du ønsker å gjøre det ved rekursjon

Denne veiledningen fra TopCoder kan være nyttig her.

Mine 2 cents følger:

Rekursjon og iterasjon (løkker, som for, mens etc.) kan brukes til å løse dagens problem.

Din nåværende koden er ikke rekursiv, det er iterativ. Rekursjon skjer når du kaller den samme funksjonen igjen og igjen til noen ende tilstand.

En rekursiv funksjon har to deler:

  1. basen tilstand - forteller deg når du skal stoppe rekursjon
  2. den rekursive tilstand - forteller deg når du skal gjøre rekursjon

La oss se dette med et eksempel. Si at du ønsker å skrive ut "Hello World" 10 ganger. Her er hvordan du ville gjøre det iterativt

for(int i = 0; i < 10; i++){
   System.out.println("Hello World");
}

Og her er hvordan du gjør det rekursivt

void helloWorldPrinter(int index){
   //This is the base condition, tells us to stop when we've reached 10
   if(index == 10){
      return;
   }
   else{
      //Print for the n th hello world
      System.out.println("Hello World");
      //call the same function for printing the next (n+1 th) hello world
      helloWorldPrinter(index+1); //Looks similar to the i++ in the loop right?
   }
}

Rekursjon er utrolig nyttig i binærtrær som er datastrukturer som ser ut som opp ned trær. Et konsept som du kan huske på når du skriver iterativ vs rekursiv koden er at gjentakelse er som å se på datastrukturen som observatør og gjøre handlinger på it.Recursion fortsetter som om du er et element i datastrukturen - du gjør jobben din og pass ansvaret til neste element (ved rekursive kall)

Nå tror jeg du kan utvide denne logikken til å finne den siste elementet i lenket liste. Selv om en iterativ løsning på dette ville være mye lettere enn en rekursiv en.

Logikken er:

Loop over list (iterative or recursive)
  If element is found, note down the index
End Loop if list has been traversed completely
return the element index
Svarte 25/02/2017 kl. 16:22
kilden bruker

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more