java - 我怎样才能解决这个涉及具有最小内存需求的队列的 Java 编程挑战？

Question

所以我有这个编程挑战http://www.codewars.com/kata/double-cola我有一个队列中的人员列表，每次有人到达第一个位置时，它就会加倍并到达队列的末尾。

例如我有 x,y,z

x,y,z 下一个循环是y,z,x,x 然后是 z,x,x,y,y 然后是 x,x,y,y,z,z 然后是 x,y,y,z,z,x,x 然后是 y,y,z, z,x,x,x,x 等

这是我在 eclipse 中完美运行的代码。

public class Line {

static Node first;
    static Node last;
    static int N;

    private static class Node
    {
        String name;
        Node next;
    }

    public static boolean isEmpty() { return first == null; }

    public static void enqueue(String name)
    {
        Node oldlast = last;
        last = new Node();
        last.name = name;
        last.next = oldlast;
        if(isEmpty()) first = last;
        else oldlast.next = last;
        N++;
    }

    public static String dequeue()
    {
        String name = first.name;
        first = first.next;
        N--;
        if(isEmpty()) last = null;
        return name;
    }

    public static String WhoIsNext(String[] names, int n)
    {
        // Your code is here...

        for(int i = 0; i < names.length; i++) enqueue(names[i]);

        for(int i = 0; i < n; i++)
        {
            String name = dequeue();
            enqueue(name);
            enqueue(name);
        }

        return last.name;
    }
}

现在的问题是，当我运行它时，程序启动良好，给出了正确的答案，但在第 12 次测试时它开始给我一个错误的答案。例如，给方法 WhoIsNext 一个 n = 3667 我在具有相同代码的 eclipse 中的答案是 = Penny，这是正确的答案，但在编码网页中它给了我 = Leonard 所以我的假设是内存开始结束所以程序在 12/13 测试后开始给出错误答案。我怎样才能改进我的代码以通过所有测试？

这是测试。

public class ListTests {
    @Test
    public void test1() {
      String[] names = new String[] { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
      int n = 1;  
      assertEquals("Sheldon", new Line().WhoIsNext(names, n));
    }
      @Test
    public void test2() {
      String[] names = new String[] { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
      int n = 6;  
      assertEquals("Sheldon", new Line().WhoIsNext(names, n));
    }
      @Test
    public void test3() {
      String[] names = new String[] { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
      int n = 1802;  
      assertEquals("Penny", new Line().WhoIsNext(names, n));
    }
      @Test
    public void test4() {
      String[] names = new String[] { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
      int n =  2;  
      assertEquals("Leonard", new Line().WhoIsNext(names, n));
    }
     @Test
    public void test6() {
      String[] names = new String[] { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
      int n = 10;  
      assertEquals("Penny", new Line().WhoIsNext(names, n));
    }
     @Test
    public void test7() {
      String[] names = new String[] { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
      int n = 534;  
      assertEquals("Rajesh", new Line().WhoIsNext(names, n));
    }
     @Test
    public void test8() {
      String[] names = new String[] { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
      int n = 5033;  
      assertEquals("Howard", new Line().WhoIsNext(names, n));
    }
    @Test
    public void test9() {
      String[] names = new String[] { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
      int n = 10010;  
      assertEquals("Howard", new Line().WhoIsNext(names, n));
    }
     @Test
    public void test10() {
      String[] names = new String[] { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
      int n = 63;  
      assertEquals("Rajesh", new Line().WhoIsNext(names, n));
    }
     @Test
    public void test11() {
      String[] names = new String[] { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
      int n = 841;  
      assertEquals("Leonard", new Line().WhoIsNext(names, n));
    }
     @Test
    public void test12() {
      String[] names = new String[] { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
      int n = 3667;  
      assertEquals("Penny", new Line().WhoIsNext(names, n));
    }
     @Test
    public void test13() {
      String[] names = new String[] { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
      int n = 38614;  
      assertEquals("Howard", new Line().WhoIsNext(names, n));
    }
    @Test
    public void test14() {
      String[] names = new String[] { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
      int n = 1745;  
      assertEquals("Leonard", new Line().WhoIsNext(names, n));
    }
   @Test
    public void test15() {
      String[] names = new String[] { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
      int n = 8302;  
      assertEquals("Rajesh", new Line().WhoIsNext(names, n));
    }
    @Test
    public void test16() {
      String[] names = new String[] { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
      int n = 12079;  
      assertEquals("Sheldon", new Line().WhoIsNext(names, n));
    }
    @Test
    public void test17() {
      String[] names = new String[] { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
      int n = 28643950;  
      assertEquals("Leonard", new Line().WhoIsNext(names, n));
    }
    @Test
    public void test18() {
      String[] names = new String[] { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
      int n = 159222638;  
      assertEquals("Howard", new Line().WhoIsNext(names, n));
    }
   @Test
    public void test19() {
      String[] names = new String[] { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
      int n = 121580142;  
      assertEquals("Penny", new Line().WhoIsNext(names, n));
    }
   @Test
    public void test20() {
      String[] names = new String[] { "Sheldon", "Leonard", "Penny", "Rajesh", "Howard" };
      int n = 1000000000;  
      assertEquals("Penny", new Line().WhoIsNext(names, n));
    }
}

Answer 1

你不应该使用简单的算法来解决这个问题。正如您在 test20 中看到的，当 n=1000000000 时，解决问题的成本太高了。

你可以用纯数学来解决这个问题。例如，将x,y,z 分成组，如(xyz) (xxyyzz) (xxxyyyzzz) 并减少每个组的数量以获得特定的组，然后mod n(根据你找到的组)找出哪个输出应该是。