投其所好陪小孩学习

小码匠每天回来最开心的事就是刷道题，小孩不太喜欢看理论性很强的东西，太枯燥了。

我买了一本《算法设计》，本来想让小码匠看，拿到书，我翻了几页，就果断放弃了。

还是自己抽时间看，然后把比较枯燥的知识点想办法转化成比较有意思的知识，这样小码匠更容易接受。

回到正题，今天小码匠刚到家。

开始安排功课

老码农：今天作业多吗？

小码匠：有一点，20分钟能完成。

老码农：那咱们老五样

 

（基本每天都在重复这几件事，每天都很开心）

如何？

小码匠：OK，那我去写了啊

20分钟后，小码匠顺利写完作业。双减之后，的确爽了不少，可以有更多的时间一起学编程，和小孩沟通。

小码匠：我休息10分钟，吃个苹果就过来哈。

老码农：嗯，去吧。

开始

老码农：今天的题目也不难，但咱们不要为了做题而做题，争取做一道题，搞明白一道。

小码匠：好嘞，你先说题目吧。

老码农：题目是这样的。

题目：有效的字母异位词

地址：力扣

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

提示:

• 1 <= s.length, t.length <= 5 * 104

• s 和 t 仅包含小写字母

老码农：题目能看懂吗？

小码匠：我语文又不差，当然看的懂

老码农：那你先自己编，我去看会书，编写完了叫我。

小码匠：OK

小码匠的习惯就是不会直接写代码，先思考，然后大致想明白了，再动手编代码。

一会，听到小码匠一阵噼里啪啦声，呼叫老码农。

小码匠：我编好了，是挺简单的。

def isAnagram(s: str, t: str) -> bool:new_t = list(t)new_s = list(s)new_t.sort()new_s.sort()if new_s == new_t:return Trueelse:return False

老码农：看代码估计没什么问题，你测试了吗？

小码匠：测试不通过敢叫你过来看啊，要不然啊，你又该啰嗦我缺乏工匠精神了。

老码农：那你跑下，我看看结果。

if __name__ == "__main__":print(isAnagram("anagram", "nagaram"))print(isAnagram("rat", "car"))print(isAnagram("rate", "tear"))print(isAnagram("ratre", "tear"))

小码匠轻点【Run】按钮，结果如下。

/Users/cynthia/opt/miniconda3/envs/coder/bin/python 
/coder-algorithm/algorithm/strings/anagram.py
True
False
True
False
​
Process finished with exit code 0

老码农：运行正确。你有没有考虑过其他解决方案啊。

第一次提交

小码匠：我是没想到特别好的方式，反正我就是先排序，然后比较值是不是一样。

小码匠：咱们先提交呗。

老码农：真的现在就提交吗？

小码匠：那当然。

leetcode242-01

leetcode242-02

老码农：数据有点尴尬啊

• 内存消耗：超过13%选手

• 用时消耗：超过9%选手

小码匠：这……这不科学啊，难道还能有什么更好的解决办法吗？

老码农：你先分析一下代码吧，

• 创建了2个新列表对象

• 又做了2次sort处理

内存消耗和用时消耗肯定有点高啊。

小码匠：唔……那我再想想吧。

第二个方案：更悲剧

小码匠：我用sorted试试，代码很简洁，不知道效率如何。

小码匠噼里啪啦，先删又敲了一行代码。

def isAnagram2(s: str, t: str) -> bool:return sorted(s) == sorted(t)

小码匠：我提交吧。

老码农：你，你，提交吧。

leetcode242-03

leetcode242-04

老码农：看你猴急的，这回也挺惨的

• 消耗内存：超过19%选手

• 用时：超过63%的选手

总算比上次好些，但有限啊

小码匠：这个，这个，我的代码够简洁的了，性能还这么差。

老码农：知道为啥吗？还记得我给你留过一道题吗？

• list.sort和sorted的区别吗？

小码匠：是有点印象，咋啦？

老码农：你真是气人，我给你安排的作业都不好好做，现在去查然后告诉我结果

小码匠：哎，好吧。

小码匠打开谷歌浏览器，打开了菜鸟教程。

小码匠：

• list.sort()不创建新对象，直接在原来对象上排序。

• sorted是创建一个新对象，排序结果放到新对象中。

哎，又是创建新对像，怪不得耗时这块还是那么糟糕呢。

老码农：继续再想想，相信你能解决的。

小码匠托起小腮帮，开始了思考。

第三个方案

小码匠：老码农，我实在想不出来更好的方案了，我的方案也都是需要循环，估计性能也不好。

老码农：还思考不，放弃了，我们就看看官方解答。

小码匠：放弃吧，看看官方吧。

官方地址：力扣

老码农：我们来分析下官方的解答吧。

小码匠：嗯，好

• 方法一：跟我的是一样的，只是他是用Java实现的，

• 方法二：哈希表，我看看代码。

看了一分钟，小码匠大呼一声，我明白了。

• 他是先创建一个Hash表

• 然后循环第一个串计算每个字符的出现次数

• 然后循环第二个串，减去每个字符串出现次数，如果有小于0的，就说明第二个字符串中出现的字符在第一个中没有。

小码匠：咋没有Python的实现方式啊？

leetcode242-05

老码农：等你来写的呢呗，你用Python写下吧。

小码匠：好的吧。

小码匠有些不情愿，还是噼里啪啦敲起了键盘。

def isAnagram3(s: str, t: str) -> bool:x = [0] * 26s = s.lower()t = t.lower()for i in s:x[ord(i) - ord('a')] = x[ord(i) - ord('a')] + 1for j in t:if (x[ord(j) - ord('a')] - 1) < 0:return Falsex[ord(j) - ord('a')] = x[ord(j) - ord('a')] - 1return x.count(0) == 26

老码农：我们再Run一次，这次估计不仅成绩能提高，而且时间复杂度和空间复杂度都小了。

小码匠：好，走起，提交。

老码农：这回不错

• 用时：超过62%选手

• 内存：超过72%选手

小码匠：官方的解答成绩也不太理想啊，才超过这么多选手。这个时间和空间复杂度都有降低的啊。

老码农：应该还有更好的解决方案，真相是需要你不断追寻才能一步一步逼进的。

小码匠：可我真的想不出来更好的解决方案了。

老码农：我记得有个库也是统计次数的。我想想啊。

第四个方案

老码农：我想起来了，你查查Counter这个库，是Python里面的一个计数器类。

小码匠：我不想弄了，都过去一个小时了，我歇会好不啊。

老码农：在调研下吧，以你的小脑袋瓜，很快就解决了，搞到半道就跑了，不是你的风格啊。

小码匠：嗯，我去查查官方资料吧。

“

地址：collections — Container datatypes — Python 3.8.12 documentation

”

leetcode242-06

老码农：真棒，加油！

小码匠又是一阵噼里啪啦，代码呈现如下。

def isAnagram(s: str, t: str) -> bool:from collections import Counters_count = Counter(s)t_count = Counter(t)return s_count == t_count

小码匠轻点【Run】，本地测试通过。开始又一次提交，

leetcode242-07

leetcode242-08

• 用时：超过89%选手

• 内存：超过51%选手

老码农：今天就到这里吧。

小码匠：嗯，那我去看10分钟柯南了啊。

老码农：又忘了吧。还差最后一项，总结下今天所学内容。

小码匠：哦。

总结

• list.sort()和sorted区别

  • list.sort()不创建新对象，直接在原来对象上排序。

  • sorted是创建一个新对象，排序结果放到新对象中。

• 创建对象时直接初始化大小

  x = [0] * 26

• 学习了新库的使用方法：Counter

  • collections — Container datatypes — Python 3.8.12 documentation

• 字符串灵活运用方式

老码农说

学习算法的路上没有捷径

每天坚持写代码

每天坚持先自己思考，然后写代码，不要一上来就去看题解

每一道题都力所能及追求极致

每一道题都关注他人是否有更好的解决方案

不要为了刷题而刷题，我们获取的是真知识

关注公众号【小码匠和老码农】收获小码匠和老码农精心挑选的电子书

• 回复: java, 获得Java基础教程
• 回复: jvm, 获得JVM资料
• 回复: springboot, 获得SpringBoot资料
• 回复: springcloud, 获得springcloud资料
• 回复: python, 获得Python资料
• 回复: 算法, 获得算法资料