筆試算法模拟題精解之“恢複字元串”

【線上程式設計産品介紹】

阿裡雲開發者社群線上程式設計：

免費刷題大神器，助你拿到好offer

周賽月賽不停歇，做題還能領獎品

大賽筆試全真題，常做常新有驚喜

點選連結開始産品體驗：

https://developer.aliyun.com/coding 本文為大家介紹的是“111.恢複字元串”的解法探究。先來看一下題目内容：

題目詳情

等級：中等

知識點：貪心

檢視題目：恢複字元串

給出兩個僅包含“+”、“-”兩種字元且長度相同字元串s1、 s2，你需要通過填充數字将這兩個字元串恢複成一個合法的表達式。并且隻能填入正整數，恢複後的表達式的值必須非負。

例如對于字元串“+-”，你可以将其變成“1+1-2”，但是不可以變成“1+1-3”，也不可以變成“1+0-1”。定義你的消耗為你填充的所有正整數的和。比如“1+1-2”的消耗為 1 + 1 + 2 = 4。你需要将這兩個字元串都恢複成合法表達式，并且盡量的使它們的內插補點最小，于此同時你還需要使你的消耗最小。

相信你通過思考已經發現最小內插補點總是0，是以你隻需要求出內插補點為0時的最小消耗即可。字元串長度都小于100000。

輸入兩個字元串s1和s2。

輸出一個數字，表示最小消耗。

示例1

輸入：

“++-”

“--+”

輸出：

10

注意

樣例最優解為“1+1+1-1”，“3-1-1+1”。

解題方法：

首先可以确定最小值一定為0。分兩種情況讨論。

1. 兩個字元串都沒有負号的時候，最優解的所有位置都填1。最小消耗為 2*（n+1）。
2. 表達式中僅需要有一個負号，表達式的值就可以為任何值。此時兩個表達式可以互相調整，是以最小差也是0。

表達式中除了第一位以外每位數字填1可以得到最小消耗，因為值加在哪一位都是等效的。

不妨假設都加在第一位。計算出s1,s2的正負号數量的差，分别為x和y。假設第一位分别為pa，pb，我們隻需要使（pa+x==pb+y）即可。

假設最終表達式的值為final，則final=max(max(x, y) + 1, 0)，則pa=final-x，pb=final-y。

看完之後是不是有了答題思路了呢，快來練練手吧：

111.恢複字元串

線上程式設計周賽、月賽火熱進行中，更有限時答題活動，定制衛衣、雙肩背包、機械鍵盤等多重好禮等你來拿~每天都有好禮相送~點選了解周賽詳情：

線上程式設計3月份比賽正式開啟！機械鍵盤等你拿！