出場人物介紹：

小美：小學4年級學生，參加了學校的編程興趣小組崭放，已經(jīng)了解了Python語言的基本語法鬼吵，能夠看懂一些簡單的程序扣甲。她做事風風火火，對所有的事情都很好奇齿椅，喜歡打破砂鍋問到底琉挖，是一個叫人又愛又恨的小丫頭。

阿福：一個酷愛編程的8年級男生涣脚。大家都說他長得像國寶大熊貓示辈，動作緩慢，憨態(tài)可掬遣蚀。他做事情確實夠慢的矾麻，連說話也慢條斯理，可是他一點也不擔心妙同，他常常說：“慢就是快射富，只要堅持下去，蝸牛也能爬上金字塔粥帚∫群模”

古老師：雖然年近不惑，但依然對生活充滿熱情芒涡〔竦疲“愛生活愛運動”是他的人生信條卖漫，和孩子們一起編程是他最大的樂趣。他神出鬼沒赠群，總是在孩子們最需要幫助的時候出現(xiàn)羊始。當然，你也不能動不動就找古老師查描，因為他很忙突委，非常非常忙。所以冬三，遇到問題還是自己先思考吧匀油。

正文

列表的紛爭之回文數(shù)列

小美：前幾天我去廈門鼓浪嶼旅游了，看到一副很有趣的對聯(lián)：霧鎖山頭山鎖霧勾笆；天連水尾水連天敌蚜。

阿福：這叫回文聯(lián)，它是我國對聯(lián)中的一種窝爪。用回文形式寫成的對聯(lián)弛车，既可順讀，也可倒讀蒲每。不僅它的意思不變纷跛，而且頗具趣味，是我國的重要傳統(tǒng)文化之一邀杏。

小美：沒錯忽舟，回文聯(lián)倒讀順讀都一樣，有趣極了淮阐。

古老師：不僅僅有回文對聯(lián)叮阅，還有回文數(shù)字呢。我現(xiàn)在就給你們出個題目泣特，看看你們會不會做浩姥。

題目1：

回文數(shù)字串

函數(shù)功能：根據(jù)輸入的數(shù)字字符串，判斷其是否為回文數(shù)字串

函數(shù)名：isPalindrome(x:str) -> bool

參數(shù)表：x -- 存儲了正整數(shù)的字符串状您。

返回值：若x為回文數(shù)字串勒叠，返回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

古老師：沒錯飘诗，你們兩個人的方法都可行与倡。小美利用了字符串的特性，代碼簡單實用昆稿。但從理解算法的本質(zhì)來說纺座，確實是阿福的雙指針掃描方法比較好。類似的題目非常多溉潭，基本上都是采用阿福的方法净响。下面我們就來看一道關于回文數(shù)列的題目。

題目2：

????回文數(shù)列是指一個包含n個整數(shù)的數(shù)列a喳瓣，對于任意元素a[i](0<=i<n)别惦，都有a[i]==a[n-i-1]。

????但是回文數(shù)列非常難得》蛲郑現(xiàn)在小明想到了一個辦法，他可以將數(shù)列中氯庆，任意兩個相鄰的元素合并蹭秋，用它們的和來代替，合并完成的值還可以和其他相鄰值不斷合并堤撵，直到獲得回文數(shù)列或只剩下一個元素（因為只有一個元素的數(shù)列肯定是回文數(shù)列）仁讨。

????當然，小明希望他的回文數(shù)列盡可能長实昨，因此洞豁，請你幫助小明計算一下，對于一個長度為n的數(shù)列荒给，經(jīng)過最少多少次合并丈挟，可以構(gòu)成一個回文數(shù)列。

函數(shù)功能：計算將一個普通數(shù)列變成回文數(shù)列所需的最小合并次數(shù)志电。

函數(shù)名：be_palindrome(a:list) -> int

參數(shù)表：a -- 存儲了整數(shù)數(shù)列的列表曙咽。

返回值：返回將列表a變成回文數(shù)列所需的最小合并次數(shù)。

示例1：輸入a=[1,2,3]挑辆，返回1例朱。解釋：將1,2合并得到回文數(shù)列[3,3]。

示例2：輸入a=[1,2,4,6,1]鱼蝉，返回1洒嗤。解釋：將2,4合并得到回文數(shù)列[1,6,6,1]。

示例3：輸入a=[1,4,3,2]魁亦，返回2渔隶。解釋：先將1和4合并，得到[5,3,2]洁奈；再將3和2合并得到回文數(shù)列[5,5]派撕。

小美：這道題目有點難呢婉弹。要求最小合并次數(shù)，合并的方式那么多终吼，難道要一個個暴力枚舉嗎镀赌？

阿福：暴力枚舉？那時間復雜度太高了际跪，它只要求最小的合并次數(shù)商佛，又沒問具體的合并方法，我覺得沒有必要保留合并的過程姆打。

古老師：呵呵良姆，別想得太復雜，要從回文數(shù)列的特征入手幔戏，確定什么時候需要合并玛追。再回顧一下前面的雙指針掃描方法，看看有沒有什么啟發(fā)闲延？好了痊剖，我只能說這么多了，剩下的自己去琢磨吧垒玲。拜拜咯陆馁。

彩蛋：

小美：古老師每次都跑得這么快，也不多給點提示合愈。

阿福：我倒是覺得他已經(jīng)提示得夠多了叮贩。

小美：這就夠多了啊佛析？我還沒有頭緒呢益老。你給我說說看吧。

阿福：這個其實和前面判斷回文數(shù)字串的方法差不多寸莫，只不過當兩側(cè)元素不相等時杨箭，需要將較小一側(cè)的兩個元素合并而已。具體操作是用雙指針從左右兩側(cè)向中間掃描储狭，比較a[L] 和a[R]互婿，若兩個元素相等，則左右指針均向中間移動一位辽狈；若左側(cè)元素較小慈参，則左指針右移一位，再合并左側(cè)元素刮萌；若右側(cè)元素較小驮配，則右指針左移一位，再合并右側(cè)元素。

?????? 這樣左右指針不斷地向中間掃描壮锻，直到二者靠攏為止琐旁，此時若最后兩個元素相等，則說明得到了回文數(shù)列猜绣；若不相等灰殴，則合并這兩個元素，也能得到回文數(shù)列掰邢。

?????? 用這種方法合并元素牺陶，所需的次數(shù)肯定是最少的。

小美：確實很有道理辣之！讓我梳理一下思路掰伸。。怀估。狮鸭。。多搀。你看代碼是不是這樣歧蕉？

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]:#若左側(cè)元素較小酗昼，則左指針右移一位，再合并左側(cè)元素

??????????? s, L = s + 1, L + 1

??????????? a[L] += a[L-1]

??????? else: #若右側(cè)元素較小梳猪，則右指針左移一位麻削，再合并右側(cè)元素

??????????? s, R = s + 1, R - 1

??????????? a[R] += a[R+1]

????return s

阿福：沒錯，正是這樣春弥。