成对的69

[编程题]成对的69

热度指数：1464 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

成对的69匹配序列定义为：

1、空串""是一个成对的69序列；

2、如果"X"和"Y"是成对的69序列，那么"XY"也是成对的69序列；

3、如果"X"是一个成对的69序列，那么"6X9"也是一个成对的69序列；

4、每个成对的69序列都可以由以上规则生成。例如，"", "69", "6699", "6969"都是成对的。

现在给出一个序列S，允许你的操作是：在S的开始和结尾出添加一定数量的6或者9，使序列S变为一个成对的69序列。输出添加最少的6或者9之后成对的69序列是什么。

示例1

输入

"66"

输出

"6699"

算法知识视频讲解

不是怪人

发表于 2021-09-09 22:02:26

做的时候一直在想是不是动态规划或者分治之类的问题，交卷后看了题解才知道是括号匹配的变形。既然数字只有6和9，就不需要用堆栈了，只需要一个变量cnt记录未匹配的6的数量思路根据题目对于69匹配序列的定义可以看出：对于一个合法的69序列，6和9的数量一定是相等的，即一个6对应一个9 6和9不仅一展开全文