java - 无需重新创建数组的数组游戏解决方案

Question

我正在尝试为一个问题陈述创建一个程序，该问题陈述是一个数组游戏，其中 2 个人正在为给定数组玩游戏，A 人首先移动，B 人轮流轮流玩。

每一回合，由于玩家执行以下操作，数组的长度减 1： 1. 如果数组的长度为奇数，则从数组中删除中间的数字。2. 如果长度是偶数，玩家可以选择删除中间两个元素中的任何一个。

被移除元素的值被添加到当前玩家的得分中。最后，由得分最高的人决定获胜者。如果最后两者得分相同，我们允许人 A 获胜，因为他是这个游戏的发明者。两名球员都发挥最佳。

我为此编写了一个代码，但在我的代码中，我实际上是在修改每个循环条件中的现有数组，这是一项繁重的操作，需要更多的内存和时间。如果输入太大，我的程序运行时间超过 2 秒。有什么方法可以优化下面的代码，我们可以避免修改/重新创建数组。

class TestClass {

    public static void main(String args[]) throws Exception {

        Scanner s = new Scanner(System.in);

        int n = s.nextInt();
        int arr[] = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = s.nextInt();

        }

        boolean aTurn = true;
        int aScore = 0, bScore = 0;
        int middle = 0;

        while (n > 0) {
            int point = 0;
            int position = 0;
            int size = arr.length;
            if (size % 2 == 0) {

                middle = size / 2;

                if (arr[middle - 1] > arr[middle]) {
                    point = arr[middle - 1];
                    position = middle - 1;
                } else {
                    point = arr[middle];
                    position = middle;
                }
            } else {
                middle = (size) / 2;
                if (middle == 0) {
                    point = arr[0];
                    position = 0;
                } else {
                    point = arr[middle];
                    position = middle;
                }

            }

            arr = removeElement(arr, position);
            n--;

            if (aTurn) {
                aScore += point;
                aTurn = false;
            } else {
                bScore += point;
                aTurn = true;
            }

        }

        if (aScore == bScore) {
            System.out.println("Person_A 0");
        } else if (aScore > bScore) {
            System.out.println("Person_A " + (aScore - bScore));
        } else {
            System.out.println("Person_B " + (bScore - aScore));
        }

    }

    public static int[] removeElement(int[] original, int element) {
        int[] n = new int[original.length - 1];
        System.arraycopy(original, 0, n, 0, element);
        System.arraycopy(original, element + 1, n, element, original.length - element - 1);
        return n;
    }

}

标签： javaarraysoptimization

Answer 1

基本上，您需要的是一个数组，它之间可以有一个孔/间隙，并且在每一步中，间隙都会增加 1。元素只能从间隙的任一端移除，而不是从任何随机位置移除。

//an array which has a gap in between and
//elements can be removed from either end of the gap.
private static final class GapArray
{
    private final int[] array;
    private int gapStart;
    private int gapLength;

    private GapArray(int[] array)
    {
        this.array = array;
        this.gapStart = array.length;
    }

    int get(int index)
    {
        checkBounds(index);
        if (index < gapStart)
        {
            return array[index];
        }
        else
        {
            return array[index + gapLength];
        }
    }

    private void checkBounds(int index)
    {
        if (index < 0 || index >= size())
        {
            throw new ArrayIndexOutOfBoundsException(index);
        }
    }
    //index is either just before start of the gap or just after end of gap.
    int remove(int index)
    {
        checkBounds(index);
        if (gapLength == 0)
        {
            gapStart = index;
            gapLength++;
            return array[gapStart];
        }
        else
        {
            if (index == gapStart - 1)
            {
                gapStart--;
                gapLength++;
                return array[gapStart];
            }
            else if (index == gapStart)
            {
                int value = array[gapStart + gapLength];
                gapLength++;
                return value;
            }
            else
            {
                throw new IllegalArgumentException("elements can be removed either end of the gap only");
            }
        }
    }

    int size()
    {
        return array.length - gapLength;
    }
}

使用此数据结构，您的代码如下所示。

int[] arr = new int[]{1, 2, 3};
//int[] arr = new int[]{1, 2, 3, 4};
//int[] arr = new int[]{1, 2, 3, 4, 5};

GapArray ca = new GapArray(arr);

boolean aTurn = true;
int aScore = 0;
int bScore = 0;

while (ca.size() > 0)
{
    int point;
    int size = ca.size();
    int middle;
    if (size % 2 == 0)
    {
        middle = size / 2;

        if (ca.get(middle - 1) > ca.get(middle))
        {
            point = ca.remove(middle - 1);
        }
        else
        {
            point = ca.remove(middle);
        }
    }
    else
    {
        point = ca.remove(size / 2);
    }
    if (aTurn)
    {
        aScore += point;
        aTurn = false;
    }
    else
    {
        bScore += point;
        aTurn = true;
    }
}
if (aScore == bScore)
{
    System.out.println("Person_A 0");
}
else if (aScore > bScore)
{
    System.out.println("Person_A " + (aScore - bScore));
}
else
{
    System.out.println("Person_B " + (bScore - aScore));
}