首页 > 试题广场 >

回文序列

[编程题]回文序列
  • 热度指数：51 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解 
如果一个数字序列逆置之后跟原序列是一样的，称这样的数字序列为回文序列。例如：
{1, 2, 1}, {16, 82, 82, 16} , {113} 是回文序列, {1, 2, 2}, {16, 82, 82, 61} ,{113, 3, 11} 不是回文序列。

现在给出一个数字序列，允许使用一种转换操作：
选择任意两个相邻的数，然后从序列移除这两个数，并用这两个数字的和插入到这两个数之前的位置，对于所给序列要求出最少需要多少次操作可以将其变成回文序列？


输入描述:
输入为两行，第一行为序列长度n (1 ≤ n ≤ 50) ，第二行为序列中n个整数item[i](1 ≤ item[i]≤ 1000)，以空格分隔。


输出描述:
输出一个数，表示最少需要的转换次数
示例1

输入

6
1  1  1  1  1  5

输出

4

说明

输入为两行
算法知识视频讲解
添加回答
菲尼克斯弗兰克头像 菲尼克斯弗兰克 
import java.util.Scanner;
// 双指针贪心
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        int cnt = 0;
        int l = 0, r = arr.length-1;
        while (l < r) {
            if (arr[l] == arr[r]) {
                l++;
                r--;
            } else if (arr[l] < arr[r]) { // 优先合并左边
                arr[l+1] += arr[l];
                l++;
                cnt++;
            } else { // 优先合并右边
                arr[r-1] += arr[r];
                r--;
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}
发表于 2022-07-22 16:58:08 回复(0)
werdenwissen头像 werdenwissen
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        int n=input.nextInt();
        int[] a=new int[n];
        int res=0;
        for(int i=0;i<n;i++) a[i]=input.nextInt();
        int i=0,j=n-1;
        while(i<j){
            if(a[i]==a[j]){
                i++;
                j--;
            }
            else if(a[i]<a[j]){
                a[i+1]+=a[i];
                i++;
                res++;
            }
            else{
                a[j-1]+=a[j];
                j--;
                res++;
            }
        }
        System.out.println(res);
    }
}
发表于 2021-04-20 19:06:32 回复(0)
提交观点

问题信息

阅文集团 测试开发工程师 2021
来自：2021届阅文测试开发...
上传者：小小
难度：
2条回答 1864浏览

热门推荐

通过挑战的用户

相关试题

回文序列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号