如果一个数字序列逆置之后跟原序列是一样的就称这样的数字序列为回文序列。例如：
{1, 2, 1}, {15, 78, 78, 15}, {112} 是回文序列,
{1, 2, 2}, {15, 78, 87, 51}, {112, 2, 11} 不是回文序列。
现在给出一个数字序列，允许使用一种转换操作：
选择任意两个相邻的数，然后从序列移除这两个数，并用这两个数字的和插入到这两个数之前的位置(只插入一个和)。
现在对于所给序列要求出最少需要多少次操作可以将其变成回文序列。
[编程题]回文序列
- 热度指数：23527 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
输入为两行，第一行为序列长度n ( 1 ≤ n ≤ 50) 第二行为序列中的n个整数item[i] (1 ≤ iteam[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)
//模仿 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)
//利用递归，两端不论怎样都要相等或者最终合成为同一个数
#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)
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)
/*思路：分别使用两个指针，从两头向中间靠拢。如果两个指针处的数值相等，两个指针同时向中间移动。如果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)
#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)
#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)
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)
双指针
从两端向中间合并，给定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)
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)
#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)
#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)
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)
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);
}
}
}
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)
题目分析：
操作：对相邻两数加和放入之前位置
无论如何都会得到回文序列（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)
#include <iostream>
#include <vector>
using namespace std;
int main()
{ int n; while(cin>>n) { vector<int> a(n); for(int i=0;i<n;i++) cin>>a[i]; int result = 0, n = a.size(); if(n<=1) result = 0; int l=0,r=n-1,p=a[l],q=a[r]; while(l<r) { if(p<q) { p += a[++l]; result++; }else if(p > q){ q += a[--r]; result++; }else{ p = a[++l]; q = a[--r]; } } cout<<result<<endl; } return 0;
}
发表于 2018-01-17 00:34:15
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-10-14 16:49:15 -
2022-09-14 10:59:05 -
2022-09-06 20:18:54 -
2022-09-06 00:48:48
-
2022-09-03 14:10:21
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
