【C语言】回文数组问题

1.问题描述

求出一个整数数组经过至少多少次的操作次数后能变成回文数组

2.源代码

#include <stdio.h>
#define Maxn 10001
int main()
{   
	int flag=0;
    int i,n,a[Maxn],left,right,ans=0;
    
    scanf("%d",&n);
    
    for(i=0;i<n;i++) 
		scanf("%d",&a[i]);
    
    left=0; right=n-1;        
    while(left<right)
    {
        if(a[left] == a[right])
        {
            if(left+1==right || left+2==right)
			{//成功得到回文数组 
                flag=1;
			}
 			
            left++; right--;//left和right指针的移动 
        }
        else if(a[left] > a[right]) //右部做操作 
        {
            a[right-1] += a[right]; 
            right--;
            ans++;
        }
        else//左部做操作 
        {	
            a[left+1] += a[left];
            left++;
		    ans++;
        }
        
    }
         
    if(flag==0) ans=-1;
    printf("%d\n",ans);
    return 0;
}

3.代码思路

• 定义一个主函数main，它首先声明一个长度为Maxn的整数数组a，一个整数变量n，一个循环控制变量i，一个标记变量flag，一个记录操作次数的变量ans，和两个指针变量left和right。然后，使用scanf函数从标准输入读取一个整数n，表示数组的实际长度，以及n个整数，作为数组a的元素。
• 接下来，将指针left和right分别初始化为数组的第一个和最后一个元素的下标，即0和n-1，然后使用一个while循环，不断地将数组的两端向中间移动，直到指针相遇或交叉。循环的每一步，都做以下操作：
  • 如果指针left和right所指向的元素相等，说明这两个元素是回文的，就将指针分别向右和向左移动一位，即left++和right--。同时，检查是否满足left+1==right或left+2==right的条件，如果满足，说明数组已经是回文的，就将标记变量flag设为1，表示成功得到回文数组。
  • 如果指针left所指向的元素大于指针right所指向的元素，说明需要对数组的右部做操作，就将指针right的左边一个元素的值加上指针right所指向的元素的值，相当于将这两个元素合并，然后将指针right向左移动一位，即right--。同时，将操作次数变量ans加一，表示进行了一次操作。
  • 如果指针left所指向的元素小于指针right所指向的元素，说明需要对数组的左部做操作，就将指针left的右边一个元素的值加上指针left所指向的元素的值，相当于将这两个元素合并，然后将指针left向右移动一位，即left++。同时，将操作次数变量ans加一，表示进行了一次操作。
• 最后，如果标记变量flag为0，说明数组无法变成回文的，就将操作次数变量ans设为-1，表示无解。然后，使用printf函数将操作次数变量ans的值输出到标准输出，并换行。返回0表示程序正常结束。

这段代码的效果是，对于给定的整数数组a，它会求出最少的操作次数，使得数组变成回文的，如果无法变成回文的，就输出-1。例如，如果输入的数组a是[1, 4, 3, 2]，那么输出的操作次数是2，因为可以通过以下两步操作得到回文数组[5, 5]：

• 将a[1]和a[2]合并，得到[1, 7, 2]
• 将a[0]和a[1]合并，得到[8, 2]
• 将a[0]和a[1]合并，得到[10]