← 返回目录

算法笔试模拟题精解之“恢复字符串”

第 18 / 74 卷日期：

算法笔试模拟题精解之“恢复字符串”

贡献者 | 猿圈

简介：本题首先可以确定最小值一定为 0。接下来要分两种情况来讨论。

题目描述

等级：中等

知识点：贪心

查看题目：恢复字符串

给出两个仅包含“+”、“-”两种字符且长度相同字符串 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）。

  1. 表达式中仅需要有一个负号，表达式的值就可以为任何值。此时两个表达式

可以相互调整，因此最小差也是 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。

看完之后是不是有了答题思路了呢，快来练练手吧：恢复字符串

全站分卷索引 · 74 卷
  1. 1一、算法思想
  2. 2算法笔试模拟题精解之“打怪兽”
  3. 31.2 贪心
  4. 4算法笔试模拟题精解之“最强的团队”
  5. 5算法笔试模拟题精解之“Tom 爱吃巧克力”
  6. 6算法笔试模拟题精解之“吃奶酪”
  7. 7算法笔试模拟题精解之“一的个数”
  8. 8算法笔试模拟题精解之“Bob 的花束”
  9. 9算法笔试模拟题精解之“钱庄”
  10. 10算法笔试模拟题精解之“移动射击”
  11. 11算法笔试模拟题精解之“相似数组”
  12. 12算法笔试模拟题精解之“过吊桥”
  13. 13算法笔试模拟题精解之“完美排列”
  14. 14算法笔试模拟题精解之“采摘圣诞果”
  15. 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
  16. 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
  17. 17算法笔试模拟题精解之“学习小组”
  18. 18算法笔试模拟题精解之“恢复字符串”
  19. 191.3 DP/ 动态规划
  20. 20算法笔试模拟题精解之“寻找等比数列”
  21. 21算法笔试模拟题精解之“字符配对”
  22. 22算法笔试模拟题精解之“数组染色”
  23. 23算法笔试模拟题精解之“连绵的群山”
  24. 24算法笔试模拟题精解之“难住Tom 的问题”
  25. 25算法笔试模拟题精解之“变化的字符”
  26. 26算法笔试模拟题精解之“跳房子”
  27. 27算法笔试模拟题精解之“寒假活动”
  28. 28算法笔试模拟题精解之“最短路”
  29. 29算法笔试模拟题精解之“codancer 上楼”
  30. 30算法笔试模拟题精解之“木棒拼接”
  31. 31算法笔试模拟题精解之“Codancer 的数组封印”
  32. 32算法笔试模拟题精解之“Jerry 的异或运算”
  33. 33算法笔试模拟题精解之“小明的数学作业”
  34. 34算法笔试模拟题精解之“奇偶数列”
  35. 351.4 剪枝
  36. 361.5 尺取法
  37. 37算法笔试模拟题精解之“调整数组”
  38. 38算法笔试模拟题精解之“最优分组”
  39. 39算法笔试模拟题精解之“破译密码”
  40. 40二、数据结构
  41. 412.2 搜索
  42. 42算法笔试模拟题精解之“能量半径”
  43. 43算法笔试模拟题精解之“苹果收获程序”
  44. 44算法笔试模拟题精解之“恐怖的辐射”
  45. 45算法笔试模拟题精解之“树的拆分”
  46. 46算法笔试模拟题精解之“Password”
  47. 47算法笔试模拟题精解之“神奇数字在哪里”
  48. 48算法笔试模拟题精解之“神奇的棋子”
  49. 492.3 树
  50. 50算法笔试模拟题精解之“Codancer 的旅行”
  51. 51算法笔试模拟题精解之“Codancer 的求和”
  52. 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
  53. 532.4 线型
  54. 54算法笔试模拟题精解之“最活跃的数”
  55. 55算法笔试模拟题精解之“非递减序列”
  56. 56算法笔试模拟题精解之“Tom 跳方格”
  57. 57算法笔试模拟题精解之“复杂的字符串”
  58. 58算法笔试模拟题精解之“神秘消失”
  59. 59三、计算
  60. 60算法笔试模拟题精解之“简单题？
  61. 61算法笔试模拟题精解之“朋友一生一起走”
  62. 62算法笔试模拟题精解之“正三角塔”
  63. 63算法笔试模拟题精解之“组队难题”
  64. 64算法笔试模拟题精解之“2n 合体”
  65. 65算法笔试模拟题精解之“平行线”
  66. 66算法笔试模拟题精解之“叠叠高”
  67. 67算法笔试模拟题精解之“公平”
  68. 68算法笔试模拟题精解之“Tom 的手工课”
  69. 69算法笔试模拟题精解之“填数问题”
  70. 70算法笔试模拟题精解之“Jerry 的考验”
  71. 71算法笔试模拟题精解之“超车”
  72. 72算法笔试模拟题精解之“坏掉的时钟”
  73. 73算法笔试模拟题精解之“期末考试”
  74. 74算法笔试模拟题精解之“滑雪比赛”