本题是一次扫描上的贪心。甲要让剩余串字典序尽量大,只能删一个 0;乙要让剩余串字典序尽量小,只能删一个 1。
关键观察:
0 不会改变各个 1 的相对顺序,因此乙眼中「最靠前的 1」始终是原串里最靠前的那个 1。1 也不会改变各个 0 的相对顺序。0,相当于从原串去掉该位。越靠前的 0 越可能处在高位,删掉它更能把后面较大的前缀顶上来,因此甲的最优是删最左的 0。期末测验用的答题卡是一排涂点,从左到右记成一条 0/1 串 s:
0:这一格还空着1:这一格已经涂黑两位同学要对这张卡做最后修订,各改恰好一格,顺序如下:
0 涂掉(从串里删掉这个字符)。甲希望剩下的串字典序尽量大(看起来「前面更满」)。1 擦掉。乙希望剩下的串字典序尽量小。甲先动手,双方都按对自己最有利的方式选格子。请返回改完之后剩下的串。
保证卡上至少有一个空格 0、至少一个已涂格 1。
请实现:
reviseMarks(s: str) -> str
一行:由字符 0 和 1 组成的字符串 s,不含引号,形如 101。
约束:
s 中至少各有一个 0 和一个 1一行字符串:双方最优修订后的剩余串。
输入:
101
输出:
1
说明:
0,甲只能涂掉它,剩余 1111 里擦掉一个 1(擦哪一个结果相同),剩余 1输入:
0001
输出:
00
说明:
0,剩余 0011(也是唯一的已涂格),剩余 00输入:
110010
输出:
1010
说明:甲涂掉最早的 0(下标从 0 计的第 2 位),乙擦掉最早的 1(第 0 位),剩下 1010。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册