每日一题——Python实现PAT甲级1112 Stucked Keyboard（举一反三+思想解读+逐步优化）五千字好文

一个认为一切根源都是“自己不够强”的INTJ

个人主页：用哲学编程-****博客
专栏：每日一题——举一反三
Python编程学习
Python内置函数

Python-3.12.0文档解读

目录

 我的写法

时间复杂度

空间复杂度

总结

我要更强

代码分析

时间复杂度

空间复杂度

哲学和编程思想

抽象与具体化：

效率与优化：

数据结构与算法：

迭代与递归：

模块化与可维护性：

预处理与后处理：

单一职责原则：

测试与验证：

举一反三

1. 抽象与具体化

2. 效率与优化

3. 数据结构与算法

4. 迭代与递归

5. 模块化与可维护性

6. 预处理与后处理

7. 单一职责原则

8. 测试与验证

综合应用

---

题目链接

 我的写法

# 读取输入的整数 k
k = int(input())

# 读取输入的字符串 resulting_str
resulting_str = input()

# 初始化一个空集合，用于存储去重后的字符
resulting_str_set = set()

# 初始化一个空集合，用于存储卡住的键
stucked_keys = set()

# 遍历字符串中的每一个字符
for char in resulting_str:
    # 如果字符不在集合 resulting_str_set 中
    if char not in resulting_str_set:
        # 将字符添加到集合 resulting_str_set 中
        resulting_str_set.add(char)
        # 检查字符在字符串中出现的次数是否是 k 的整数倍
        if resulting_str.count(char * k) * k == resulting_str.count(char):
            # 如果是的话，说明这个字符是卡住键，将其添加到 stucked_keys 集合中
            stucked_keys.add(char)
            # 打印卡住的键，不换行
            print(char, end='')

# 打印一个换行符
print()

# 遍历所有卡住的键
for char in stucked_keys:
    # 将原字符串中所有连续 k 次出现的卡住键替换为单个字符
    resulting_str = resulting_str.replace(char * k, char)

# 输出处理后的字符串
print(resulting_str)

这段代码的功能是从输入的字符串中识别出“卡住”的键，并在输出中将这些卡住的键只显示一次，同时还会恢复原始字符串中这些卡住键的正确形式。下面是对代码的专业点评以及复杂度分析：

1. 输入处理：
2. 集合初始化：
3. 遍历字符并检查卡住键：
   • 通过 if char not in resulting_str_set 确保每个字符只处理一次，避免重复计算。
   • resulting_str.count(char * k) 计算子串 char * k 在 resulting_str 中的出现次数，但这部分的计算效率不高，因为 count 方法的时间复杂度为 (O(n))。
   • resulting_str.count(char * k) * k == resulting_str.count(char) 检查字符出现次数是否为 k 的整数倍。如果是，则该字符认为是卡住键。
4. 替换卡住键的子串：
   • 遍历卡住键集合，并将字符串中连续 k 次出现的卡住键替换为单个字符。
5. 输出结果：

时间复杂度

1. 字符遍历：遍历字符串的每一个字符，时间复杂度为 (O(n))，其中 (n) 是字符串的长度。
2. 字符计数：resulting_str.count(char * k) 的时间复杂度为 (O(n))，这个操作在最坏情况下需要对每个字符进行一次，总的时间复杂度为 (O(n^2))。
3. 替换操作：替换的时间复杂度为 (O(n))，因为 replace 方法需要遍历整个字符串。

综合来看，最坏情况下的时间复杂度为 (O(n^2))。

空间复杂度

1. 集合存储：两个集合 resulting_str_set 和 stucked_keys 最多存储 n 个字符，所以空间复杂度为 (O(n))。
2. 字符串存储：输入字符串和处理后的字符串都需要占用 (O(n)) 的空间。

综合来看，空间复杂度为 (O(n))。

总结

这段代码实现了预期的功能，但在字符计数部分的效率较低，导致最坏情况下的时间复杂度为 (O(n^2))。可以通过更高效的算法（例如滑动窗口或预处理字符频率）来优化计算字符重复出现的次数，从而降低总体时间复杂度。总体而言，代码逻辑清晰，结构合理，但在处理大规模输入时性能可能受限。

---

我要更强

为了优化这段代码，可以采取以下方法：

1. 优化计数操作：我们可以通过一次遍历来记录每个字符的出现位置和出现次数，这样可以避免多次使用 count 函数。
2. 使用哈希表：用字典代替集合来存储字符的频率及其索引信息，可以在一次遍历中完成所有统计和检查操作。

下面是优化后的代码，时间复杂度从 (O(n^2)) 降低到 (O(n))，空间复杂度仍为 (O(n))。

# 读取输入的整数 k
k = int(input())

# 读取输入的字符串 resulting_str
resulting_str = input()

# 初始化一个字典用于存储字符的频率
char_count = {}

# 遍历字符串，统计字符频率
for i, char in enumerate(resulting_str):
    if char not in char_count:
        char_count[char] = []
    char_count[char].append(i)

# 初始化一个集合，用于存储卡住的键
stucked_keys = set()

# 检查每个字符的频率是否符合卡住键的条件
for char, indices in char_count.items():
    if len(indices) % k == 0:
        # 符合卡住键条件
        stucked_keys.add(char)
        # 输出卡住的键，不换行
        print(char, end='')

print()

# 构建一个新的字符串，用于替换卡住键
resulting_list = list(resulting_str)
for char in stucked_keys:
    i = 0
    while i < len(resulting_list):
        # 找到连续 k 个相同字符的位置
        if resulting_list[i:i + k] == [char] * k:
            # 替换为单个字符
            resulting_list[i:i + k] = [char]
            i += k
        else:
            i += 1

# 将列表转换为字符串并输出
resulting_str = ''.join(resulting_list)
print(resulting_str)

代码分析

1. 输入处理：
2. 字符频率统计：
   • 这里使用字典 char_count 记录每个字符出现的索引位置。
3. 卡住键检查和输出：
   • 检查每个字符的出现次数是否是 k 的整数倍，符合条件的字符加入 stucked_keys 集合，并输出。
4. 构建新字符串：

• 使用列表 resulting_list 来构建新的字符串，逐段检查并替换连续 k 个相同字符。

时间复杂度

1. 字符频率统计：遍历字符串一次，时间复杂度为 (O(n))。
2. 卡住键检查：检查每个字符的频率，最坏情况下时间复杂度为 (O(n))。
3. 构建新字符串：遍历列表进行替换，时间复杂度为 (O(n))。

综合来看，优化后的时间复杂度为 (O(n))。

空间复杂度

1. 字符频率统计：字典 char_count 需要存储每个字符的索引，空间复杂度为 (O(n))。
2. 结果存储：列表 resulting_list 需要与输入字符串相同的空间，空间复杂度为 (O(n))。

综合来看，空间复杂度为 (O(n))。

通过这些优化，代码在时间复杂度和空间复杂度方面已经有了显著改进。

---

哲学和编程思想

优化这段代码的过程中，涉及到了多种哲学和编程思想，具体包括：

1. 抽象与具体化：

   • 在编程中，抽象是指忽略或隐藏细节，专注于问题的本质特征。具体化则是将抽象的概念转化为具体的实现。在这个优化过程中，我们抽象出了“卡住键”的概念，并通过具体化的代码实现来处理这些键。

2. 效率与优化：

   • 编程中的效率哲学强调在解决问题时尽可能减少资源消耗（如时间、空间）。通过优化计数操作和使用更高效的数据结构（如哈希表），我们减少了时间复杂度，体现了效率哲学。

3. 数据结构与算法：

   • 选择合适的数据结构和算法是编程中的核心思想。在这个例子中，我们使用了字典（哈希表）来存储字符的频率和位置，这是一种高效的数据结构，可以快速查找和更新数据。

4. 迭代与递归：

   • 迭代是通过循环重复执行一系列操作，而递归是通过函数调用自身来解决问题。在这个优化中，我们使用了迭代（遍历字符串）来处理问题，而不是递归，因为迭代通常在时间和空间上更高效。

5. 模块化与可维护性：

   • 模块化编程思想强调将程序分解为独立、可替换的模块，每个模块具有单一功能。这种思想有助于提高代码的可读性和可维护性。在这个代码中，我们通过将不同的功能（如输入处理、频率统计、卡住键检查）分离到不同的代码块中，实现了模块化。

6. 预处理与后处理：

   • 预处理是在处理主要问题之前对数据进行准备，后处理是在处理主要问题之后对结果进行整理。在这个例子中，我们预先统计了字符的频率和位置，这是预处理；在处理完卡住键后，我们构建了新的字符串，这是后处理。

7. 单一职责原则：

   • 这个原则要求一个模块或函数应该只有一个引起它变化的原因。在优化后的代码中，每个函数或代码块都专注于一个特定的任务，如统计字符频率、检查卡住键、构建新字符串等。

8. 测试与验证：

• 在编程中，测试和验证是确保代码正确性的重要环节。虽然在这个讨论中没有展示具体的测试代码，但在实际开发中，编写测试用例来验证代码的功能是不可或缺的。

通过这些哲学和编程思想的指导，能够更有效地解决问题，提高代码的质量和性能。

---

举一反三

1. 抽象与具体化

技巧：

• 找出共性：在解决问题之前，先找出问题中各个部分的共性，进行抽象化。这样可以减少重复工作。
• 分而治之：将大问题分解成若干个子问题，逐个解决。每个子问题可以更容易抽象和具体化。

举例：给定一组操作（如插入、删除、查找），抽象出一个通用的数据结构接口，然后具体化为不同的数据结构（如数组、链表、哈希表）。

2. 效率与优化

技巧：

• 选择合适的数据结构：根据操作的频率和类型（如查找、插入、删除）选择最合适的数据结构。
• 减少冗余计算：避免重复计算，通过缓存（如动态规划中的记忆化）来提高效率。
• 使用空间换时间：在某些情况下，通过增加一些额外的存储空间可以显著提高时间效率。

举例：在动态规划中，通过保存子问题的解来避免重复计算，从而降低时间复杂度。

3. 数据结构与算法

技巧：

• 熟悉常用数据结构：如数组、链表、栈、队列、树、图、哈希表等，了解它们的特性和适用场景。
• 掌握经典算法：如排序、搜索、动态规划、贪心算法、回溯等，理解它们的实现和优化。

举例：对于频繁查找操作，优先考虑使用哈希表或二分搜索树。

4. 迭代与递归

技巧：

• 优先选择迭代：在大多数情况下，迭代比递归更高效且更容易控制栈空间。
• 优化递归：如果必须使用递归，考虑使用尾递归或将递归转换为迭代。

举例：斐波那契数列的计算可以使用迭代替代递归，从而避免栈溢出。

5. 模块化与可维护性

技巧：

• 单一职责：每个函数和模块应该只做一件事，这样可以提高代码的可读性和可维护性。
• 松耦合：模块之间的依赖关系应该尽量简单，减少耦合度，使得更容易进行修改和维护。

举例：将输入处理、数据处理、输出结果分成不同的函数或模块。

6. 预处理与后处理

技巧：

• 提前准备：在主算法运行前，进行必要的数据预处理，可以显著提高整体效率。
• 整理结果：在主算法运行后，对结果进行格式化或整理，使其更易于使用和理解。

举例：在字符串匹配问题中，预先构建一个模式表来加速匹配过程。

7. 单一职责原则

技巧：

• 功能分离：确保每个函数或模块只负责一个功能，尽量避免“大而全”的函数。
• 明确接口：定义清晰的接口，使得模块之间的交互简单明了。

举例：一个计算器程序，应该将输入解析、运算处理、结果输出分成不同的模块。

8. 测试与验证

技巧：

• 全面测试：编写覆盖各种边界情况和特殊情况的测试用例，确保代码的健壮性。
• 自动化测试：使用单元测试框架（如JUnit、pytest）来自动化测试过程，提高效率。

举例：对于每个函数，编写一组测试用例，包括正常输入、边界输入和异常输入。

综合应用

综合技巧：

• 问题分解：将复杂的问题分解成多个小问题，通过组合这些小问题的解来解决整体问题。
• 多角度思考：从不同的角度（如时间复杂度、空间复杂度、代码可维护性）来思考和优化代码。
• 不断学习：保持对新技术、新算法的学习热情，丰富自己的工具箱。

举例：在面对一个新的编程挑战时，可以先尝试简单的暴力解法，然后通过优化数据结构和算法来逐步提升性能。

通过这些技巧和思路，不仅可以提高解决当前问题的效率，还能在面对新问题时举一反三，找到更加高效和优雅的解决方案。

---