列车组成的最佳解决方案 [英] Best Solution For the Train Composition

问题描述

最近我回答了我的在线面试测试，其中有人问我以下问题

Recently I answered My Online Interview test Wherein I was asked Following question

通过从左边附加和拆卸货车建造一个TrainComposition

A TrainComposition is built by attaching and detaching wagons from the left and the right sides.

例如，如果我们首先从左侧安装旅行车7，然后再从左侧安装旅行车13，我们将得到两个组合货车（从左到右分别为13和7）。现在可以从右侧分离的第一辆货车是7，第一辆可以从左侧拆卸的货车是13.实施一个模拟这个问题的TrainComposition。

For example, if we start by attaching wagon 7 from the left followed by attaching wagon 13, again from the left, we get a composition of two wagons (13 and 7 from left to right). Now the first wagon that can be detached from the right is 7 and the first that can be detached from the left is 13. Implement a TrainComposition that models this problem.

我使用双向链表来解决问题

I used doubly linked list to solve the issue

class Node

{
    protected int data;
    protected Node next, prev;
    /* Constructor */
    public Node()
    {
        next = null;
        prev = null;
        data = 0;
    }

    /* Constructor */

    public Node(int d, Node n, Node p)
    {
        data = d;
        next = n;
        prev = p;
    }

    /* Function to set link to next node */
    public void setLinkNext(Node n) {
        next = n;
    }
    /* Function to set link to previous node */
    public void setLinkPrev(Node p) {
        prev = p;
    }

    /* Funtion to get link to next node */

    public Node getLinkNext() {
        return next;
    }

    /* Function to get link to previous node */

    public Node getLinkPrev() {
        return prev;
    }

    /* Function to set data to node */
    public void setData(int d) {
        data = d;
    }

    /* Function to get data from node */

    public int getData() {
        return data;
    }
}

public class SortedSearch {
    protected Node start;
    protected Node end;
    public int size;
    /* Constructor */
    public SortedSearch()
    {
        start = null;
        end = null;
        size = 0;
    }
    public boolean isEmpty()
    {
        return start == null;
    }

    public int getSize()
    {
        return size;
    }

    public void attachWagonFromLeft(int wagonId) {
        Node nptr = new Node(wagonId, null, null);
        if (start == null)
        {
            start = nptr;
            end = start;
        }
        else
        {
            start.setLinkPrev(nptr);
            nptr.setLinkNext(start);
            start = nptr;
        }
        size++;
    }
    public void attachWagonFromRight(int wagonId) {
        Node nptr = new Node(wagonId, null, null);
        if (start == null)
        {
            start = nptr;
            end = start;
        }
        else
        {
            nptr.setLinkPrev(end);
            end.setLinkNext(nptr);
            end = nptr;
        }
        size++;
    }
    public int detachWagonFromLeft() {
        int value=0;
        if (size == 1)
        {
            value = start.getData();
            start = null;
            end = null;
            size = 0;
            return value;

        }
        value = start.getData();
        start = start.getLinkNext();
        start.setLinkPrev(null);
        size--;
        return value;
    }

    public int detachWagonFromRight() {
        int value=0;
            value = end.getData();
            end = end.getLinkPrev();
            end.setLinkNext(null);
            size-- ;
            return value;
    }

    public static void main(String[] args) {
        SortedSearch tree = new SortedSearch();
        tree.attachWagonFromLeft(7);
        tree.attachWagonFromLeft(13);
        tree.attachWagonFromLeft(12);
        tree.attachWagonFromLeft(10);
        tree.attachWagonFromLeft(6);
        tree.attachWagonFromLeft(4);
        tree.attachWagonFromLeft(3);
        tree.attachWagonFromLeft(2);
        System.out.println(tree.detachWagonFromRight()); // 7
        System.out.println(tree.detachWagonFromRight()); // 13
        System.out.println(tree.detachWagonFromRight()); // 7
        System.out.println(tree.detachWagonFromRight()); // 13
        System.out.println(tree.detachWagonFromRight()); // 7
        System.out.println(tree.detachWagonFromRight()); // 13

    }
}

并相应测试。但在提交时，它表示内部测试案例失败，答案标记错误。
能告诉你哪个是这个问题的最佳解决方案。

And tested it accordingly. But when submitted it said failed internal test cases, and the answer was marked wrong. Can you please tell which is the best solution for this problem.

推荐答案

为什么不使用这个简单的实现呢？

Why not just use this simple implementation?

private static class TrainComposition {

  private final Deque<Integer> wagons = new LinkedList<>();

  public void attachLeft(int wagonNumber) {
    wagons.addFirst(wagonNumber);
  }

  public void attachRight(int wagonNumber) {
    wagons.addLast(wagonNumber);
  }

  public void detachLeft() {
    if (!wagons.isEmpty()) {
      wagons.removeFirst(); // Alternative if exception should not be bubbled up: wagons.pollFirst()
    } else {
      throw new IndexOutOfBoundsException("No wagons available");
    }
  }

  public void detachRight() {
    if (!wagons.isEmpty()) {
      wagons.removeLast(); // Alternative if exception should not be bubbled up: wagons.pollLast()
    } else {
      throw new IndexOutOfBoundsException("No wagons available");
    }
  }
}

这篇关于列车组成的最佳解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！