首页 > 试题广场 >

回文序列

[编程题]回文序列
  • 热度指数：23402 时间限制：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 ≤ item[i] ≤ 1000)，以空格分隔。


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

输入

4
1 1 1 3

输出

2

说明

经过第一次操作后，变为2 1 3，{2, 1, 3} 不是回文序列；
再经过一次操作后，变为3 3，{3, 3} 是回文序列；
所以共需要进行两次转换。
算法知识视频讲解
添加回答
脱缰的哈士奇～头像 脱缰的哈士奇～

使用双端队列deque数据结构进行求解。双端队列deque数据结构支持高效地首尾两端元素的插入和删除。(提交运行时间小于1ms)

本题思路为：判断队首和队尾元素。若二者相等，则将这两个元素都弹出队列，将队列规模缩小2个，再对该问题进行判断；若二者不相等，则选择其中较小的一个，将该元素和与其相邻的元素都弹出队列，再将其和插入队列，从而将队列规模缩小1个，再对该问题进行判断。 

#include <iostream>
#include <deque>
using  namespace std;

int main() {
    int length;
    deque<int> datas;
    int count = 0;
    int temp;
    int start;
    int end;
    int add;
    while (cin >> length) {
        count = 0;
        datas.clear(); 

        for (int i = 0; i<length; i++) {
            cin >> temp;
            datas.push_back(temp);
        }

        while (datas.size() > 1) {

            start = datas.front();
            end = datas.back();
            if (start == end) {
                //若相等，删除队首和队末元素
                datas.pop_back();
                datas.pop_front();
            }
            else {
                //不相等
                add = 0;
                count++;
                if (start <= end) {
                    add += start;
                    datas.pop_front();
                    add += datas.front();
                    datas.pop_front();
                    datas.push_front(add);
                }
                else {
                    add += end;
                    datas.pop_back();
                    add += datas.back();
                    datas.pop_back();
                    datas.push_back(add);
                }

            }
        }
        cout << count << endl;
    }
    return 0;
}
编辑于 2017-03-31 11:46:39 回复(21)
Python
basicworld头像 basicworld 
#不用递归！－－人生苦短我用python
#首尾指针跟踪
#两个数不相等就进行加法：小的数加上相邻的值
n = int(raw_input().strip())
item = [int(x) for x in raw_input().strip().split()]

def huiwen(item, head, tail):
    times=0
    left = item[head]
    right = item[tail]
    while (head<tail):

        if left<right:
            head+=1
            left+=item[head]
            times+=1
            continue
        elif left>right:
            tail-=1
            right+=item[tail]
            times+=1
            continue
        elif left==right:
            head+=1
            tail-=1
            left = item[head]
            right = item[tail]

    return times


print huiwen(item,0,n-1)

编辑于 2016-09-24 12:08:52 回复(13)
Java
easollx头像 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)
bupt渣硕头像 bupt渣硕 
//利用递归，两端不论怎样都要相等或者最终合成为同一个数
#include <iostream>
using namespace std;
int comb(int* nums, int head, int tail) {
    int times = 0;
    int left = nums[head], right = nums[tail];
    while (head < tail && left != right) {
        if (left < right) left += nums[++head], times++;
        else right += nums[--tail], times++;
    }
    if (head >= tail) return times;
    else return times += comb(nums, ++head, --tail);
}
int main(){
    int n = 0;
    int nums[50] = {0};
    cin >> n;
    for( int i = 0; i < n; i++)
        cin >> nums[i];
    cout << comb(nums, 0, n-1);
}

编辑于 2016-09-12 22:40:56 回复(16)
Alex-大伟头像 Alex-大伟 
package com.suda.alex;

import java.util.ArrayList;
import java.util.Scanner;

public class Test1 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			int n = scanner.nextInt();
			int[] item = new int[n];
			for(int i=0;i<n;i++){
				item[i] = scanner.nextInt();
			}
			System.out.println(leastTimeToHuiwen(n, item));
		}
	}
	public static int leastTimeToHuiwen(int n, int[] item) {
		//比较第一个和最后一个数，如果第一个大，则前两个相加替换原来位置。
		//如果最后一个数大，则最后两个相加替换原来位置。
		//如果首尾元素相等，则删除首尾元素。
		int leastTime = 0;
		ArrayList<Integer> list = new ArrayList<Integer>();
		for(int i=0;i<n;i++){
			list.add(item[i]);
		}
		while(list.size() > 1){
			if(list.get(0) < list.get(list.size() - 1)){
				int a = list.get(0);
				int b = list.get(1);
				list.set(0, a+b);
				list.remove(1);
				leastTime++;
			}
			else if(list.get(0) > list.get(list.size() - 1)){
				int a = list.get(list.size() - 1);
				int b = list.get(list.size() - 2);
				list.set(list.size() - 2, a+b);
				list.remove(list.size() - 1);
				leastTime++;
			}
			else{
				list.remove(0);
				list.remove(list.size() - 1);
			}
		}
		return leastTime;
	}
	
}


发表于 2016-09-26 19:57:06 回复(2)
anas头像 anas 

	/*思路：分别使用两个指针，从两头向中间靠拢。如果两个指针处的数值相等，两个指针同时向中间移动。





	如果left指针处的值较小，让left指针处的数值不断地与后面的元素相加，直至>=right处的数值，然后将得到的和存放在left指针处，在加的过程中，加的次数就合并的次数。





	如果right指针处的数值较小，让right不断地与前面的数值相加，直至和>=left处的数值，然后将和保存在right指针处，在加的过程中，加的次数就是合并的次数。





	#include<iostream>





	#include<vector>





	using namespace std;





	intmain(){





	    intn;





	    while(cin>>n){





	        if(n<=0)





	            break;





	        vector<int> member(n);





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





	            cin>>member[i];





	        }





	        intleft=0,right=n-1;





	        intans=0;





	        while(left<right){





	            if(member[left]<member[right]){





	                intsum=member[left];





	                while(sum<member[right]){





	                    sum+=member[++left];





	                    ans++;





	                }





	                member[left]=sum;





	            }





	            elseif(member[left]>member[right]){





	                intsum=member[right];





	                while(sum<member[left]){





	                    sum+=member[--right];





	                    ans++;





	                }





	                member[right]=sum;





	            }





	            else{





	             





	                left++;





	                right--;





	            }





	             





	        }





	        cout<<ans<<endl;





	    }





	    return0;





	}

发表于 2016-09-14 08:52:15 回复(2)
木然猫猫头像 木然猫猫
比较首尾，
1、若相等，则将首尾去除
2、若不等，则将较小端相邻两个元素去除，并插入其和，操作次数+1
重复以上操作直至长度<=1 
input()
arr = list(map(int, input().split()))
cnt = 0
while len(arr) > 1:
    if arr[0] == arr[-1]:
        arr.pop(0)
        arr.pop(-1)
    else:
        if arr[0] < arr[-1]:
            n = arr.pop(0) + arr.pop(0)
            arr.insert(0, n)
        else:
            n = arr.pop(-1) + arr.pop(-1)
            arr.append(n)
        cnt += 1
print(cnt)

运行时间：29ms

占用内存：3564k


发表于 2018-08-30 17:18:17 回复(3)
DarcyX头像 DarcyX 
#include <iostream>
#include <vector>
using namespace std;

int fun(vector<int> arr) {
	int rslt = 0;
	int n = arr.size();
	if (n <= 1) {
		return 0;
	}
	int l = 0;
	int r = n - 1;
	int ln = arr[l];
	int rn = arr[r];
	while (l < r) {
		if (ln < rn) {
			ln += arr[++l];
			++rslt;
		}
		else if (ln > rn) {
			rn += arr[--r];
			++rslt;
		}
		else {
			++l;
			--r;
			ln = arr[l];
			rn = arr[r];
		}

	}

	return rslt;
}

int main() {
	int n;
	while (cin >> n) {
		vector<int> arr(n);
		for (int i = 0; i < n; ++i)
			cin >> arr[i];
		cout << fun(arr);
	}

	return 0;
}


发表于 2016-09-13 11:43:50 回复(1)
C/C++
Aran-lq头像 Aran-lq 
#include<vector>
#include<iostream>
using namespace std;

int main(){  int n, cnt;  int* left;  int* right;  int palin[50] = {0};  while(cin >> n){  cnt = 0;  for(int i=0; i<n; i++)  cin >> palin[i];  left = &palin[0];  right = &palin[n-1];  while(left <= right){  if(*left == *right){  left++;  right--;  continue;  }  else if(*left > *right){  *(right-1) += *right;  right --;  }else{  *(left+1) += *left;  left ++;  }  cnt++;  }  cout << cnt << endl;  }
}

编辑于 2018-03-17 00:57:59 回复(0)
元气の悟空头像 元气の悟空 
#include<stdio.h>
int main(){
    int n,i,a[60],l,r,res=0;
    for(scanf("%d",&n),i=0;i<n;i++) scanf("%d",a+i);
    for(l=0,r=n-1;l<r;)
        if(a[l]==a[r]) l++,r--;
        else{
            res++;
            a[l]<a[r]?a[l+++1]+=a[l]:a[r---1]+=a[r];
        }
    printf("%d\n",res);
}//已AC，挑战最短代码

发表于 2017-09-22 14:49:27 回复(2)
JavaScript
星云锁链头像 星云锁链 
function test(arr){
	var len = arr.length ;
	var start=0 ; end = len - 1;
	while(start > end && arr[start] == arr[end]){
		start ++ ;
		end -- ;
	}
	var rest = arr.splice(start, end -start +1) ; // 去除两端已经符合回文条件的元素

	start = 0 ;
	end = rest.length -1;  
	var count = 0 ; // 计数
	while (rest.length >=2 && start < end) {
		if(rest[start] < rest[end]){   // 首部数字较小则合并首部
			var tmp = rest.shift() + rest.shift() ;
			rest.unshift(tmp) ;
			count ++ ;
		}else if(rest[start] > rest[end]){ // 尾部数字较小则合并尾部 var tmp = rest.pop() + rest.pop() ;
			rest.push(tmp)
			count ++ ;
		}else{ // 符合条件的跳过 start ++ ;
			end -- ;
		}
	}

	return count;
}

编辑于 2016-10-15 12:10:34 回复(5)
静水云深头像 静水云深 
//参考java主要算法

#include <stdio.h>
int isHuiWen(int *item, int n){  //用于统计相加次数，为处理主要算法
    int left=0;
    int right=n-1;
    int num=0;
    while(left<right){
        if(item[left]<item[right]){
            item[left+1]+=item[left];
            left++;
            num++;
        }
        else if (item[left]>item[right]){
            item[right-1]+=item[right];
            right--;
            num++;
        }
        else {
            left++;
            right--;
        }          
    }
    return num;
}
int main(){
    int n;
    int item[50];
    int num=0;
    while(scanf("%d",&n) != EOF){
   		 for(int i=0;i<n;i++){
        	scanf("%d",&item[i]);
    	 }     
    	int num=isHuiWen(item,n);    
    	printf("%d",num);
    }
}

编辑于 2016-09-24 11:51:13 回复(1)
Java
pein531头像 pein531

双指针

从两端向中间合并，给定head=arr[0]，tail=arr[n-1]
  1. 如果head<tail，head就累加上下一个位置的元素，并往右移动左指针。相当于合并了两个相邻元素arr[left]和arr[left++]，并删掉了arr[left]。
  2. 如果tail>head，tail就累加上上一个位置的元素，并向左移动右指针。相当于合并了两个相邻元素arr[right]和arr[right-1]，并删掉了arr[right]。
  3. 如果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)
WalkingCoder头像 WalkingCoder 
public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        LinkedList<Integer> list = new LinkedList<Integer>();
        for(int i=0;i<n;i++){
            list.add(scanner.nextInt());
        }
        int count = 0;
        while (list.size()>1){
            Integer first = list.getFirst();
            Integer last = list.getLast();
            if(first.equals(last)){
                list.removeFirst();
                list.removeLast();
                continue;
            }
            count ++;
            if(first>last) list.addLast(list.removeLast()+list.removeLast());
            else list.addFirst(list.removeFirst()+list.removeFirst());
        }
        System.out.println(count);
    }
编辑于 2018-10-10 18:16:33 回复(0)
2019眷顾我头像 2019眷顾我 
#include <iostream>
#include <vector>
using namespace std;
int main(){
    int n,temp;
    vector<int> v;
    cin>>n;
    int res=0;
    for(int i=0;i<n;i++){
        cin>>temp;
        v.push_back(temp);
    }
    int left=0,right=n-1;
    int lv=v[left],rv=v[right];
    while(left<right){
        if(lv==rv){
            left++;
            right--;
            lv=v[left],rv=v[right];
        }else if(lv<rv){
            while(left<right&&lv<rv){
                left++;
                lv=lv+v[left];
                res+=1;

            }
        }else if(lv>rv){
            while(left<right&&lv>rv){
                right--;
                rv=rv+v[right];
                res+=1;

            }
        }
    }
    cout<<res<<endl;
    return 0;
}
发表于 2018-09-25 10:55:15 回复(0)
Mr.Ghost头像 Mr.Ghost 
#include <stdio.h>

int main()
{
    int num;
    int cnt = 0;
    scanf("%d", &num);
    int a[num];
    for (int i = 0; i < num; i++)
    {
        scanf("%d", &a[i]);
    }
    
    for (int i = 0, j = num - 1; i < j; ++i, --j)
    {
        if (a[i] == a[j])
        {
            continue;
        }
        else 
        {
            if (a[i] < a[j])
            {
                a[i + 1] += a[i];
                cnt++;
                j++;
            }
            else 
            {
                a[j - 1] += a[j];
                cnt++;
                i--;
            }
        }
    }
    printf("%d\n", cnt);
}

发表于 2018-09-22 19:22:02 回复(0)
LSur头像 LSur 
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();
        }
        in.close();
        //分治递归的思想：两端的数最终必须相等或合成为一个数
        int count = 0,head=0,tail=n-1;
        while(head<tail){
            if(arr[head]<arr[tail]){
                arr[head+1] += arr[head];
                head++;
                count++;
            }else if(arr[head]>arr[tail]){
                arr[tail-1] += arr[tail];
                tail--;
                count++;
            }else{
                head++;
                tail--;
            }
        }
        System.out.println(count);
    }
}

发表于 2018-04-09 22:01:26 回复(0)
Bug！不存在的头像 Bug！不存在的
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
    while (in.hasNext()) {
    int N=in.nextInt();
    int[] arr=new int[N];
    for (int i = 0; i < N; i++) {
        arr[i]=in.nextInt();
    }
    int len=arr.length;
    int times=0;
    int i=0;
    int j=len-1;
   while(i<j) {
        if(arr[i]>arr[j])
        {
            arr[j-1]+=arr[j];
            j--;
            times++;
        }
            else if(arr[i]<arr[j]){
                arr[i+1]=arr[i+1]+arr[i];
                i++;
                times++;
            }
            else
            {
                i++;
                j--;
            }
    }
    System.out.println(times);
    }
}
}
发表于 2018-04-02 16:05:37 回复(0)
大花喵星人头像 大花喵星人 
int palindromeSequence(int n, int* item){
    int count = 0;
    for(int i=0,j=n-1; (i<n)&&(j>=0)&&(j-i>=1); ) {
        if(item[i]==item[j]){
            i+=1;j-=1;continue;
        }
        else if(item[i]!=item[j]) {
            int a = item[i]>item[j]?1:0;
            switch (a) {
                case 1:
                    item[j-1]=item[j-1]+item[j];
                    count+=1;
                    if(item[i]==item[j-1]) {
                        i+=1;j-=2;break;
                    }
                    else if(item[i]!=item[j-1]) {
                        j-=1;break;
                    }
                    break;
                case 0:
                    item[i+1]=item[i]+item[i+1];
                    count+=1;
                    if(item[i+1]==item[j]) {
                        i+=2;j-=1;break;
                    }
                    else if(item[i+1]!=item[j]) {
                        i+=1;break;
                    }
                    break;
            }
        }
    }
    return count;
}

发表于 2018-03-17 01:46:35 回复(0)
C/C++
asdddsa头像 asdddsa

题目分析：
操作：对相邻两数加和放入之前位置

无论如何都会得到回文序列（1个数时）
所以从两头向中间遍历，相等即省一步操作，不等就小的一端与相邻数求和 

#include <iostream>
#include<cstdio>
using namespace std;

int main(){
    int n,a[60],l=0,r=0,res=0;
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",a+i);
    for(l=0,r=n-1;l<r;)
        if(a[l]==a[r]) l++,r--;
        else{
            res++;
            if(a[l]<a[r]){
                a[l+1]+=a[l];
                l++;
            }
            else{
                a[r-1]+=a[r];
                r--;
            }
        }
    printf("%d\n",res);
}
编辑于 2018-03-15 15:33:42 回复(0)
提交观点

问题信息

贪心 模拟
来自：网易2017秋招编程题集合
难度：
170条回答 36179浏览

热门推荐

通过挑战的用户

查看代码

相关试题

回文序列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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