算法leetcode

力扣2810-故障键盘

字数统计: 1.2k字   |   阅读时长: 5分
,

摘要: 画图观察，找规律，猜想出结论

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

今天看一个模拟题，可以通过模拟的方式去做。但是还有更优雅的方式，不用来回来去地反转字符串，而只需要反转少量的子串即可。不过这需要通过画图分析，找到规律猜想出结论，所以涉及到一点找规律的思想。

题目

你的笔记本键盘存在故障，每当你在上面输入字符 ‘i’ 时，它会反转你所写的字符串。而输入其他字符则可以正常工作。

给你一个下标从 0 开始的字符串 s ，请你用故障键盘依次输入每个字符。

返回最终笔记本屏幕上输出的字符串。

示例 1：
输入：s = “string”
输出：”rtsng”
解释：
输入第 1 个字符后，屏幕上的文本是：”s” 。
输入第 2 个字符后，屏幕上的文本是：”st” 。
输入第 3 个字符后，屏幕上的文本是：”str” 。
因为第 4 个字符是 ‘i’ ，屏幕上的文本被反转，变成 “rts” 。
输入第 5 个字符后，屏幕上的文本是：”rtsn” 。
输入第 6 个字符后，屏幕上的文本是： “rtsng” 。
因此，返回 “rtsng” 。

示例 2：
输入：s = “poiinter”
输出：”ponter”
解释：
输入第 1 个字符后，屏幕上的文本是：”p” 。
输入第 2 个字符后，屏幕上的文本是：”po” 。
因为第 3 个字符是 ‘i’ ，屏幕上的文本被反转，变成 “op” 。
因为第 4 个字符是 ‘i’ ，屏幕上的文本被反转，变成 “po” 。
输入第 5 个字符后，屏幕上的文本是：”pon” 。
输入第 6 个字符后，屏幕上的文本是：”pont” 。
输入第 7 个字符后，屏幕上的文本是：”ponte” 。
输入第 8 个字符后，屏幕上的文本是：”ponter” 。
因此，返回 “ponter” 。

提示：

1
2
3
1 <= s.length <= 100
s 由小写英文字母组成
s[0] != 'i'

题解

算法: 模拟

首先处理连续 i 的问题。一个 i 代表一次反转，因此连续奇数个 i 相当于 1 个 i；连续偶数个 i 相当于没有 i。此外前缀中的 i 都相当于没有，直接全删掉即可。

因此预处理阶段做以下两步：

  • 前缀中的 i 全部删除。
  • 非前缀的 i，连续偶数个 i 直接删除；连续奇数个 i 替换为一个 i。

预处理之后，剩下的字符串中假设还剩 $n_{i}$ 个 i，将字符串分为 $n_{i} + 1$ 份子串。将各份子串按顺序维护在数组 items 中。items[j] 表示第 $j-1$ 个 i 与第 $j$ 个 i 之间的部分。

记结果字符串为 result，则在 result 中 items[j] 中的部分总是连在一起的，但是可能会反转。如果 items[j] 右边有奇数个 i，即 ni - j 为奇数，则在结果字符串中 items[j] 这部分要反转。

这样 items 中需要反转的部分为 items[ni - 1], items[ni - 3], ...；不需要反转的部分为 items[ni - 2], items[ni - 4], ...。

下面要考虑在结果字符串中，items 中的各个部分的连接顺序。

最后一个 i （第 $n_{i}$ 个 i）后面的部分是不变的，生成完结果字符串其它部分之后，将 items[ni] 接在后面即可。

经过画图分析，可以发现结果字符串 result 中各份子串的顺序是，首先将 items 中需要反转的部分按照 items[ni - 1], items[ni - 3], ... 的顺序压入 result，然后将不需要反转的部分按照 items[ni - 2], items[ni - 4], ... 的逆序压入 result，最后将 items 最后一个元素压入 result。

例如考虑 items = [a, b, c, d, e, f, g]，a, b, c, d, e, f, g 为被 i 分割后的子串。则 f, d, b 是需要反转的，首先将其压入 result，然后再将不需要反转的 e, c, a 逆序压入 result，最后将 g 接在末尾，得到 result = [f, d, b, a, c, e, g]。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def finalString(self, s: str) -> str:
        s = self.preprocess(s)
        items = s.split("i")
        ni = len(items) - 1 # i 的个数
        # items[j] 右边有 ni - j 个 i，若 (ni - i) % 2 为 1 则需要反转
        ans = []
        for j in range(ni - 1, -1, -2):
            ans.append(items[j][::-1])
        for j in reversed(range(ni - 2, -1, -2)):
            ans.append(items[j])
        ans.append(items[ni])
        return "".join(ans)

    def preprocess(self, s: str) -> str:
        result = []
        n = len(s)
        i = 0
        while i < n and s[i] == "i":
            i += 1
        while i < n:
            j = i
            while j < n and s[j] != "i":
                j += 1
            result.append(s[i:j])
            if j == n:
                break
            i = j
            while j < n and s[j] == "i":
                j += 1
            if (j - i) % 2 == 1:
                result.append("i")
            i = j
        print(result)
        return "".join(result)
Share