[编程题]回文序列

深碍√TFBOYSˉ_ 2022-09-30 13:46 149阅读 0赞

如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如：  
\{1, 2, 1\}, \{15, 78, 78, 15\} , \{112\} 是回文序列,   
\{1, 2, 2\}, \{15, 78, 87, 51\} ,\{112, 2, 11\} 不是回文序列。  
现在给出一个数字序列，允许使用一种转换操作：  
选择任意两个相邻的数，然后从序列移除这两个数，并用这两个数字的和插入到这两个数之前的位置(只插入一个和)。

现在对于所给序列要求出最少需要多少次操作可以将其变成回文序列。

思路：

要想将一个数组变成回文序列，必须保证这个数组是“中心对称”的。于是可以考虑用两个游标low和high，一个从头部，一个从尾部往中间滑动。low和high滑动的目的是使前后两部分的相邻的元素之和相等，然后将它们用一个数代替，这样就能保证中心对称。（不知道这样有没有表达清楚。。。）当low和high相遇时，回文序列生成。

import java.util.Scanner;
     
    public class Main {
     
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int[] item = new int[n];
            for(int i = 0; i < n; i++){
                item[i] = sc.nextInt();
            }
            int low = 0, high = n - 1;
            int sum_low = item[0], sum_high = item[n - 1];
            int result = 0;
            while (low < high){
                if(sum_low == sum_high){
                    low++;
                    high--;
                    sum_low = item[low];
                    sum_high = item[high];
                }else if(sum_low < sum_high){
                    low++;
                    sum_low += item[low];
                    result++;
                }else{
                    high--;
                    sum_high += item[high];
                    result++;
                }
            }
            System.out.print(result);
        }
    }