java - 如何反转并破坏数组以形成新的最大化数组？

Question

问题详细信息:这个特定的编码问题希望我这样做:

• 接受数组中的几个数字，然后对其自身执行以下操作(假设数组为 A)以形成一个新的数组 X，使其元素最大化(下面的示例)。

这些操作将一直执行到数组 A 为空为止，此时我们可以选择只执行以下操作之一。

• 1:删除数组A的最后一个数字，并将其添加到数组X中
• 2:删除数组A的最后2个数字，并将它们的乘积添加到数组X
• 3:反转数组A并删除最后一个元素并将其添加到数组X
• 4:反转数组 A 并将最后 2 个元素的乘积添加到数组 X 中，同时从数组 A 中删除这 2 个元素。

例如，如果设置 A = [1, 4, 2, 3, 5]，则在操作 [2, 3, 2] 后设置 X = [15, 1, 8]，总和为 24，这是最大值从每个可能的操作组合中求和，以从集合 A 创建集合 X。

Question source

我的问题:我为此编写了代码，但它仅适用于某些测试用例，并且大多数情况下不适用于其他输入，从某种意义上说，它输出了错误的答案，但是我无法注意我的逻辑错误在哪里，所以请指出我的错误/修改我的代码。

我的方法:首先，我执行了 4 个操作中的每一个操作(删除或反转部分除外)，并选择产生最大元素的操作，然后继续执行完整操作(删除或反转部分)反转集合 A 并形成集合 X)，因此可以最大化该集合 X。我继续这样做，直到 A 组被清空为止。

我的基本代码片段如下:

public class Firstly {
 public static ArrayList A = new ArrayList();//declared set A
  public static ArrayList X = new ArrayList();//declared set X

public static void main(String[] args) {

    int s=0;
    Scanner sc = new Scanner(System.in);
  int u=sc.nextInt();//accepted the size of set A from the user
  for(int i=0;i<u;i++)
      A.add(sc.nextInt());//accepted 'u' numbers in set A from the user

/*below i define and use a method 'execute' which performs one of 
 the 4 operations on set A as well as makes set X */

while(!A.isEmpty())//'execute' is implemented until set A is emptied
      execute(maxi(A),X,A);

for (Iterator it = X.iterator(); it.hasNext();) 
    s+=  (int) it.next();//adding all the set X elements
System.out.println(s);
}

/*maxi method below returns the number that is the largest possible among 
  the 4 operations that can be performed on set A*/ 


private static int maxi(ArrayList A) {
      ArrayList Y = new ArrayList();//declared a set Y

      Y.add(A.get(A.size()-1));//adds the product of 1st operation

      if(A.size()>1){//adds the product of 2nd operation
      int k= (int) A.get(A.size()-1);
      int h= (int) A.get(A.size()-2);
          Y.add(k*h);
      }

  Y.add(A.get(0));//adds the product of 3rd operation

      if(A.size()>1){//adds the product of 4th operation
        int kt= (int) A.get(0);
      int ht=(int) A.get(1);
      Y.add(kt*ht);
      }
      return Y.indexOf(Collections.max(Y));/*returns the index of the 
    largest of the 4 elements*/
}

 /*depending on the value(index) the 'maxi' method returns, 'execute' 
  method performs the requisite operation on set A as well as on set X*/


private static void execute(int maxi, ArrayList X, ArrayList A){
    switch(maxi){
        case 0://if the largest number is produced by 1st operation
            X.add(A.remove(A.size()-1));
            break;
        case 1://if the largest number is produced by 2nd operation
           int k= (int) A.remove(A.size()-1);
      int h=(int) A.remove(A.size()-1);
      X.add(h*k);
      break;
        case 2://if the largest number is produced by 3rd operation
            X.add(A.remove(0));
             Collections.reverse(A);
             break;
        default ://if the largest number is produced by 4th operation
              int kt=(int) A.remove(0);
      int ht=(int) A.remove(0);
            X.add(ht*kt);
             Collections.reverse(A);                
    }
  }  
}

谢谢。

Answer 1

您的代码是正确的，但您的示例不正确。

例如，如果设置 A = [1, 4, 2, 3, 5]，则在操作 [2, 3, 2] 后设置 X = [15, 1, 8]，总和为 24，这是最大值从每个可能的操作组合中求和，以从集合 A 创建集合 X。

Array A: 1 4 2 3 5  
Op: 2 
Array X: 15  
Array A: 1 4 2  
Op: 2 
Array X: 15 8  
Array A: 1  
Op: 1 
Array X: 15 8 1  
Array A:  
Result:24

Your problem is on the second step: [1 4 2] why would you pick the op 1? if the op 2 is higher on the result value. If this is not the idea then you have to change your "maxi" function to pick the op that you want.

另一个例子:

对于此入口:8 8 1 4 1 2 0 9

我得到了正确的预期结果:64 9 4 2 0

使用此操作顺序:4 3 4 2 1

Array A: 8 8 1 4 1 2 0 9  
Op: 4 
Array X: 64  
Array A: 9 0 2 1 4 1  
Op: 3 
Array X: 64 9  
Array A: 1 4 1 2 0  
Op: 4 
Array X: 64 9 4  
Array A: 0 2 1  
Op: 2 
Array X: 64 9 4 2  
Array A: 0  
Op: 1 
Array X: 64 9 4 2 0  
Array A:  
Result:79

我的测试代码:我更改了一些内容以适应正确的环境。 使用JDK1.8

import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Firstly {

    private static void printArrayA(List<Integer> A){
        // PRINT THE ARRAY
        A.forEach(a -> System.out.print(a + " "));
        System.out.println(" ");
    };

    public static void main(String[] args) {

        List<Integer> A = new LinkedList<Integer>();// declared set A
        List<Integer> X = new LinkedList<Integer>();// declared set X

        int s = 0;
        Scanner sc = new Scanner(System.in);
        int u = sc.nextInt();// accepted the size of set A from the user
        for (int i = 0; i < u; i++)
            A.add(sc.nextInt());// accepted 'u' numbers in set A from the user

        System.out.print("Array A: ");
        printArrayA(A);

        /*
         * below i define and use a method 'execute' which performs one of the 4
         * operations on set A as well as makes set X
         */

        while (!A.isEmpty())
            // 'execute' is implemented until set A is emptied
            execute(maxi(A), X, A);

        for (Iterator it = X.iterator(); it.hasNext();)
            s += (Integer) it.next();// adding all the set X elements
        System.out.println("Result:" + s);
    }

    /*
     * maxi method below returns the number that is the largest possible among the 4
     * operations that can be performed on set A
     */

    private static int maxi(List<Integer> A) {
        List<Integer> Y = new LinkedList<Integer>();// declared a set Y

        Y.add(A.get(A.size() - 1));// adds the product of 1st operation

        if (A.size() > 1) {// adds the product of 2nd operation
            int k = (Integer) A.get(A.size() - 1);
            int h = (Integer) A.get(A.size() - 2);
            Y.add(k * h);
        }

        Y.add(A.get(0));// adds the product of 3rd operation

        if (A.size() > 1) {// adds the product of 4th operation
            int kt = (Integer) A.get(0);
            int ht = (Integer) A.get(1);
            Y.add(kt * ht);
        }
        int index = Y.indexOf(Collections.max(Y))+1;
        System.out.print("Op: "+index);
        return Y.indexOf(Collections.max(Y));/*
                                                 * returns the index of the largest of the 4 elements
                                                 */
    }

    /*
     * depending on the value(index) the 'maxi' method returns, 'execute' method
     * performs the requisite operation on set A as well as on set X
     */

    private static void execute(int maxi, List<Integer> X, List<Integer> A) {
        System.out.println(" ");
        switch (maxi) {
        case 0:// if the largest number is produced by 1st operation
            X.add(A.remove(A.size() - 1));
            break;
        case 1:// if the largest number is produced by 2nd operation
            int k = (Integer) A.remove(A.size() - 1);
            int h = (Integer) A.remove(A.size() - 1);
            X.add(h * k);
            break;
        case 2:// if the largest number is produced by 3rd operation
            X.add(A.remove(0));
            Collections.reverse(A);
            break;
        default:// if the largest number is produced by 4th operation
            int kt = (Integer) A.remove(0);
            int ht = (Integer) A.remove(0);
            X.add(ht * kt);
            Collections.reverse(A);
        }
        System.out.print("Array X: ");
        printArrayA(X);
        System.out.print("Array A: ");
        printArrayA(A);
    }
}