优化孪生方法

Question

这个问题的第三部分说：

填写twin()类中的SList方法，使其按照注释中的指示执行。您的解决方案不应该使用数组。

下面是用8行代码为twin()方法编写的解决方案。对twin()方法进行了模块化测试。

public class SList {

  private SListNode head;
  private int size;

  /**
   *  SList() constructs an empty list.
   **/

  public SList() {
    size = 0;
    head = null;
  }

  /**
   *  isEmpty() indicates whether the list is empty.
   *  @return true if the list is empty, false otherwise.
   **/

  public boolean isEmpty() {
    return size == 0;
  }

  /**
   *  length() returns the length of this list.
   *  @return the length of this list.
   **/

  public int length() {
    return size;
  }

  /**
   *  insertFront() inserts item "obj" at the beginning of this list.
   *  @param obj the item to be inserted.
   **/

  public void insertFront(Object obj) {
    head = new SListNode(obj, head);
    size++;
  }

  /**
   *  insertEnd() inserts item "obj" at the end of this list.
   *  @param obj the item to be inserted.
   **/

  public void insertEnd(Object obj) {
    if (head == null) {
      head = new SListNode(obj);
    } else {
      SListNode node = head;
      while (node.next != null) {
        node = node.next;
      }
      node.next = new SListNode(obj);
    }
    size++;
  }

  /**
   *  nth() returns the item at the specified position.  If position < 1 or
   *  position > this.length(), null is returned.  Otherwise, the item at
   *  position "position" is returned.  The list does not change.
   *  @param position the desired position, from 1 to length(), in the list.
   *  @return the item at the given position in the list.
   **/

  public Object nth(int position) {
    SListNode currentNode;

    if ((position < 1) || (head == null)) {
      return null;
    } else {
      currentNode = head;
      while (position > 1) {
        currentNode = currentNode.next;
        if (currentNode == null) {
          return null;
        }
        position--;
      }
      return currentNode.item;
    }
  }

  /**
   *  squish() takes this list and, wherever two or more consecutive items are
   *  equal(), it removes duplicate nodes so that only one consecutive copy
   *  remains.  Hence, no two consecutive items in this list are equal() upon
   *  completion of the procedure.
   *
   *  After squish() executes, the list may well be shorter than when squish()
   *  began.  No extra items are added to make up for those removed.
   *
   *  For example, if the input list is [ 0 0 0 0 1 1 0 0 0 3 3 3 1 1 0 ], the
   *  output list is [ 0 1 0 3 1 0 ].
   *
   *  IMPORTANT:  Be sure you use the equals() method, and not the "=="
   *  operator, to compare items.
   **/

  public void squish() {
    // Fill in your solution here. (Ours is eleven lines long.)
      SListNode prevNode = null;
      SListNode curNode = null;
      if(size < 2){
          return;
      }
      prevNode = this.head;
      curNode = this.head.next;
      while(size >= 2){
            if(prevNode.item.equals(curNode.item)){
                prevNode.next = curNode.next;
            }else{
                prevNode = curNode;
            }

            size--;
            curNode = curNode.next;
      }

  }

  /**
   *  twin() takes this list and doubles its length by replacing each node
   *  with two consecutive nodes referencing the same item.
   *
   *  For example, if the input list is [ 3 7 4 2 2 ], the
   *  output list is [ 3 3 7 7 4 4 2 2 2 2 ].
   *
   *  IMPORTANT:  Do not try to make new copies of the items themselves.
   *  Just copy the references to the items.
   **/

  public void twin() {
    // Fill in your solution here.  (Ours is seven lines long.)
    if(size < 1)
        return;
    SListNode currentNode = this.head;
    while(currentNode != null){
        currentNode.next = new SListNode(currentNode.item, currentNode.next);
        currentNode = currentNode.next.next;
        size++;
    }
  }

  /**
   *  toString() converts the list to a String.
   *  @return a String representation of the list.
   **/

  public String toString() {
    int i;
    Object obj;
    String result = "[  ";

    SListNode cur = head;

    while (cur != null) {
      obj = cur.item;
      result = result + obj.toString() + "  ";
      cur = cur.next;
    }
    result = result + "]";
    return result;
  }

}

public class Homework3 {

  /**
   *  smoosh() takes an array of ints.  On completion the array contains
   *  the same numbers, but wherever the array had two or more consecutive
   *  duplicate numbers, they are replaced by one copy of the number.  Hence,
   *  after smoosh() is done, no two consecutive numbers in the array are the
   *  same.
   *
   *  Any unused elements at the end of the array are set to -1.
   *
   *  For example, if the input array is [ 0 0 0 0 1 1 0 0 0 3 3 3 1 1 0 ],
   *  it reads [ 0 1 0 3 1 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 ] after smoosh()
   *  completes.
   *
   *  @param ints the input array.
   **/

  public static void smoosh(int[] a) {
    // Fill in your solution here.  (Ours is fourteen lines long, not counting
    // blank lines or lines already present in this file.)
    int currentPointer = 1;
    int i, j = 0;
    for(i =0; i < a.length; i++){
        int flag = 0;
        for(j = currentPointer; j < a.length; j++)
            if(a[j] != a[i])
            {
                a[i+1] = a[j];
                currentPointer = ++j;
                flag = 1;
                break;
            }
        if(j == a.length){
            if(flag == 1)
                i+=2;
            else
                i += 1;
            for(int k = i; k < a.length; k++)
                a[k] = -1;
            break;
        }
    }
  }

  /**
   *  stringInts() converts an array of ints to a String.
   *  @return a String representation of the array.
   **/

  private static String stringInts(int[] ints) {
    String s = "[  ";
    for (int i = 0; i < ints.length; i++) {
      s = s + Integer.toString(ints[i]) + "  ";
    }
    return s + "]";
  }

  /**
   *  main() runs test cases on your smoosh and squish methods.  Prints summary
   *  information on basic operations and halts with an error (and a stack
   *  trace) if any of the tests fail.
   **/

  public static void main(String[] args) {
    String result;
    int i;


    System.out.println("Let's smoosh arrays!\n");

    int[] test1 = {3, 7, 7, 7, 4, 5, 5, 2, 0, 8, 8, 8, 8, 5};
    System.out.println("smooshing " + stringInts(test1) + ":");
    smoosh(test1);
    result = stringInts(test1);
    System.out.println(result);
    TestHelper.verify(result.equals(
            "[  3  7  4  5  2  0  8  5  -1  -1  -1  -1  -1  -1  ]"),
                      "BAD SMOOSH!!!  No cookie.");

    int[] test2 = {6, 6, 6, 6, 6, 3, 6, 3, 6, 3, 3, 3, 3, 3, 3};
    System.out.println("smooshing " + stringInts(test2) + ":");
    smoosh(test2);
    result = stringInts(test2);
    System.out.println(result);
    TestHelper.verify(result.equals(
            "[  6  3  6  3  6  3  -1  -1  -1  -1  -1  -1  -1  -1  -1  ]"),
                      "BAD SMOOSH!!!  No cookie.");

    int[] test3 = {4, 4, 4, 4, 4};
    System.out.println("smooshing " + stringInts(test3) + ":");
    smoosh(test3);
    result = stringInts(test3);
    System.out.println(result);
    TestHelper.verify(result.equals("[  4  -1  -1  -1  -1  ]"),
                      "BAD SMOOSH!!!  No cookie.");

    int[] test4 = {0, 1, 2, 3, 4, 5, 6};
    System.out.println("smooshing " + stringInts(test4) + ":");
    smoosh(test4);
    result = stringInts(test4);
    System.out.println(result);
    TestHelper.verify(result.equals("[  0  1  2  3  4  5  6  ]"),
                      "BAD SMOOSH!!!  No cookie.");


    System.out.println("\nLet's squish linked lists!\n");

    int[] test5 = {3, 7, 7, 7, 4, 5, 5, 2, 0, 8, 8, 8, 8, 5};
    SList list5 = new SList();
    for (i = 0; i < test5.length; i++) {
      list5.insertEnd(new Integer(test5[i]));
    }
    System.out.println("squishing " + list5.toString() + ":");
    list5.squish();
    result = list5.toString();
    System.out.println(result);
    TestHelper.verify(result.equals("[  3  7  4  5  2  0  8  5  ]"),
                      "BAD SQUISH!!!  No biscuit.");

    int[] test6 = {6, 6, 6, 6, 6, 3, 6, 3, 6, 3, 3, 3, 3, 3, 3};
    SList list6 = new SList();
    for (i = 0; i < test6.length; i++) {
      list6.insertEnd(new Integer(test6[i]));
    }
    System.out.println("squishing " + list6.toString() + ":");
    list6.squish();
    result = list6.toString();
    System.out.println(result);
    TestHelper.verify(result.equals("[  6  3  6  3  6  3  ]"),
                      "BAD SQUISH!!!  No biscuit.");

    int[] test7 = {4, 4, 4, 4, 4};
    SList list7 = new SList();
    for (i = 0; i < test7.length; i++) {
      list7.insertEnd(new Integer(test7[i]));
    }
    System.out.println("squishing " + list7.toString() + ":");
    list7.squish();
    result = list7.toString();
    System.out.println(result);
    TestHelper.verify(result.equals("[  4  ]"),
                      "BAD SQUISH!!!  No biscuit.");

    int[] test8 = {0, 1, 2, 3, 4, 5, 6};
    SList list8 = new SList();
    for (i = 0; i < test8.length; i++) {
      list8.insertEnd(new Integer(test8[i]));
    }
    System.out.println("squishing " + list8.toString() + ":");
    list8.squish();
    result = list8.toString();
    System.out.println(result);
    TestHelper.verify(result.equals("[  0  1  2  3  4  5  6  ]"),
                      "BAD SQUISH!!!  No biscuit.");

    SList list9 = new SList();
    System.out.println("squishing " + list9.toString() + ":");
    list9.squish();
    result = list9.toString();
    System.out.println(result);
    TestHelper.verify(result.equals("[  ]"),
                      "BAD SQUISH!!!  No biscuit.");


    System.out.println("\nLet's twin linked lists!\n");

    System.out.println("twinning " + list6.toString() + ":");
    list6.twin();
    result = list6.toString();
    System.out.println(result);
    TestHelper.verify(result.equals(
                      "[  6  6  3  3  6  6  3  3  6  6  3  3  ]"),
                      "BAD TWIN!!!  No gravy.");

    System.out.println("twinning " + list7.toString() + ":");
    list7.twin();
    result = list7.toString();
    System.out.println(result);
    TestHelper.verify(result.equals("[  4  4  ]"),
                      "BAD TWIN!!!  No gravy.");

    System.out.println("twinning " + list9.toString() + ":");
    list9.twin();
    result = list9.toString();
    System.out.println(result);
    TestHelper.verify(result.equals("[  ]"),
                      "BAD TWIN!!!  No gravy.");
  }

}

public class TestHelper {

  /**
   *  verify() checks an invariant and prints an error message if it fails.
   *  If invariant is true, this method does nothing.  If invariant is false,
   *  the message is printed, followed by a dump of the program call stack.
   *
   *  @param invariant  the condition to be verified
   *  @param message  the error message to be printed if the invariant fails to
   *                  hold true.
   **/

  static void verify(boolean invariant, String message) {
    if (!invariant) {
      System.out.println("*** ERROR:  " + message);
      Thread.dumpStack();
    }
  }
}

class SListNode {
  Object item;
  SListNode next;


  /**
   *  SListNode() (with two parameters) constructs a list node referencing the
   *  item "obj", whose next list node is to be "next".
   */

  SListNode(Object obj, SListNode next) {
    item = obj;
    this.next = next;
  }

  /**
   *  SListNode() (with one parameter) constructs a list node referencing the
   *  item "obj".
   */

  SListNode(Object obj) {
    this(obj, null);
  }
}

测试用例：

让我们把两个链表连起来！孪生6 3 6 3 6 3：6 6 3 3 6 6孪生4.：4 4孪生undefined：undefined

我的问题是：

我可以用将近7行(8行)为twin()方法做解决方案。我们还能像评论中提到的那样把这个压缩到7行吗？

注意:此代码不打算遵循OOP原则。

Answer 1

没有必要检查

if(size < 1)
    return;

请养成永不漏掉可选大括号的习惯。引入bug的可能性不值得节省几个字符。

循环可以写成for-循环，因此可能应该是：

public void twin() {
    for (SListNode node = this.head; node != null; node = node.next.next) {
        node.next = new SListNode(node.item, node.next);
        this.size++;
    }
}