首页 > 试题广场 >

回文序列

[编程题]回文序列
  • 热度指数:23385 时间限制: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} 是回文序列;
所以共需要进行两次转换。  
#首尾指针跟踪
#两个数不相等就进行加法:小的数加上相邻的值
import sys

n=int(input())
item=list(map(int,sys.stdin.readline().strip().split()))
ans=0
head=0
tail=n-1#首尾指针
left = item[head]
right = item[tail]#首尾指针指向的数
while (head<tail):
    if left<right:#左小于右,左边的数加上他旁边的数
        head+=1
        left+=item[head]
        ans+=1
        continue
    elif left>right:#左大于右,右边的数加上它旁边的树
        tail-=1
        right+=item[tail]
        ans+=1
        continue
    else: #左等于右时,首尾指针各往中间移一位
        head+=1
        tail-=1
        left = item[head]
        right = item[tail]
print(ans)

发表于 2018-04-15 12:56:12 回复(0)
#不用递归!--人生苦短我用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)
def comb(num,head,tail):
    times=0
    left=num[head]
    right=num[tail]
    while(head<tail and left!=right):
        if(left<right):
            head+=1
            left+=num[head]
            times+=1
        else:
            tail-=1
            right+=num[tail]
            
    if(head>=tail):
        return times
    else:
        while(head<tail):
            head+=1
            tail-=1
            times+=comb(num,head,tail)
        return times
N=input('')
line=raw_input('')
num=line.split(' ')
print comb(num,head=0,tail=N)

发表于 2016-09-22 11:35:15 回复(0)
import random

n=int(input('请输入序列的长度:'))
s=input('请输入序列:')
n=len(s)
c=0
while s!=list(reversed(s)):
    j=n-c
    i=random.randint(0,j)
    if i<j:
        a=s[i]+s[i+1]
        s.remove(s[i])
        s.remove(s[i])
        s.insert(i,a)
        c+=1
    elif i==j:
        a=s[i]+s[i-1]
        s.remove(s[i])
        s.remove(s[i-1])
        s.insert(i-1,a)
        c+=1
    print(c)
请教大神怎么修改
发表于 2016-09-19 17:42:35 回复(0)