每日一题——Python实现PAT甲级1077 Kuchiguse（举一反三+思想解读+逐步优化）


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

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

Python-3.12.0文档解读

目录

我的写法

代码点评

时间复杂度分析

空间复杂度分析

总结

我要更强

方案1：利用字典树（后缀树）

优化代码（后缀树实现）

代码点评

时间复杂度分析

空间复杂度分析

方案2：水平扫描法

优化代码（水平扫描法实现）

代码点评

时间复杂度分析

空间复杂度分析

总结

哲学和编程思想

1. 字典树（Trie）方法

编程思想

哲学理念

2. 水平扫描法

编程思想

哲学理念

3. 动态编程（不在上述代码中，但也是常见的优化方法）

编程思想

哲学理念

总结

举一反三

1. 数据结构优化

2. 空间换时间

3. 递归与迭代

4. 分而治之

5. 贪心算法

6. 动态规划

总结



题目链接

我的写法

N=int(input())  # 读取一个整数N，表示有多少个字符串
strs=[]  # 创建一个空列表来存储字符串
for i in range(N):  # 循环N次
    strs.append(input()[::-1])  # 读取每个字符串并将其倒序，然后添加到列表strs中

same_end=''  # 初始化一个空字符串，用于存储相同的后缀
for i in range(min([len(s) for s in strs])):  # 找出所有字符串中最短的长度，并遍历该长度
    if len(set([strs[j][i] for j in range(N)]))==1:  # 检查所有字符串在第i个位置上的字符是否相同
        same_end+=strs[0][i]  # 如果相同，则将该字符添加到same_end中
    else:  # 如果不相同
        break  # 结束循环

if len(same_end)==0:  # 如果没有相同的后缀
    print("nai")  # 输出"nai"
else:  # 如果有相同的后缀
    print(same_end[::-1])  # 将same_end倒序输出，即得到原始的相同后缀

这段代码的功能是找到多个字符串的最长公共后缀。以下是对代码的专业点评以及时间复杂度和空间复杂度分析：

代码点评

  1. 输入处理：
    • 使用 input() 读取输入的整数 N，然后读取 N 个字符串，并将其倒序存储在列表 strs 中。这样做是为了方便从后向前逐字符比较字符串。
  2. 查找公共后缀：
    • 首先计算所有字符串的最小长度，确保不会越界。
    • 逐字符检查所有字符串在当前位是否相同，如果相同则添加到 same_end 中，否则终止检查。
  3. 结果输出：
  • 如果 same_end 为空，则输出 "nai"，表示没有公共后缀。
  • 否则将 same_end 倒序输出，即为原始字符串的公共后缀。

时间复杂度分析

因此，查找公共后缀部分的总体时间复杂度为 O(M * N)。

  1. 输入处理：
    • 读取 N 个字符串的时间复杂度是 O(N)。
    • 每个字符串的倒序操作的时间复杂度是 O(L)，其中 L 是字符串的平均长度。总体时间复杂度为 O(N * L)。
  2. 查找公共后缀：
    • 计算最小长度的时间复杂度是 O(N)。
    • 逐字符比较的时间复杂度是 O(M * N)，其中 M 是最短字符串的长度。
  3. 结果输出：
  • 输出的时间复杂度为 O(M)。

综合以上分析，总的时间复杂度为 O(N * L + M * N)，在最坏情况下 L 和 M 都可以接近最长字符串长度。

空间复杂度分析

  1. 输入处理：
    • 使用了一个列表 strs 来存储 N 个字符串，空间复杂度为 O(N * L)。
  2. 查找公共后缀：
  • 使用了一个字符串 same_end 来存储公共后缀，最坏情况的空间复杂度为 O(M)。

综合分析，空间复杂度为 O(N * L + M)。

总结

这段代码在处理字符串公共后缀问题时较为直接，逻辑清晰，步骤明确。代码的时间复杂度和空间复杂度都取决于输入字符串的数量和长度，但对于常规的输入规模，性能表现应该是合理的。优化的重点可以放在减少字符串操作的次数和改进字符串比较过程。

我要更强

在寻找多个字符串的最长公共后缀时，时间复杂度和空间复杂度的优化可以通过多种途径实现，例如避免多余的字符串操作，使用更高效的数据结构等。以下是一些可能的优化方案，并给出相应的代码和注释：

方案1：利用字典树（后缀树）

字典树（Trie）是一种高效的数据结构，特别适合字符串集合的共性处理。在这里，可以使用反向构建的后缀树来查找公共后缀。

优化代码（后缀树实现）

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        current = self.root
        for char in word:
            if char not in current.children:
                current.children[char] = TrieNode()
            current = current.children[char]
        current.is_end_of_word = True

    def longest_common_suffix(self, n):
        common_suffix = []
        current = self.root
        while len(current.children) == 1 and not current.is_end_of_word:
            (char, next_node), = current.children.items()
            common_suffix.append(char)
            current = next_node
            n -= 1
            if n == 0:
                break
        return ''.join(common_suffix)


def find_longest_common_suffix(strings):
    trie = Trie()
    for string in strings:
        trie.insert(string[::-1])
    
    return trie.longest_common_suffix(len(strings))


N = int(input())  # 读取一个整数N，表示有多少个字符串
strs = [input() for _ in range(N)]  # 读取N个字符串

result = find_longest_common_suffix(strs)

if not result:
    print("nai")
else:
    print(result[::-1])

代码点评

  1. Trie 数据结构：
    • 使用 TrieNode 类表示字典树的节点。
    • 使用 Trie 类封装字典树的插入和寻找最长公共后缀的功能。
  2. 插入字符串：
    • 将每个字符串倒序后插入字典树。
  3. 寻找公共后缀：
  • 在字典树中搜索最长的路径，路径上的字符即为最长公共后缀。

时间复杂度分析

  • 插入每个字符串的时间复杂度为 O(L)，其中 L 是字符串的长度，因此总插入时间复杂度为 O(N * L)。
  • 寻找最长公共后缀的时间复杂度为 O(M)，其中 M 是最短字符串的长度。

综合时间复杂度为 O(N * L)。

空间复杂度分析

  • 字典树节点的空间复杂度为 O(N * L)，因为每个字符都可能需要一个节点。
  • 另外，存储结果的空间复杂度为 O(M)。

综合空间复杂度为 O(N * L)。

方案2：水平扫描法

水平扫描法通过逐一比较字符串，类似于前缀匹配，但是从字符串末尾开始。

优化代码（水平扫描法实现）

def find_longest_common_suffix(strings):
    if not strings:
        return ""
    
    # 取第一个字符串作为基准
    suffix = strings[0][::-1]
    
    # 逐个比较其他字符串
    for string in strings[1:]:
        temp_suffix = ""
        rev_string = string[::-1]
        min_length = min(len(suffix), len(rev_string))
        
        # 从后向前比较字符
        for i in range(min_length):
            if suffix[i] == rev_string[i]:
                temp_suffix += suffix[i]
            else:
                break
        
        suffix = temp_suffix
        if not suffix:
            break
    
    return suffix

N = int(input())  # 读取一个整数N，表示有多少个字符串
strs = [input() for _ in range(N)]  # 读取N个字符串

result = find_longest_common_suffix(strs)

if not result:
    print("nai")
else:
    print(result[::-1])

代码点评

  1. 水平扫描：
    • 使用第一个字符串作为初始公共后缀的基准。
    • 逐一与后续字符串进行比较，更新公共后缀。
  2. 字符比较：
  • 从后向前逐字符比较，直到找到不同字符或达到最短长度。

时间复杂度分析

  • 比较每个字符串的时间复杂度为 O(M)，其中 M 是最短字符串的长度。因此总时间复杂度为 O(N * M)。

空间复杂度分析

  • 存储公共后缀的空间复杂度为 O(M)。

综合空间复杂度为 O(M)。

总结

上述优化方法在时间和空间复杂度上相比原始方案都有一定的提升。字典树（后缀树）方法在处理大量字符串时更高效，而水平扫描法实现简单且易于理解。选择哪种方法可以根据具体的应用场景和性能需求来定。

哲学和编程思想

在优化寻找多个字符串的最长公共后缀的方法时，涉及到一些重要的编程思想和哲学理念。以下是对这些思想的详细说明：

1. 字典树（Trie）方法

编程思想
  • 数据结构优化：字典树是一种特定的树结构，专门用于处理字符串集合，通过将公共前缀合并在一起，可以高效地存储和查询字符串。
  • 空间换时间：字典树在插入和查询时，花费的时间与字符串的长度呈线性关系，因此可以通过增加空间复杂度来降低时间复杂度。
  • 递归与迭代：字典树的构建和查询通常使用递归或迭代的方式来遍历各节点。
哲学理念
  • 分而治之：将问题分解为更小的子问题，通过处理这些子问题来解决整个问题。字典树通过逐层处理每个字符，实现了这一思想。
  • 高效存储与快速访问：字典树在设计上就是为了优化字符串的存储和访问，这反映了在计算机科学中追求效率的哲学理念。

2. 水平扫描法

编程思想
  • 贪心算法：每次选择当前最优的解，在这里，每次比较当前字符串的最长公共后缀并更新。
  • 迭代优化：逐步改进解决方案，通过不断迭代来优化结果。
  • 暴力搜索：尽管是优化的暴力搜索，水平扫描法还是采用了一种直接比较的方式，这是一种简单且直接的思维方式。
哲学理念
  • 最小工作原则：每一步都尽量少做工作，只比较必要的字符。这种方法避免了多余的计算和复杂的逻辑。
  • 逐步求精：通过逐步比较和更新公共后缀，从而逐渐接近最终解决方案。这种逐步优化的思想在哲学上类似于“渐进主义”。

3. 动态编程（不在上述代码中，但也是常见的优化方法）

编程思想
  • 子问题重用：将问题分解为子问题，通过记忆化或表格存储中间结果，避免重复计算。
  • 状态转移：通过状态转移方程来确定从一个状态到另一个状态的关系。
哲学理念
  • 整体与部分：整体问题的解决依赖于部分问题的解决，通过解决部分问题，逐步构建整体解决方案。
  • 平衡与优化：动态规划在时间和空间之间找到平衡，通过空间换时间来优化计算过程。

总结

通过使用不同的数据结构和算法优化，不仅提高了程序的效率，还展示了重要的编程思想和哲学理念。这些方法在计算机科学中都有广泛的应用，体现了在解决问题时对效率、简洁性和可维护性的追求。字典树方法体现了分而治之和高效存储的哲学，而水平扫描法则展示了逐步求精和贪心算法的思想。这些方法的结合，使得可以更好地理解和处理复杂的字符串问题。

举一反三

理解和应用编程思想与哲学理念，可以帮助在遇到各种编程问题时，灵活地找出高效的解决方案。以下是一些技巧，能帮助举一反三，从而更好地应对各种复杂问题：

1. 数据结构优化

技巧：

  • 学习和理解常用的数据结构（如数组、链表、栈、队列、树、图、哈希表等）的特点和适用场景。
  • 在解决问题时，首先考虑是否有合适的数据结构能简化问题或提高效率。
  • 对于特定的应用场景，考虑定制或组合多种数据结构。

举例：

  • 当处理大量字符串时，考虑使用字典树（Trie）来高效地存储和查询公共前缀或后缀。
  • 在频繁需要插入和删除操作时，选择链表而不是数组。

2. 空间换时间

技巧：

  • 当计算时间复杂度较高时，考虑使用额外的空间来存储中间结果，从而减少计算时间。
  • 使用缓存或者记忆化技术（如动态规划中的 memoization）来避免重复计算。

举例：

  • 在动态规划中，使用二维数组存储中间计算结果，优化递归问题的时间复杂度。
  • 在查找问题中，使用哈希表存储已访问节点或结果，优化查找速度。

3. 递归与迭代

技巧：

  • 理解递归和迭代的转换，当递归深度过大时尝试使用迭代来避免栈溢出。
  • 递归适用于分治法，迭代适用于需要多次重复计算的场景。

举例：

  • 使用递归实现快速排序（Quick Sort），但在递归深度可能过大时，改为使用迭代版本。
  • 通过迭代实现斐波那契数列，避免递归重复计算。

4. 分而治之

技巧：

  • 将复杂问题划分为更小的子问题，分别解决这些子问题再合并结果。
  • 使用分治法处理递归问题或大数据量的处理问题。

举例：

  • 使用归并排序（Merge Sort）将大问题拆分成小问题，再合并排序。
  • 在二分搜索中，将问题空间逐步缩小，直到找到目标。

5. 贪心算法

技巧：

  • 每一步选择当前最好（最优）的解，适用于局部最优能导致全局最优的问题。
  • 贪心算法往往简单高效，但需证明所选策略能得到全局最优解。

举例：

  • 在活动选择问题中，每次选择结束时间最早的活动。
  • 在找零问题中，每次选择面值最大的硬币。

6. 动态规划

技巧：

  • 识别问题的子结构，将问题分解为子问题，通过存储子问题的解来避免重复计算。
  • 使用表格法或记忆化技术存储子问题的解，优化计算过程。

举例：

  • 在背包问题中，使用二维数组存储每个容量和物品组合的最优解。
  • 在最长公共子序列问题中，构建二维表格来存储子序列的长度。

总结

通过灵活运用数据结构优化、空间换时间、递归与迭代、分而治之、贪心算法和动态规划等编程思想，可以更高效地解决各种复杂问题。在面对新的问题时，尝试识别其性质，寻找合适的编程思想和数据结构，从而设计出高效的解决方案。多练习和多思考，将这些技巧内化为自己的编程习惯，就能举一反三，游刃有余地解决各种编程挑战。

感谢支持。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/693091.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

C语言 | Leetcode C语言题解之第140题单词拆分II

C语言 | Leetcode C语言题解之第140题单词拆分II

题目&#xff1a; 题解&#xff1a; struct Trie {int ch[26];bool flag; } trie[10001];int size;void insert(char* s, int sSize) {int add 0;for (int i 0; i < sSize; i) {int x s[i] - a;if (trie[add].ch[x] 0) {trie[add].ch[x] size;memset(trie[size].ch, 0…
阅读更多...
mnist的t-SNE二维空间可视化MATLAB

mnist的t-SNE二维空间可视化MATLAB

%% filename ‘mnist’; digitDatasetPath fullfile(matlabroot,‘toolbox’,‘nnet’,‘nndemos’, … ‘nndatasets’,‘DigitDataset’); imds imageDatastore(digitDatasetPath, … ‘IncludeSubfolders’,true,‘LabelSource’,‘foldernames’); %% labelCount coun…
阅读更多...
Django redirect()函数实现页面重定向

Django redirect()函数实现页面重定向

1&#xff0c;通过路由反向解析进行重定向 1.1 添加视图函数 myshop/app2/views.py from django.http import HttpResponse from django.shortcuts import render from django.urls import reverse def index(request):return HttpResponse("app2 的index")# 反向…
阅读更多...
simulink中显示模块中的名字

simulink中显示模块中的名字

simulink/matlab version: R2022a 改动前&#xff1a;X那里没有显示名字&#xff1b; 改动方法&#xff1a; 1&#xff09;鼠标左键点击待显示模块&#xff1b; 2&#xff09;菜单栏新增 模块这个选项&#xff1b; 3&#xff09;点击自动名称&#xff1b; 4) 点击名称打开…
阅读更多...
SpringBoot+Vue企业客户管理系统（前后端分离）

SpringBoot+Vue企业客户管理系统（前后端分离）

技术栈 JavaSpringBootMavenMySQLMyBatisVueShiroElement-UI 角色对应功能 员工管理员 功能截图
阅读更多...
字节开源Hyper-SD模型，超越SDXL-Lightning，单步生成SOTA级图像

字节开源Hyper-SD模型，超越SDXL-Lightning，单步生成SOTA级图像

前言 近年来&#xff0c;扩散模型&#xff08;Diffusion Model&#xff0c;DM&#xff09;在图像生成领域取得了显著进展&#xff0c;展现出前所未有的图像质量和多样性。然而&#xff0c;扩散模型的训练和推理过程通常需要多个步骤&#xff0c;这限制了其在实际应用中的效率。…
阅读更多...
【HarmonyOS】放大缩小手势实现

【HarmonyOS】放大缩小手势实现

【HarmonyOS】放大缩小手势实现 一、鸿蒙中手势的类型&#xff1a; 对于放大缩小手势&#xff0c;在应用开发中使用较为常见&#xff0c;例如预览图片时&#xff0c;扫码时等。 在鸿蒙中对于常见的手势进行的封装&#xff0c;可以通过简单的API进行监听调用&#xff0c;以下是…
阅读更多...
【STM32】ucOS-III多任务程序

【STM32】ucOS-III多任务程序

【STM32】uc/OS-III多任务程序 文章目录 【STM32】uc/OS-III多任务程序STM32F103C8T6移植uC/OS-III基于HAL库超完整详细过程与相关实验实验任务实验过程一、 uC/OS-III源码下载二、 建立STM32CubeMX工程三、 复制uC/OS-III文件到工程文件夹四、 添加工程组件和头文件路径五、修…
阅读更多...
如何在恢复出厂设置后从 Android 恢复照片

如何在恢复出厂设置后从 Android 恢复照片

在某些情况下&#xff0c;您可能会考虑将 Android 设备恢复出厂设置。需要注意的是&#xff0c;恢复出厂设置后&#xff0c;所有设置、用户数据甚至应用程序数据都将被清除。因此&#xff0c;如果您将 Android 设备恢复出厂设置&#xff0c;甚至在里面留下了一些珍贵的照片&…
阅读更多...
Java开发-面试题-0005-==和String的equals()和String的intern()方法的区别

Java开发-面试题-0005-==和String的equals()和String的intern()方法的区别

Java开发-面试题-0005-和String的equals()和String的intern()方法的区别 更多内容欢迎关注我&#xff08;持续更新中&#xff0c;欢迎Star✨&#xff09; Github&#xff1a;CodeZeng1998/Java-Developer-Work-Note 技术公众号&#xff1a;CodeZeng1998&#xff08;纯纯技术…
阅读更多...
程序猿大战Python——运算符

程序猿大战Python——运算符

常见的运算符 目标&#xff1a;了解Python中常见的运算符有哪些&#xff1f; 运算符是用于执行程序代码的操作运算。常见的运算符有&#xff1a; &#xff08;1&#xff09;算术运算符&#xff1a;、-、*、/、//、% 、**&#xff1b; &#xff08;2&#xff09;赋值运算符&am…
阅读更多...
MinIO 分布式文件系统 快速入门 这篇就够了

MinIO 分布式文件系统 快速入门 这篇就够了

1.MinIO简介 MinIO 是一个开源的对象存储服务&#xff0c;它提供了一个可扩展的分布式文件系统&#xff0c;用于存储和检索任意类型的数据。MinIO 旨在为云原生应用程序提供快速、可靠和成本效益高的存储服务&#xff0c;并支持多种数据格式和协议&#xff0c;如Amazon S3 API。…
阅读更多...
Java 语言概述 -- Java 语言的介绍、现在、过去与将来

Java 语言概述 -- Java 语言的介绍、现在、过去与将来

大家好&#xff0c;我是栗筝i&#xff0c;这篇文章是我的 “栗筝i 的 Java 技术栈” 专栏的第 001 篇文章&#xff0c;在 “栗筝i 的 Java 技术栈” 这个专栏中我会持续为大家更新 Java 技术相关全套技术栈内容。专栏的主要目标是已经有一定 Java 开发经验&#xff0c;并希望进…
阅读更多...
《软件定义安全》之一：SDN和NFV：下一代网络的变革

《软件定义安全》之一：SDN和NFV：下一代网络的变革

第1章 SDN和NFV&#xff1a;下一代网络的变革 1.什么是SDN和NFV 1.1 SDN/NFV的体系结构 SDN SDN的体系结构可以分为3层&#xff1a; 基础设施层由经过资源抽象的网络设备组成&#xff0c;仅实现网络转发等数据平面的功能&#xff0c;不包含或仅包含有限的控制平面的功能。…
阅读更多...
华为防火墙 1

华为防火墙 1

华为防火墙1 实验拓扑&#xff1a; 实验步骤&#xff1a; 1.完成终端基本IP信息配置 2.配置防火墙&#xff1a; 2.1配置IP地址 sys Enter system view, return user view with CtrlZ. [USG6000V1]undo in e Info: Saving log files… Info: Information center is disabled. […
阅读更多...
Spark 性能调优——分布式计算

Spark 性能调优——分布式计算

前言 分布式计算的精髓&#xff0c;在于如何把抽象的计算流图&#xff0c;转化为实实在在的分布式计算任务&#xff0c;然后以并行计算的方式交付执行。今天这一讲&#xff0c;我们就来聊一聊&#xff0c;Spark 是如何实现分布式计算的。分布式计算的实现&#xff0c;离不开两个…
阅读更多...
详解SM3算法加密流程（SM3加密算法一）

详解SM3算法加密流程（SM3加密算法一）

1、SM3 算法简介 SM3是中国国家密码管理局发布的消息摘要算法&#xff0c;首次发布于2010年&#xff0c;并于2016年发布了正式的国家标准GB/T 32905-2016。类似于国际上广泛应用的SHA-256算法&#xff0c;但有其独特的设计和实现细节。 该算法应用于各种数据加密和验证场景&…
阅读更多...
vs - vs2015编译gtest-v1.12.1

vs - vs2015编译gtest-v1.12.1

文章目录 vs - vs2015编译gtest-v1.12.1概述点评笔记将工程迁出到本地后&#xff0c;如果已经编译过工程&#xff0c;将工程Revert, Clean up 干净。编译用的CMake, 优先用VS2019自带的打开VS2015X64本地命令行编译gtest工程测试安装自己写个测试工程&#xff0c;看看编译出来的…
阅读更多...
使用小黄鸟(HttpCanary)、VMOS Pro虚拟机对手机APP进行抓包（附带软件）

使用小黄鸟(HttpCanary)、VMOS Pro虚拟机对手机APP进行抓包（附带软件）

老规矩先看&#xff0c;效果图&#xff1a; 文章很详细&#xff0c;希望可以耐心看完&#xff0c;保证可以学会抓包&#xff0c;不再走冤枉路&#xff0c;小编在之前看过太多类似文章&#xff0c;折腾了太久才搞懂的&#xff0c;写这篇文章就是不想希望你们像小编一样再花时间…
阅读更多...
谁也没想到来得如此之快，现在二三线城市就有电梯楼变成贫民窟了

谁也没想到来得如此之快，现在二三线城市就有电梯楼变成贫民窟了

独家首发 ----------------- 高层电梯楼贫民窟化&#xff0c;一直是业界担忧的问题&#xff0c;许多人以为这个问题应该还要十多年时间才会成为现实&#xff0c;然而有网友表示在二三线城市已出现高层电梯楼贫民窟化&#xff0c;时间比大家预期的早得多。 该网友说&#xff0c;…
阅读更多...
最新文章

Copyright @ 2022~2023