自学做网站多长时间,给wordpress添加背景音乐,淘宝优惠券网站怎么做的,如何套用别人网站模板文章目录 一、实战概述二、实战步骤#xff08;一#xff09;逐个比较法1、编写源程序2、代码解释说明#xff08;1#xff09;函数逻辑解释#xff08;2#xff09;主程序部分 3、运行程序#xff0c;查看结果4、计算时间复杂度 #xff08;二#xff09;排序比较法1… 文章目录 一、实战概述二、实战步骤一逐个比较法1、编写源程序2、代码解释说明1函数逻辑解释2主程序部分 3、运行程序查看结果4、计算时间复杂度 二排序比较法1、编写源程序2、代码解释说明1 函数逻辑解释2主程序部分 3、运行程序查看结果4、计算时间复杂度 三计数比较法1、编写源程序2、代码解释说明1函数逻辑解释2主程序部分 3、运行程序查看结果4、计算时间复杂度 四相互包含法1、编写源程序2、代码解释说明1函数逻辑解释2主程序部分 3、运行程序查看结果4、计算时间复杂度 五强力法 三、实战总结 一、实战概述 本实战通过编写四个Python程序分别采用逐个比较法、排序比较法、计数比较法和相互包含法来解决变位词检测问题。逐个比较法的时间复杂度为 O ( n 2 ) \text{O}(n^2) O(n2)虽然实现简单但效率较低排序比较法则利用字符串排序后直接比较时间复杂度为 O ( n l o g n ) \text{O}(n log n) O(nlogn)效率相对较高计数比较法则统计字符出现次数进行对比时间复杂度为 O ( n ) \text{O}(n) O(n)是四种方法中最高效的而相互包含法则分别检查两个字符串中的字符是否完全包含对方时间复杂度为 O ( n ∗ m ) \text{O}(n*m) O(n∗m)。 在实际应用中针对不同的场景需求和输入规模可选择合适的算法以达到时间和空间效率的最佳平衡。例如在处理大规模字符串时计数比较法更优而在较小规模或对内存有限制的场景下排序比较法可能是更好的选择。同时强力法由于其极高的时间复杂度 n ! n! n!不适用于实际问题求解。
二、实战步骤
一逐个比较法
1、编写源程序
编写Python程序 - 变位词侦测问题解法01-逐个比较法.py 功能变位词侦测问题解法01-逐个比较法
作者华卫
日期2024年01月13日
def anagramSolution1(s1, s2):stillOK Trueif len(s1) ! len(s2):stillOK Falsealist list(s2)pos1 0while pos1 len(s1) and stillOK:pos2 0found Falsewhile pos2 len(alist) and not found:if s1[pos1] alist[pos2]:found Trueelse:pos2 pos2 1if found:alist.pop(pos2)else:stillOK Falsepos1 pos1 1return stillOKstr1 input(Input the first string: )
str2 input(Input the second string: )
if anagramSolution1(str1, str2):print(str1, and, str2, are anagrams.)
else:print(str1, and, str2, are not anagrams.)2、代码解释说明
这段代码实现了一个名为anagramSolution1的函数用于检测两个输入字符串s1和s2是否为变位词。
1函数逻辑解释 函数首先检查两个字符串的长度是否相等如果不等则直接返回False表示它们不是变位词。 将第二个字符串s2转换为字符列表alist便于进行元素操作。 使用变量pos1遍历第一个字符串s1的每个字符。 a. 初始化一个布尔变量found为False用于记录当前字符是否在alist中找到。 b. 对于s1中的每个字符使用pos2遍历alist寻找匹配项。 如果找到匹配项即s1[pos1] alist[pos2]将found设为True并跳出内层循环。 否则将pos2加1继续搜索下一个字符。 c. 如果找到了匹配项从alist中移除该字符alist.pop(pos2)否则将stillOK设为False表示无法构成变位词。 d. 将pos1递增准备处理下一个字符。 当遍历完s1的所有字符且stillOK仍为True时说明s1与s2是变位词函数返回True否则返回False。
2主程序部分 通过input()获取用户输入的两个字符串str1和str2。 调用anagramSolution1(str1, str2)函数判断这两个字符串是否为变位词。 根据函数返回的结果输出相应的信息如果两个字符串是变位词则输出str1 and str2 are anagrams.“否则输出str1 and str2 are not anagrams.”。
3、运行程序查看结果
运行两次程序第一次是同位词第二次不是同位词
4、计算时间复杂度 此程序的时间复杂度为 O ( n 2 ) \text{O}(n^2) O(n2)其中n代表输入字符串s1和s2的长度假设它们是等长的。 首先检查两个字符串长度时间复杂度为 O ( 1 ) \text{O}(1) O(1)。 将字符串s2转换为列表alist时间复杂度为 O ( n ) \text{O}(n) O(n)。 使用两层循环进行逐个字符比较 外层循环遍历字符串s1次数为n时间复杂度为 O ( n ) \text{O}(n) O(n)。内层循环在每一轮外层循环中遍历alist寻找匹配项最坏情况下需要遍历整个alist次数也为n因此内层循环的时间复杂度为 O ( n ) \text{O}(n) O(n)。因此总的时间复杂度为 O ( n ∗ n ) \text{O}(n*n) O(n∗n)即 O ( n 2 ) \text{O}(n^2) O(n2)。 此外在内层循环找到匹配项后执行的alist.pop(pos2)操作虽然在Python中平均时间复杂度为 O ( n ) \text{O}(n) O(n)但在实际应用中由于每次找到一个匹配项就移除一个元素其对于整体时间复杂度的影响可以忽略不计所以整体时间复杂度仍视为 O ( n 2 ) \text{O}(n^2) O(n2)。 T ( n ) ∑ i 1 n n ( n 1 ) 2 ≈ O ( n 2 ) \displaystyle \text{T}(n)\sum_{i1}^n\frac{n(n1)}{2}\approx \text{O}(n^2) T(n)i1∑n2n(n1)≈O(n2)
二排序比较法
1、编写源程序
编写Python程序 - 变位词侦测问题解法02-排序比较法.py 功能变位词侦测问题解法02-排序比较法
作者华卫
日期2024年01月13日
def anagramSolution2(s1,s2):alist1 list(s1)alist2 list(s2)alist1.sort()alist2.sort()pos 0matches Truewhile pos len(s1) and matches:if alist1[pos] alist2[pos]:pos pos 1else:matches Falsereturn matchesstr1 input(Input the first string: )
str2 input(Input the second string: )
if anagramSolution2(str1, str2):print(str1, and, str2, are anagrams.)
else:print(str1, and, str2, are not anagrams.)2、代码解释说明
这段代码实现了一个名为anagramSolution2的函数用于检测两个输入字符串s1和s2是否为变位词。
1 函数逻辑解释 首先将输入的两个字符串s1和s2分别转换为字符列表alist1和alist2。 对这两个字符列表进行排序操作排序后的列表中相同的字符将会按照字典序排列到一起。 初始化一个变量pos为0表示当前比较的位置同时初始化布尔值matches为True用以记录是否所有对应位置的字符都匹配成功。 使用while循环遍历两个已排序的字符列表直到遍历完其中一个列表或发现不匹配为止 如果在相同位置上的字符相等即alist1[pos] alist2[pos]则将pos加1继续比较下一个字符。否则将matches设置为False跳出循环。 循环结束后根据matches的值判断两个字符串是否为变位词 若matches为True则说明原字符串s1和s2是变位词返回True。若matches为False则说明它们不是变位词返回False。
2主程序部分 通过input()获取用户输入的两个字符串str1和str2。 调用anagramSolution2(str1, str2)函数判断这两个字符串是否为变位词。 根据函数返回的结果输出相应的信息如果两个字符串是变位词则输出str1 and str2 are anagrams.“否则输出str1 and str2 are not anagrams.”。
3、运行程序查看结果
运行两次程序第一次是同位词第二次不是同位词
4、计算时间复杂度
此程序的时间复杂度主要由两部分组成 排序操作对输入字符串s1和s2转换成的字符列表alist1和alist2进行排序。Python内置的sort()方法采用Timsort算法其平均时间复杂度为 O ( n l o g n ) \text{O}(n log n) O(nlogn)其中 n n n为列表长度即字符串长度。 遍历比较操作在排序后的字符列表中通过一个while循环逐个比较对应位置的字符是否相等该过程的时间复杂度为 O ( n ) \text{O}(n) O(n)。
因此整个程序的时间复杂度为 O ( n l o g n ) O ( n ) O ( n l o g n ) \text{O}(n log n) \text{O}(n) \text{O}(n log n) O(nlogn)O(n)O(nlogn)其中主要的时间消耗在于排序阶段。不过在实际情况中由于遍历比较阶段总是紧跟在排序阶段之后并且只执行一次所以整体的时间复杂度通常简记为 O ( n l o g n ) \text{O}(n log n) O(nlogn)。
三计数比较法
1、编写源程序
编写Python程序 - 变位词侦测问题解法03-计数比较法.py 功能变位词侦测问题解法03-计数比较法
作者华卫
日期2024年01月13日
def anagramSolution4(s1, s2):c1 [0] * 26c2 [0] * 26for i in range(len(s1)):pos ord(s1[i]) - ord(a)c1[pos] c1[pos] 1for i in range(len(s2)):pos ord(s2[i]) - ord(a)c2[pos] c2[pos] 1j 0stillOK Truewhile j 26 and stillOK:if c1[j] c2[j]:j j 1else:stillOK Falsereturn stillOKstr1 input(Input the first string: )
str2 input(Input the second string: )
if anagramSolution4(str1, str2):print(str1, and, str2, are anagrams.)
else:print(str1, and, str2, are not anagrams.)2、代码解释说明
这段代码实现了一个名为anagramSolution4的函数用于检测两个输入字符串s1和s2是否为变位词。该方法采用计数比较法统计每个字符串中各字符出现的次数并进行比较。
1函数逻辑解释 初始化两个长度为26的计数列表c1和c2分别用于记录字符串s1和s2中小写字母的出现次数。这里假设输入字符串仅包含小写字母。 对于字符串s1中的每一个字符 计算其在字母表中的位置通过ord(s1[i]) - ord(a)得到将字符转换为其ASCII值并减去’a’的ASCII值。将对应位置的计数加1。 同样对字符串s2执行相同的操作更新计数列表c2。 初始化一个变量j为0表示当前正在检查的小写字母的位置以及一个布尔值stillOK初始值为True表示目前所有已检查的字符计数都相等。 使用while循环遍历26个小写字母如果在对应的索引位置上c1[j]与c2[j]相等则继续检查下一个字母否则将stillOK设置为False跳出循环。 循环结束后根据stillOK的值判断两个字符串是否为变位词 若stillOK仍为True说明原字符串s1和s2是变位词返回True。若stillOK变为False则说明它们不是变位词返回False。
2主程序部分 通过input()获取用户输入的两个字符串str1和str2。 调用anagramSolution4(str1, str2)函数判断这两个字符串是否为变位词。 根据函数返回的结果输出相应的信息如果两个字符串是变位词则输出str1 and str2 are anagrams.“否则输出str1 and str2 are not anagrams.”。
3、运行程序查看结果
运行两次程序第一次是同位词第二次不是同位词
4、计算时间复杂度 此程序的时间复杂度为 O ( n ) \text{O}(n) O(n)其中 n n n表示输入字符串的长度。 在函数anagramSolution4中首先初始化了两个长度为26的列表c1和c2时间复杂度为 O ( 1 ) \text{O}(1) O(1)。 然后对s1中的每个字符进行遍历计算其在字母表中的位置并增加相应计数循环次数为n假设字符串仅包含小写字母时间复杂度为 O ( n ) \text{O}(n) O(n)。 同样地对s2中的每个字符执行相同的操作时间复杂度也为 O ( n ) \text{O}(n) O(n)。 最后通过一个while循环比较两个计数列表是否相等循环最多会进行26次对于所有可能的小写字母因此这一部分的时间复杂度是 O ( 1 ) \text{O}(1) O(1)级别的。 综合上述步骤整个程序的主要时间消耗在于遍历字符串并统计字符出现次数的部分故总时间复杂度为 O ( n ) \text{O}(n) O(n)。同时由于空间上只使用了固定大小的计数数组所以空间复杂度为 O ( 1 ) \text{O}(1) O(1)。
四相互包含法
1、编写源程序
编写Python程序 - 变位词侦测问题解法04-相互包含法.py 功能变位词侦测问题解法04-相互包含法
作者华卫
日期2024年01月13日
def anagramSolution5(s1, s2):stillOK Truefor i in range(len(s1)):if s1[i] not in s2:stillOK Falsebreakif stillOK:for i in range(len(s2)):if s2[i] not in s1:stillOK Falsebreakreturn stillOKstr1 input(Input the first string: )
str2 input(Input the second string: )
if anagramSolution5(str1, str2):print(str1, and, str2, are anagrams.)
else:print(str1, and, str2, are not anagrams.)2、代码解释说明
这段代码实现了一个名为anagramSolution5的函数用于检测两个输入字符串s1和s2是否为变位词。该方法采用了相互包含法即检查一个字符串中的每个字符是否都出现在另一个字符串中。
1函数逻辑解释 初始化一个布尔变量stillOK为True表示在没有发现不匹配字符的情况下两个字符串可能是变位词。 使用一个for循环遍历字符串s1中的每个字符 如果当前字符不在字符串s2中则将stillOK设为False并使用break语句跳出循环。这意味着s1中存在s2中没有的字符因此它们不是变位词。 当遍历完s1后如果stillOK仍为True则继续对字符串s2进行相同的操作 用另一个for循环遍历s2中的每个字符。如果当前字符不在字符串s1中则将stillOK设为False并同样使用break语句跳出循环。这意味着s2中也存在s1中没有的字符因此它们不是变位词。 在完成所有检查后返回stillOK的值。若为True说明两个字符串是变位词否则它们不是变位词。
2主程序部分 通过input()获取用户输入的两个字符串str1和str2。 调用anagramSolution5(str1, str2)函数判断这两个字符串是否为变位词。 根据函数返回的结果输出相应的信息如果两个字符串是变位词则输出str1 and str2 are anagrams.“否则输出str1 and str2 are not anagrams.”。
3、运行程序查看结果
运行两次程序第一次是同位词第二次不是同位词
4、计算时间复杂度 此程序的时间复杂度为 O ( n ∗ m ) \text{O}(n*m) O(n∗m)其中 n n n和 m m m分别为输入字符串s1和s2的长度。 在函数anagramSolution5中首先遍历字符串s1对每个字符执行一次查找操作即s1[i] not in s2这需要在字符串s2中进行线性搜索。最坏情况下对于每个字符都需要遍历整个s2因此这部分时间复杂度为 O ( m ) \text{O}(m) O(m)。 如果s1中的所有字符都在s2中找到则继续遍历字符串s2再次对每个字符执行查找操作即s2[i] not in s1。同样地这部分在最坏情况下也具有 O ( n ) \text{O}(n) O(n)的时间复杂度。 因此总时间复杂度为这两部分之和即 O ( n m ) \text{O}(nm) O(nm)由于两者均与输入字符串的长度相关且相互独立我们可以将其简化为 O ( n ∗ m ) \text{O}(n*m) O(n∗m)表示随着两个字符串长度同时增加时程序运行时间的增长趋势。
五强力法
强力法采用穷尽所有可能性的方式来处理问题。对于长度为n的字符串s1全排列得到所有字符串然后去看s2是否出现在s1全排列后构成的字符串列表里。 T ( n ) n × ( n − 1 ) × ( n − 2 ) × . . . . × 2 × 1 n ! T(n)n\times(n-1)\times(n-2)\times....\times2\times1 n! T(n)n×(n−1)×(n−2)×....×2×1n!, n ! n! n!跑得比 2 n 2^n 2n还要快得多比如 20 ! 2432902008176640000 20! 2432902008176640000 20!2432902008176640000。如果每秒钟处理一种可能性那么要花 77 , 146 , 816 , 596 77,146,816,596 77,146,816,596年才能遍历整个列表。显然不是一个好的解决方案。
三、实战总结
实战中我们运用四种不同策略检测变位词逐个比较法 O ( n 2 ) \text{O}(n^2) O(n2)、排序比较法 O ( n l o g n ) \text{O}(n log n) O(nlogn)、计数比较法 O ( n ) \text{O}(n) O(n)和相互包含法 O ( n ∗ m ) \text{O}(n*m) O(n∗m)。其中计数比较法效率最高适合大规模字符串排序比较法则在小规模数据或对内存有限制时适用。通过实践对比理解并掌握了针对不同场景选择合适算法的重要性。
