出场人物介绍：
小美：小学4年级学生，参加了学校的编程兴趣小组，已经了解了Python语言的基本语法，能够看懂一些简单的程序。她做事风风火火，对所有的事情都很好奇，喜欢打破砂锅问到底，是一个叫人又爱又恨的小丫头。
阿福：一个酷爱编程的8年级男生。大家都说他长得像国宝大熊猫，动作缓慢，憨态可掬。他做事情确实够慢的，连说话也慢条斯理，可是他一点也不担心，他常常说：“慢就是快，只要坚持下去，蜗牛也能爬上金字塔。”
古老师：虽然年近不惑，但依然对生活充满热情。“爱生活爱运动”是他的人生信条，和孩子们一起编程是他最大的乐趣。他神出鬼没，总是在孩子们最需要帮助的时候出现。当然，你也不能动不动就找古老师，因为他很忙，非常非常忙。所以，遇到问题还是自己先思考吧。
正文
列表的纷争之回文数列
小美：前几天我去厦门鼓浪屿旅游了，看到一副很有趣的对联：雾锁山头山锁雾；天连水尾水连天。
阿福：这叫回文联，它是我国对联中的一种。用回文形式写成的对联，既可顺读，也可倒读。不仅它的意思不变，而且颇具趣味，是我国的重要传统文化之一。
小美：没错，回文联倒读顺读都一样，有趣极了。
古老师：不仅仅有回文对联，还有回文数字呢。我现在就给你们出个题目，看看你们会不会做。
题目1：
回文数字串
函数功能：根据输入的数字字符串，判断其是否为回文数字串
函数名：isPalindrome(x:str) -> bool
参数表：x -- 存储了正整数的字符串。
返回值：若x为回文数字串，返回True，否则返回False。
示例1：输入x='123321'，返回True
示例2：输入x='100'，返回False
小美：这个不难，只要比较一下顺序和逆序字符串是否相等就行了。代码如下：
def is_palindrome(x: str) -> bool:
return x ==x[::-1]
阿福：我觉得还是使用双指针扫描，逐个比较字符的方法比较好。
def is_palindrome2(x: str) -> bool:
L, R = 0, len(x) - 1
while L < R:
if x[L] != x[R]:
return False
L, R = L + 1, R - 1
return True
古老师：没错，你们两个人的方法都可行。小美利用了字符串的特性，代码简单实用。但从理解算法的本质来说，确实是阿福的双指针扫描方法比较好。类似的题目非常多，基本上都是采用阿福的方法。下面我们就来看一道关于回文数列的题目。
题目2：
回文数列是指一个包含n个整数的数列a，对于任意元素a[i](0<=i<n)，都有a[i]==a[n-i-1]。
但是回文数列非常难得。现在小明想到了一个办法，他可以将数列中，任意两个相邻的元素合并，用它们的和来代替，合并完成的值还可以和其他相邻值不断合并，直到获得回文数列或只剩下一个元素（因为只有一个元素的数列肯定是回文数列）。
当然，小明希望他的回文数列尽可能长，因此，请你帮助小明计算一下，对于一个长度为n的数列，经过最少多少次合并，可以构成一个回文数列。
函数功能：计算将一个普通数列变成回文数列所需的最小合并次数。
函数名：be_palindrome(a:list) -> int
参数表：a -- 存储了整数数列的列表。
返回值：返回将列表a变成回文数列所需的最小合并次数。
示例1：输入a=[1,2,3]，返回1。解释：将1,2合并得到回文数列[3,3]。
示例2：输入a=[1,2,4,6,1]，返回1。解释：将2,4合并得到回文数列[1,6,6,1]。
示例3：输入a=[1,4,3,2]，返回2。解释：先将1和4合并，得到[5,3,2]；再将3和2合并得到回文数列[5,5]。
小美：这道题目有点难呢。要求最小合并次数，合并的方式那么多，难道要一个个暴力枚举吗？
阿福：暴力枚举？那时间复杂度太高了，它只要求最小的合并次数，又没问具体的合并方法，我觉得没有必要保留合并的过程。
古老师：呵呵，别想得太复杂，要从回文数列的特征入手，确定什么时候需要合并。再回顾一下前面的双指针扫描方法，看看有没有什么启发？好了，我只能说这么多了，剩下的自己去琢磨吧。拜拜咯。
彩蛋：
小美：古老师每次都跑得这么快，也不多给点提示。
阿福：我倒是觉得他已经提示得够多了。
小美：这就够多了啊？我还没有头绪呢。你给我说说看吧。
阿福：这个其实和前面判断回文数字串的方法差不多，只不过当两侧元素不相等时，需要将较小一侧的两个元素合并而已。具体操作是用双指针从左右两侧向中间扫描，比较a[L] 和a[R]，若两个元素相等，则左右指针均向中间移动一位；若左侧元素较小，则左指针右移一位，再合并左侧元素；若右侧元素较小，则右指针左移一位，再合并右侧元素。
这样左右指针不断地向中间扫描，直到二者靠拢为止，此时若最后两个元素相等，则说明得到了回文数列；若不相等，则合并这两个元素，也能得到回文数列。
用这种方法合并元素，所需的次数肯定是最少的。
小美：确实很有道理！让我梳理一下思路。。。。。。你看代码是不是这样？
def be_palindrome(a: list) -> int:
s, L, R = 0, 0, len(a) - 1
while L < R:
if a[L] == a[R]: #若两个元素相等，则左右指针均向中间移动一位
L, R = L + 1, R - 1
elif a[L] < a[R]:#若左侧元素较小，则左指针右移一位，再合并左侧元素
s, L = s + 1, L + 1
a[L] += a[L-1]
else: #若右侧元素较小，则右指针左移一位，再合并右侧元素
s, R = s + 1, R - 1
a[R] += a[R+1]
return s
阿福：没错，正是这样。
网友评论