关于后端:一道超简单的Leetcode242异位词耗时1小时能学到什么

投其所好陪小孩学习

小码匠每天回来最开心的事就是刷道题，小孩不太喜爱看理论性很强的货色，太干燥了。

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

还是本人抽时间看，而后把比拟 干燥的知识点想方法转化成比拟有意思的常识，这样小码匠更容易接受。

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

开始安顿功课

老码农：明天作业多吗？

小码匠：有一点，20 分钟能实现。

老码农：那咱们老五样

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

如何？

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

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

小码匠：我劳动 10 分钟，吃个苹果就过去哈。

老码农：嗯，去吧。

开始

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

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

老码农：题目是这样的。

题目：无效的字母异位词

地址：https://leetcode-cn.com/probl…

给定两个字符串 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 True
    else:
        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 是创立一个新对象，排序后果放到新对象中。

哎，又是创立新对像，怪不得耗时这块还是那么蹩脚呢。

老码农：持续再想想，置信你能解决的。

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

第三个计划

小码匠：老码农，我切实想不进去更好的计划了，我的计划也都是须要循环，预计性能也不好。

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

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

官网地址：https://leetcode-cn.com/probl…

老码农：咱们来剖析下官网的解答吧。

小码匠：嗯，好

• 办法一：跟我的是一样的，只是他是用 Java 实现的，
• 办法二：哈希表，我看看代码。

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

• 他是先创立一个 Hash 表
• 而后循环第一个串计算每个字符的呈现次数
• 而后循环第二个串，减去每个字符串呈现次数，如果有小于 0 的，就阐明第二个字符串中呈现的字符在第一个中没有。

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

leetcode242-05

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

小码匠：好的吧。

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

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

老码农：咱们再 Run 一次，这次预计不仅问题能进步，而且工夫复杂度和空间复杂度都小了。

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

老码农：这回不错

• 用时：超过 62% 选手
• 内存：超过 72% 选手

小码匠：官网的解答问题也不太现实啊，才超过这么多选手。这个工夫和空间复杂度都有升高的啊。

老码农：应该还有更好的解决方案，假相是须要你一直追寻能力一步一步逼进的。

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

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

第四个计划

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

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

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

小码匠：嗯，我去查查官网材料吧。

“

地址：https://docs.python.org/3.8/l…

”

leetcode242-06

老码农：真棒，加油！

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

def isAnagram(s: str, t: str) -> bool:
    from collections import Counter
    s_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
• • https://docs.python.org/3.8/l…
• 字符串灵活运用形式

老码农说

学习算法的路上没有捷径

每天保持写代码

每天保持先本人思考，而后写代码，不要一上来就去看题解

每一道题都力不从心谋求极致

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

不要为了刷题而刷题，咱们获取的是真常识

关注公众号【小码匠和老码农】播种小码匠和老码农精心筛选的电子书

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