-1

問題 4: 与えられた整数配列を、各ノードが 1 つのシーケンスを含む連結リストに変換します。

Sample Input : [1, 3, 4, 5, 8, 9, 11, 13, 14, 15, 16, 20, 23, 30,31,32]
Sample Linked List : [1] -> [3,4,5] -> [8,9] -> [11] -> [13,14,15,16]->[20]->[23]->[30,31,32]

質問は簡単に思えるかもしれませんが、答えるのが少し難しいです。またはを使用せずに Java で上記のコードを記述できる人はいますCollectionLinkedList?

以下は、シーケンスを検出するためのコードです (役立つ場合があります)。

class Sequence {
    public static String detectSequence(int seq[]) {
        String result = "";
        for (int i = 0; i < seq.length - 1; i++) {
            if (seq[i + 1] == seq[i] + 1) {
                result += seq[i] + " ";
                if (i != seq.length - 2) {
                    if (seq[i + 1] != seq[i + 2] - 1) {
                        result += seq[i + 1];
                    }
                }
            } else {
                result += " ";
            }
        }
        if (seq[seq.length - 1] == seq[seq.length - 2] + 1) {
            result += seq[seq.length - 1];
        }
        return result;
    }
}
class Question1 {
    public static void main(String[] cla) {
        int seqArray[] = {
            4, 1, 2, 3, 4, 5, 8, 4, 7, 4, 5, 6, 7, 7, 7, 7, 7, 10, 11, 13, 1, 2, 3, 4
        };
        String res = Sequence.detectSequence(seqArray);
        System.out.println(res);
    }
}
4

2 に答える 2

0

始めるためだけに...

public YourLinkedList splitToSequences(int[] array) {
    YourLinkedList list = new YourLinkedList();

    if(array.length > 0) {
        YourSequence sequence = new YourSequence();
        int currentNumber;
        int lastNumber = array[0];
        sequence.add(lastNumber);

        for(int index = 1; index < array.length; index++) {
            currentNumber = array[index];
            if(currentNumber != lastNumber + 1) { // curentNumber breaks the sequence
                list.add(sequence);               // save the old sequence to list 
                sequence = new YourSequence();    // and start a new one
            }
            sequence.add(currentNumber);
        }

        list.add(sequence);
    }
    return list;
}

次に、リンクされたリストとシーケンスクラスを見つけて、印刷作業を行います...

リンクされたリストの最小限の実装

public class MyLinkedList<T1> {
    private MyLinkedListItem<T1> first = null;
    private MyLinkedListItem<T1> last = null;

    public MyLinkedList() {
    }

    public void add(T1 item) {
        MyLinkedListItem<T1> newItem = new MyLinkedListItem<T1>(item);
        if (first == null) {
            first = newItem;
        } else {
            last.setNext(newItem);
        }
        last = newItem;
    }

    @Override
    public String toString() {
        StringBuffer buffer = new StringBuffer();

        if(first != null) {
            MyLinkedListItem<T1> current = first;

            while(current.hasNext()) {
                buffer.append(current.toString());
                buffer.append(" -> ");
                current = current.getNext();
            }

            buffer.append(current.toString());
        }

        return buffer.toString();
    }

    private class MyLinkedListItem<T2> {
        private T2 data;
        private MyLinkedListItem<T2> next = null;

        public MyLinkedListItem(T2 data) {
            this.data = data;
        }

        public boolean hasNext() {
            return next != null;
        }

        public MyLinkedListItem<T2> getNext() {
            return next;
        }

        public void setNext(MyLinkedListItem<T2> next) {
            this.next = next;
        }

        @Override
        public String toString() {
            return data.toString();
        }
    }
}
于 2013-05-03T08:23:24.267 に答える
0

最初に、配列を複数のチャンクに分割するコードを Iterator を使用して記述し、このアルゴリズムを連結リストを作成するコードと混在させないようにすることができます。次に、機能的な方法で単純なリンクされたリストを実装する方法があります (したがって、リスト全体が不変です)。

明らかに、このコードは判読できませんが、楽しいものです。

import java.util.Arrays;
import java.util.Iterator;
import java.util.function.Consumer;
import java.util.function.Function;
import java.util.stream.IntStream;

public class LinkedConsecutiveInts {
  private static Iterator<int[]> iterator(int[] array) {
    return new Iterator<int[]>() {
      private int index;

      @Override
      public boolean hasNext() {
       return index < array.length;
      }

      @Override
      public int[] next() {
        int first = array[index];
        int value = first + 1;
        int i = 1;
        for(; index + i < array.length && array[index + i] == value++; i++) {
          // empty
        }
        index += i;
        return IntStream.range(first, first + i).toArray();
      }
    };
  }

  interface Seq<T> {
    void forEach(Consumer<? super T> consumer);

    default <U> Seq<U> map(Function<? super T, ? extends U> mapper) {
      return consumer -> forEach(e -> consumer.accept(mapper.apply(e)));
    }

    default String joining(String separator) {
      StringBuilder builder = new StringBuilder();
      forEach(e -> builder.append(e).append(separator));
      if (builder.length() != 0) {
        builder.setLength(builder.length() - separator.length());
      }
      return builder.toString();
    }

    static <T> Seq<T> from(Iterator<? extends T> it) {
      if (!it.hasNext()) {
        return consumer -> { /* empty */ };
      }
      T element = it.next();
      Seq<T> next = from(it);
      return consumer -> { consumer.accept(element); next.forEach(consumer); };
    }
  }

  public static void main(String[] args) {
    int[] values = { 1, 3, 4, 5, 8, 9, 11, 13, 14, 15, 16, 20, 23, 30, 31, 32 };

    Seq<int[]> seq = Seq.from(iterator(values)); 
    System.out.println(seq.map(Arrays::toString).joining(" -> "));
  }
}
于 2015-12-18T22:30:35.090 に答える