Algorithm

【中等】49. 字母异位词分组

https://leetcode.cn/problems/group-anagrams/

题目

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

考察点

bitmap、哈希表

解法

自己的解法

很容易想到的就是把每个单词的字母排序作为 key 放到 dict 中，list 下标作为 value

class Solution:    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:        result_list = []        result_dict = {}        for s in strs:            ns = ''.join(sorted(s))            if ns in result_dict:                result_list[result_dict[ns]].append(s)            else:                result_list.append([s])                result_dict[ns] = len(result_list) - 1        return result_list

更优的解法

字母是有限的（26 个），所以可以将单词的字母通过 bitmap 的方式映射到一个整数中，用这个整数作为 dict 的 key，可以降低时间复杂度

Review

《Attention Is All You Need》

原文链接

Attention Is All You Need

概述

这里推荐一下李沐大神在 B 站对这篇论文的精读：https://www.bilibili.com/video/BV1pu411o7BE/

笔记

3 Model Architecture

这里提出来本文最核心的 Transformer 网络结构，由全连接链接 encoder 和 decoder 部分，而 encoder 和 decode 部分主要是由放缩点乘注意力机制组成。

3.1  Encoder and Decoder Stacks

 Encoder：encoder 是由 6 层组成的，每层都分为 2 个子层，第一个子层是 multi-head self-attention，第二层是位置相关的全连接网络，并使用残差连接 和 layer normalization 链接 2 个子层。要注意的是，残差连接有一个要求：输入和输出的维度必须等长。在 Transformer 中，包括所有词嵌入在内的向量长度都是 512。

Decoder：decoder 依然是 6 层，每层由多个子层组成。第一个子层是多头注意力层，准确来说，是多头自注意力。这一层可以为每一个输入单词提取出更有意义的表示。之后数据会经过前馈网络子层。最终，输出编码结果 z，得到了 z 后，要用解码器输出结果了。解码器的输入是当前已经生成的序列，该序列会经过一个掩码（masked）多头自注意力子层。

Tips

今天分享的是 SSH 端口转发，适用于网络端口被限制的情况，可以通过一台有访问权限的机器作为跳板机（代理服务）突破访问限制，具体命令格式如下：

ssh -L [收听接口:]收听端口:目标主机:目标端口 username@hostname

Share

今天分享一个记录笔记的方法：一元笔记法

所谓「一元笔记法」，便是将所有信息保存在一个可以反复翻阅的笔记本中，不做区分，这样做的好处有：

1. 简洁而简单，不会造成混乱：不需要分类思考，不用考虑生产还是摘录，不需考虑时间

2. 无压力持续使用，不需要浪费时间分类和整理，也就不需要有心理负担。不需要单独分类坚持，提高训练密度

3. 自由度高，能够随意调整：不需要考虑各个地方的限制，用一套方法记录和复习

这种不需要把信息特别严谨的分类，按照时间的排序记录的思路，被奥野宣之在《如何有效整理信息》一书中，称之为「一元笔记法」，他在纸质本子上已经实践了近 20 年，其中有三个重要原则：

原则一：一元化

一元化意思就是把想记录的一切信息，都纳入其中，无论是工作的中的创意，读过的读书笔记，还是其他任何的东西，不用经过深思熟虑，只要想记就把它记录下来。

这样是否会过于凌乱？但是反过来问问自己，把知识分类放好，这个观点是什么时候植入到脑子里的？是否有全然的道理？还只是惯性？我们大脑存储的本身就是思维的乐高块，相比分门别类放在很多不同的地方看似整齐，放在一处的好处非常明显 —— 无论何时何地，你一定找得到它。

原则二：时序化

时序化的意思就是按照时间的先后顺序，把所有的东西记录下来。

这样的日期记录，可以清楚的记录下某年某天某日发生的事，并且能够想起发生这件事的前因后果了。

我们记忆的不仅仅是一个知识点，还是许多的情境。一旦你回到某个情境，许多曾经忘记的事情会自然地浮现出来。这也是时序化比分类更易用的原因。

原则三：索引化

索引化指的并不是信息的本身，而是寻找信息的线索。

不要追求标签的精巧和分类完整，这是一种学生时代带来的惯性。随着我们对世界理解的加深，许多事情都不是简单的割裂，而是多维的串联在一起。而标签也不是「一类」东西，而是许多类东西的集合。

譬如对我来说，有些标签是「导航」，有些标签是「分类」，有些标签是「需要研究的主题」，有些标签是「临时」。

内容和标签的关系，肯定是张网，不会是干净的树。

而在产品设计中一个经典的概念「过早优化是万恶之源」。

一个简单的东西，可以衍生出非常多的用法，而这背后，取决于你的思维的变化。所以你可以尽量多的在一个 MEMO 打上标签，这样给未来的自己留下足够多的线索。