首页 > 试题广场 >

回文序列

[编程题]回文序列

热度指数：23527 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

输入描述:

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

输出描述:

输出一个数，表示最少需要的转换次数

示例1

输入

4
1 1 1 3

输出

说明

经过第一次操作后，变为2 1 3，{2, 1, 3} 不是回文序列；
再经过一次操作后，变为3 3，{3, 3} 是回文序列；
所以共需要进行两次转换。

算法知识视频讲解

查看答案及解析

Java

pein531

双指针

从两端向中间合并，给定head=arr[0]，tail=arr[n-1]

如果head<tail，head就累加上下一个位置的元素，并往右移动左指针。相当于合并了两个相邻元素arr[left]和arr[left++]，并删掉了arr[left]。
如果tail>head，tail就累加上上一个位置的元素，并向左移动右指针。相当于合并了两个相邻元素arr[right]和arr[right-1]，并删掉了arr[right]。
如果head=tail，left++，right--两个指针同时往中间靠，head=arr[left]，tail=arr[right]。相当于此时已经搞定了回文序列的两端（两端的数字已经相等），接下来如法炮制去搞定更内侧的两端。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strs = br.readLine().split(" ");
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(strs[i]);
        }
        int left = 0, right = n - 1, count = 0;
        int head = arr[left], tail = arr[right];
        while(left < right){
            if(head < tail){
                head += arr[++left];
                count++;
            }else if(head > tail){
                tail += arr[--right];
                count++;
            }else{
                left ++;
                head = arr[left];
                right --;
                tail = arr[right];
            }
        }
        System.out.println(count);
    }
}

复杂度分析

双指针往中间靠，不回退，直至相遇或错过，因此时间复杂度O(n)；仅用了有限的几个变量，额外空间复杂度O(1)。

编辑于 2022-01-08 13:53:40 回复(0)

Java

凌晨两点敲代码

思路：双指针，一个从前向后遍历，一个从后向前遍历，如果相等继续遍历，如果前边的小就求和，如果后边的小就求和，一直循环直到指针相遇。

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for(int i=0;i<n;i++){
            a[i] = sc.nextInt();
        }
        int res = power(a);
        System.out.print(res);
    }
    static int power(int[] a){
        int start = 0;
        int end = a.length-1;
        int res = 0;
        while(start<end){
            if(a[start]==a[end]){
                start++;
                end--;
            }
            if(a[start]<a[end] ){
                a[start+1] = a[start]+a[start+1];
                start++;
                res++;
            }
            if(a[start]>a[end] ){
                a[end-1] = a[end]+a[end-1];
                end--;
                res++;
            }
        }
        return res;
    }
}

发表于 2021-09-04 23:54:11 回复(0)

Java

东东的好

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
    // 吐槽下牛客题目，上面的格式真的无语
    // 解题思路，从两边开始计算，如果左边等于右边就删除，不等于就进行操作，由于要在两边进行数据的删除就需要使用到的是双向队列,
直接模拟上面题目要求，如果两边相等就删除，如果左边大就操作右边，反之。每做一次就ans++
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            deque.add(sc.nextInt());
        }
        int start = 0;
        int end = deque.size() - 1;
        int ans = 0;
        while(start < end) {
            int l = deque.getFirst();
            int r = deque.getLast();
            if (l == r) {
                deque.pollFirst();
                deque.pollLast();
                start = 0;
                end = deque.size() - 1;
                if (deque.size() != 0) {
                    l = deque.getFirst();
                    r = deque.getLast();
                }

            } else if (l > r){
                // 左边的更大 4 1 1 1 3
                while (l > r && deque.size() != 1) {
                    deque.pollLast();
                    r += deque.getLast();
                    deque.pollLast();
                    deque.addLast(r);
                    ans++;
                }
                end = deque.size() - 1;
            } else {
                // 右边的更大 3 1 1 1 4
                while (l < r && deque.size() != 1) {
                    deque.pollFirst();
                    l += deque.getFirst();
                    deque.pollFirst();
                    deque.addFirst(l);
                    ans++;
                }
                start = 0;
            }
        }
        System.out.println(ans);
    }
}

发表于 2019-03-04 18:48:45 回复(0)

Java

小青鸟

借鉴了楼上大神的双端队列思想。69ms。

import java.util.*;

public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
LinkedList<Integer> list = new LinkedList<>();
int n = scanner.nextInt();
for(int i = 0; i<n; i++){
list.add(scanner.nextInt());
}
int sum = 0;
int temp = 0;
while(list.size() > 1){
sum+=1;
if(list.getLast() > list.getFirst()){
temp += list.getFirst();
list.removeFirst();
temp += list.getFirst();
list.removeFirst();
list.addFirst(temp);
}else if(list.getLast() < list.getFirst()){
temp += list.getLast();
list.removeLast();
temp += list.getLast();
list.removeLast();
list.addLast(temp);
}else{
list.removeFirst();
list.removeLast();
sum-=1;
}
temp = 0;
}
System.out.println(sum);
}
}

发表于 2018-09-05 14:24:01 回复(0)

Java

七仔0312

递归

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int length = Integer.parseInt(br.readLine());
        String[] strings = br.readLine().split(" ");
        int[] arr = new int[length];
        for (int i = 0; i < length; i++) {
            arr[i] = Integer.parseInt(strings[i]);
        }
        System.out.println(getCount(arr,0,length-1));
    }

    public static int getCount(int[] arr, int start, int end) {
        if (end - start <= 0)
            return 0;
        if (arr[start] == arr[end])
            return getCount(arr, start+1,end-1);
        else if (arr[start] < arr[end]) {
            arr[start+1]=arr[start]+arr[start+1];
            return getCount(arr,start+1,end) + 1;
        } else {
            arr[end-1] = arr[end-1] + arr[end];
            return getCount(arr,start,end-1) + 1;
        }
    }
}

发表于 2018-03-15 11:35:23 回复(0)

Java

RefactorWorld

import java.util.Scanner;
public class Main{

public static int minTrans(int []nums){
    int count = 0;
    int l = 0, r = nums.length - 1;
    while(l<=r){
        if(nums[l] == nums[r]){
            l++;
            r--;
        }else if(nums[l] > nums[r]){
            nums[r-1] += nums[r];
            r--;
            count++;
        }else{
            nums[l+1] +=nums[l];
            l++;
            count++;
        }
    }
    return count;
}
public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    while(sc.hasNext()){
        int n = sc.nextInt();
        int [] nums = new int[n];
        for(int i = 0;i < n ; i++) nums[i] = sc.nextInt();
        System.out.println(minTrans(nums));
    }
    sc.close();
}

}

发表于 2018-01-22 14:23:29 回复(0)

Java

傻傻傻傻

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int count = in.nextInt();
            int[] array = new int[count];
            for (int i = 0; i < count; i++)
                array[i] = in.nextInt();
            int i = 0, j = array.length - 1;
            int res = 0;
            while (i < j) {
                if (array[i] == array[j]) {
                    i++; j--;
                } else if (array[i] < array[j]) {
                    i++;
                    array[i] += array[i-1];
                    res++;
                } else {
                    j--;
                    array[j] += array[j+1];
                    res++;
                }
            }
            System.out.println(res);
        }
    }
}

发表于 2017-12-25 21:29:15 回复(0)

Java

选牌

//从最左边和最右边开始如果v[left]=v[right]

//则比较v[left+1]和right[right-1]

//如果v[left]>v[right]

//则比较v[right]+v[right-1]和v[left],

//如果v[left]<v[right]

//则比较v[left]+v[left+1]和v[right],如此循环下去，知道left>=right

import java.util.ArrayList;

import java.util.Scanner;

public class Main {

public static void main(String args[]){

Scanner in = new Scanner(System.in);

int n = in.nextInt();

ArrayList<Integer> aList = new ArrayList<Integer>();

for(int i = 0;i<n;i++){

aList.add(in.nextInt());

}

int left=0;

int right=n-1;

int count=0;

int v1;

int v2;

int v3;

int v4;

while(left<right){

v1 = aList.get(left);

v2 = aList.get(right);

if(v1==v2){

left++;

right--;

}else if(v1>v2){

right--;

v3 = aList.remove(right);

; aList.add(right, v3+v2);

count++;

}else if(v1<v2){

left++;

v4= aList.remove(left);

aList.add(left,v4+v1);

count++;

}

System.out.println(count);;

}

发表于 2017-08-18 16:03:03 回复(0)

Java

马卡维奇

    // 竟然神奇的通过了
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int total = scanner.nextInt();
        int[] array = new int[ total ];
        for (int i = 0; i < total; i++) {
            array[ i ] = scanner.nextInt();
        }
        System.out.println(transSeq(array, total - 1));
    }

    public static int transSeq(int[] nums, int high) {
        int left = nums[ 0 ], right = nums[ high ];
        int i = 1, j = len - 1, count = 0;
        while ( i <= j ) {
            if (left < right) {
                left += nums[ i++ ];
                ++count;
            } else if (left > right) {
                right += nums[ j-- ];
                ++count;
            } else {
                left = nums[ i++ ];
                right = nums[ j-- ];
            }
        }
        return left == right ? count : count + 1;
    }

发表于 2017-08-14 21:40:18 回复(1)

Java

浩亮亮亮亮

分享一下思路：

两个指针，一个从头开始，朝右移动；一个从尾开始，朝左移动。如果两个指针当前所指的两个数相同，同时移动1；如果左指针的数小，将左指针的数与后一个数相加，并用左指针指向这个新数；如果右指针的数大，将右指针的数与前一个数相加，并用右指针指向这个新数。代码能够AC，但是如果原序列无法调整为回文数列，将产生错误的结果，但是不影响这道题的评分。

import java.util.Scanner;

/**
 * Created by chl on 2017/8/12.
 */
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        while (scanner.hasNextLine()){
            int number = scanner.nextInt();
            int[] numbers = new int[number];
            for (int i = 0; i < number; i++) {
                numbers[i] = scanner.nextInt();
            }

            System.out.println(leastAdjustCount(numbers));
        }
    }

    private static int leastAdjustCount(int[] numbers) {
        int left = 0;
        int right = numbers.length - 1;
        int adjustCount = 0;
        while (left < right){
            if (numbers[left] == numbers[right]){
                left++;
                right--;
            } else if (numbers[left] < numbers[right]){
                numbers[left + 1] = numbers[left] + numbers[left + 1];
                adjustCount++;
                left++;
            } else {
                numbers[right - 1] = numbers[right] + numbers[right - 1];
                right--;
                adjustCount++;
            }
        }
        return adjustCount;
    }
}

发表于 2017-08-12 14:00:40 回复(0)

Java

Jungggle

import java.util.LinkedList;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

try (Scanner scanner = new Scanner(System.in)) {

while (scanner.hasNext()) {

LinkedList<Integer> deque = new LinkedList<>();

int n = scanner.nextInt();

for (int i = 0; i < n; i++) {

deque.addLast(scanner.nextInt());

}

int counter = 0;

while (!deque.isEmpty()) {

if (deque.size() == 1)

break;

if (deque.getFirst().equals(deque.getLast())) {

deque.removeLast();

deque.removeFirst();

} else {

if (deque.getFirst() < deque.getLast()) {

deque.addFirst(deque.removeFirst() + deque.removeFirst());

} else {

deque.addLast(deque.removeLast() + deque.removeLast());

}

counter++;

}

System.out.println(counter);

}

发表于 2017-08-11 11:29:27 回复(0)

Java

牛客288493号

这道题思路是这样的：要得到回文字符串，两端的值必须相等或者合并，之后向中间递归或者迭代。

需注意的问题:要求中是“去除当前这两个数”。代码中是不是没有得到实现这一步时获得的数组？ 答：不需要这一步，因为仔细分析递归的过程，每一步head++或者tail--实质上都已经缩小了数组的范围，相当于删除了原来head或者tail位置附近两位的值同时将新增的值插入。


import java.util.*;
public class Main{
    public static void main(String[] arg0){
        Scanner scanner=new Scanner(System.in);
        while(scanner.hasNext()){
            int n=scanner.nextInt();
            int[] a=new int[n+5];
            //输入数组
            for(int i=0;i<n;i++){
                a[i]=scanner.nextInt();
            }
            /*
             *递归，头和尾必须相等或者合并
             */
            System.out.println(huiwen(a,0,n-1));
        }
    }

    private static int huiwen(int[] a, int head, int tail) {
        int times=0;
        int left=a[head];
        int right=a[tail];
        while(left!=right &&head<tail){
            if(left<right){
                a[++head]+=left;
left=a[head];        times++;    }
            else{
                a[--tail]+=right;
                right=a[tail];
                        times++;
            }
        }
        if(head>=tail)return times;
        else return times+=huiwen(a, ++head, --tail);
    }
}

发表于 2017-03-24 11:59:12 回复(0)

Java

小飞刀

//不需要递归，头尾比较大小，小的不断往前加，直到头尾指针相等

import java.util.Scanner;

public class Main {

public static void main(String[] args){

Scanner scanner = new Scanner(System.in);

int times = 0;

int num = scanner.nextInt();

int[] Arry = new int[num];

for (int i = 0; i < num; i++){

Arry[i] = scanner.nextInt();

}

int head = 0;

int tail = num - 1;

while(tail > head){

if(Arry[head] > Arry[tail]){

Arry[--tail] += Arry[tail + 1];

times++;

}else if(Arry[head] < Arry[tail]){

Arry[++head] += Arry[head - 1];

times++;

}else{

head++;

tail--;

}

System.out.println(times);

}

编辑于 2017-03-23 16:44:09 回复(0)

Java

小风筝0010

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//第一行为序列长度n
        //序列中的n个整数item[i]
        int [] item = new int[n];
        for (int i = 0; i < n; i ++) {
            item[i] = sc.nextInt();
        }
        sc.close();
        
        int times = 0; //转换次数
        int head = 0;
        int tail = n - 1;
        while (head < tail) {
            if (item[head] < item[tail]) {
                item[++head] += item[head - 1];
                times ++;
            } else if (item[head] > item[tail]) {
                 item[-- tail] +=  item[tail + 1];
                times ++;
            } else {
                head ++;
                tail --;
            }
        }
        System.out.println(times);
    }
}

发表于 2017-03-16 16:52:08 回复(0)

Java

lyul

import java.util.Scanner;

public class Palindromic {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            int n = scan.nextInt();
            int[] item = new int[n];
            for (int i = 0; i < n; i++) {
                item[i] = scan.nextInt();
            }
            System.out.println(count(n, item));
        }
    }
    
    public static int count(int n, int[] item) {
        int count = 0;
        int left = 0, right = n - 1;
        int head = item[left], tail = item[right];
        while (left < right) {
            if (head == tail) {
                left++;
                right--;
                head = item[left];
                tail = item[right];
            } else if (head < tail) {
                left++;
                head += item[left];
                count++;
            } else {
                right--;
                tail += item[right];
                count++;
            }
        }
        return count;
    }
}

编辑于 2017-01-18 13:51:52 回复(0)

Java

该隐的星球

import java.util.Scanner;

public class Main {  

	public static int changeHW(int n,int[] x){
	       
	       int changeNum = 0;
	       
	       int leftPos = 0;
	       int rightPos = x.length-1;
	       while(leftPos <= rightPos){
	           if(x[leftPos] < x[rightPos]){
	               x[leftPos+1]= x[leftPos]+x[leftPos+1];
	               leftPos ++;
	               changeNum ++;
	           }else if(x[leftPos]>x[rightPos]){
	               x[rightPos-1]=x[rightPos]+x[rightPos-1];
	               rightPos --;
	               changeNum ++;
	           }else{
	               leftPos ++;
	               rightPos --;
	           }
	       }	       
	       return changeNum;	       
	   }
	    
	    
	    public static void main(String[] args){
	        
	        Scanner scanner = new Scanner(System.in); 
	        while(scanner.hasNext()){
	            int n = scanner.nextInt();
	            if(n<1 || n>50){
	            	System.out.println("输入的序列长度n不符合要求");
	            	return;
	            }
	            int[] items = new int[n];
	            for(int i=0;i<n;i++){
	            	int a=scanner.nextInt();
	            	if(a<1 || a>10000){
		            	System.out.println("序列中的第"+(i+1)+"个整数不符合要求");
		            	return;
		            }else {
		            	items[i] = a;
		            }	                
	            }
	            System.out.println(changeHW(n,items));	          
	        }
	        
	    }
}

发表于 2016-11-27 14:46:02 回复(0)

Java

武岩

public class HuiWenXuLie {	
	  public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();		
		int[] a=new int[n];
		int m=a.length-1;
		for(int i=0;i<n;i++){
			a[i]=sc.nextInt();			
		}
		int sum=0,count=0;
		for(int i=0,j=m;i<j;j--){
			if(a[i]<a[j]){
				sum=a[i]+a[i+1];
				a[i]=sum;
				for(int k=i+1;k<m;k++){
					a[k]=a[k+1];
				}
				count++;
			}else if(a[i]>a[j]){
				sum=a[j]+a[j-1];
				a[j-1]=sum;
				count++;
			}
			else{
				i++;
			}
		}
		System.out.println(count);
	
	}
}

发表于 2016-09-25 17:14:12 回复(0)

Java

easollx

//模仿 bupt渣硕 大神的
import java.util.Scanner;
public class Main {
	public static void main(String[] args){		
		Scanner scanner = new Scanner(System.in);
		while(scanner.hasNext()){
			int times = 0;
			int n = scanner.nextInt();
			int[] inputArr = new int[n];
			for(int i = 0; i < n; i++){
				inputArr[i] = scanner.nextInt();
			}
			int head = 0;
			int tail = n - 1;
			while(head < tail){
				if(inputArr[head] > inputArr[tail]){
					inputArr[--tail] += inputArr[tail + 1];
					times++;
				}else if(inputArr[head] < inputArr[tail]){
					inputArr[++head] += inputArr[head - 1];
					times++;
				}else{
					head++;
					tail--;
				}
			}		
			System.out.println(times);
		}
		scanner.close();
	}
}

编辑于 2016-09-13 12:42:00 回复(13)

提交观点

问题信息

贪心模拟

来自：网易2017秋招编程题集合

难度：

20条回答 713收藏 38612浏览

通过挑战的用户

查看代码

5130

2022-10-14 16:49:15
爱交友的少年在考古

2022-09-14 10:59:05
鼠鼠我呀要失业了捏

2022-09-06 20:18:54
牛客67318...

2022-09-06 00:48:48
孤独的土拨鼠面试中

2022-09-03 14:10:21

回文序列

输入描述:

输出描述:

输入

输出

说明

双指针

复杂度分析

问题信息

热门推荐

通过挑战的用户

相关试题