无需重新创建阵列的阵列游戏解决方案

Question

我试图为一个问题语句创建一个程序，这是一个数组游戏，其中两个人为给定的数组玩一个游戏，人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;
}
}

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));
}

Answer 2

还有另一种解决方案使用动态编程并从反向工作。开始反向玩游戏。因此，在这种情况下，元素从末端移除。实际上，您不必删除元素，只需维护新开始和结束的索引即可。试着测试这个。

private static int[] method2(int[] arr)
{
boolean evenSize = arr.length % 2 == 0;
Score score = new Score(evenSize ? 1 : 0);
int start = 0;
int end = arr.length;
while (start < end)
{
if (start + 1 == end)
{
score.addPoints(arr[start]);
start++;
}
else
{
if (arr[start] < arr[end - 1])
{
score.addPoints(arr[start]);
start++;
score.addPoints(arr[end - 1]);
end--;
}
else
{
score.addPoints(arr[end - 1]);
end--;
score.addPoints(arr[start]);
start++;
}
}
}
return score.score;
}
private static class Score
{
int[] score = new int[2];
int turn;
Score(int turn)
{
this.turn = turn;
}
void addPoints(int point)
{
score[turn] += point;
turn = (turn + 1) % 2;
}
}