首页 > 试题广场 >

回文序列

[编程题]回文序列

热度指数：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 1 3，{2, 1, 3} 不是回文序列；
再经过一次操作后，变为3 3，{3, 3} 是回文序列；
所以共需要进行两次转换。

算法知识视频讲解

JavaScript

ckcopy

var readline = require('readline');

const rl = readline.createInterface({

input: process.stdin,

output: process.stdout

});

var n, arr, t = 0;

rl.on('line', function (line) {

if (t === 0) {

n = Number(line);

t++;

}

else if (t === 1) {

arr = line.split(' ').map(function (x) {

return Number(x);

});

var i = 0, j = n - 1, count = 0;

while (arr.length >= 2 && i < j) {

if (arr[i] === arr[j]) {

i++;

j--;

}

else if (arr[i] < arr[j]) {

var a1 = arr[i], a2 = arr[i + 1];

arr.splice(i, 2, a1 + a2);

j--;

count++;

} else {

a1 = arr[j], a2 = arr[j - 1];

arr.splice(j - 1, 2, a1 + a2);

j--;

count++;

}

console.log(count);

process.exit(0);

}

});

发表于 2017-03-24 17:57:32 回复(0)

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)

JavaScript

释梵☎

"use strict";
const getConvertReverseTimes = (arr) => {
    let times = 0;
    let a = arr.slice(0);
    while (a.length > 1) {
        let left = a[0];
        let right = a[a.length - 1];
        if (left === right) {
            a = a.slice(1, a.length - 1);
        }
        else {
            times++;
            // 前面 > 后面 ? 合并后面 : 合并前面
            if (left > right) {
                a = a.slice(0, a.length - 1);
                a[a.length - 1] += right;
            }
            else {
                a = a.slice(1);
                a[0] += left;
            }
        }
        // console.log(a);
    }
    return times;
};

编辑于 2016-09-16 20:20:19 回复(0)