INCOMING TRANSMISSION

164. 最大间距 题目 给定一个无序的数组，找出数组在排序之后，相邻元素之间最大的差值。 如果数组元素个数小于 2，则返回 0。 Example 1: Input: [3,6,9,1] Output: 3 Explanation: The sorted form of the array is [1,3,6,9], either (3,6) or (6,9) has the maximum difference 3. 题解 如果进行排序，这里会超时。采用桶排序 基础排序算法 的思想，可以在线性时间解决。 首先建立桶，每个桶中只需要存放这个桶中元素的最大值和最小值。 我们期望将数组中的各个数等距离分配，也就是每个桶的长度相同，也就是对于所有桶来说，桶内最大值减去桶内最小值都是一样的。可以当成公式来记。 \[每个桶的长度=\max(1,\lfloor{{\max(nums)-\min(nums)}\over{len(nums)-1}}\rfloor)\tag{1}\]...

实现 方式一：使用 heapq 标准库 这是 Python 最快、最节省内存的方式，因为 heapq 底层是用 C 语言实现的。 小顶堆 (Min Heap) Python 的 heapq 默认就是小顶堆。 import heapq # 初始化 min_heap = [] # 添加元素 O(log N) heapq.heappush(min_heap, 5) heapq.heappush(min_heap, 2) heapq.heappush(min_heap, 8) # 查看堆顶 O(1) print(min_heap[0]) # 输出: 2 # 弹出堆顶 O(log N) pop_val = heapq.heappop(min_heap) print(pop_val) # 输出: 2 print(min_heap) # 输出: [5, 8] (注意：堆内部不一定有序，但堆顶一定是最小的) # 将已有的列表转化为堆 O(N) nums = [5, 7, 1, 3] heapq.heapify(nums) print(nums) #...

Tokenizer 背景与基础 目前的机器学习模型都是数学模型，其对应的输入要求必须是数字形式（number）的，而我们处理的真实场景往往会包含许多非数字形式的输入（有时候即使原始输入是数字形式，我们也需要转换），最典型的就是 NLP 中的文字(string)，为了让文字能够作为输入参与到模型的计算中去，我们就需要构建一个映射关系(mapping)：将对应的文字映射到一个数字形式上去，而其对应的数字就是 token。而对应的这个映射关系，就是我们的 tokenizer：他可以将文字映射到其对应的数字上去(encode)，也可以将数字映射回对应的文字上(decode)。 诸如GPT-3/4以及LlaMA/LlaMA2大语言模型都采用了token的作为模型的输入输出，其输入是文本，然后将文本转为token（正整数），然后从一串token（对应于文本）预测下一个token。 进入OpenAI官网提供的tokenizer可以看到GPT-3tokenizer采用的方法。这里以Hello World为例说明。...

什么是Word2Vec和Embeddings？ Word2Vec是从大量文本语料中以无监督的方式学习语义知识的一种模型，它被大量地用在自然语言处理（NLP）中。那么它是如何帮助我们做自然语言处理呢？Word2Vec其实就是通过学习文本来用词向量的方式表征词的语义信息，即 通过一个嵌入空间使得语义上相似的单词在该空间内距离很近 。Embedding其实就是一个映射，将单词从原先所属的空间映射到新的多维空间中，也就是把原先词所在空间嵌入到一个新的空间中去。 我们从直观角度上来理解一下，cat这个单词和kitten属于语义上很相近的词，而dog和kitten则不是那么相近，iphone这个单词和kitten的语义就差的更远了。通过对词汇表中单词进行这种数值表示方式的学习（也就是将单词转换为词向量），能够让我们基于这样的数值进行向量化的操作从而得到一些有趣的结论。比如说，如果我们对词向量kitten、cat以及dog执行这样的操作：kitten - cat + dog，那么最终得到的嵌入向量（embedded vector）将与puppy这个词向量十分相近。 第一部分 模型...

RNN 概述 在前面讲到的DNN和CNN中，训练样本的输入和输出是比较的确定的。但是有一类问题DNN和CNN不好解决，就是训练样本输入是连续的序列,且序列的长短不一，比如基于时间的序列：一段段连续的语音，一段段连续的手写文字。这些序列比较长，且长度不一，比较难直接的拆分成一个个独立的样本来通过DNN/CNN进行训练。 而对于这类问题，RNN则比较的擅长。那么RNN是怎么做到的呢？RNN假设我们的样本是基于序列的。比如是从序列索引1到序列索引 \(τ\) 。对于这其中的任意序列索引号 \(t\) ,它对应的输入是对应的样本序列中的 \(x(t)\) 。而模型在序列索引号 \(t\) 位置的隐藏状态 \(h(t)\) ，则由 \(x(t)\) 和在 \(t−1\) 位置的隐藏状态 \(h(t−1)\) 共同决定。在任意序列索引号 \(t\) ，我们也有对应的模型预测输出 \(o(t)\) 。通过预测输出 \(o(t)\) 和训练序列真实输出 \(y(t)\) ,以及损失函数 \(L(t)\) ，我们就可以用DNN类似的方法来训练模型，接着用来预测测试序列中的一些位置的输出。...

Self-Supervised Learning ，又称为自监督学习，我们知道一般机器学习分为有监督学习，无监督学习和强化学习。 而 Self-Supervised Learning 是无监督学习里面的一种，主要是希望能够学习到一种 通用的特征表达 用于 下游任务 (Downstream Tasks) 。 其主要的方式就是通过自己监督自己。作为代表作的 kaiming 的 MoCo 引发一波热议， Yann Lecun也在 AAAI 上讲 Self-Supervised Learning 是未来的大势所趋。所以在这个系列中，我会系统地解读 Self-Supervised Learning 的经典工作。 本文主要介绍 Self-Supervised Learning 在 NLP领域 的经典工作：BERT模型的原理及其变体。 本文来自台湾大学李宏毅老师PPT： https://speech.ee.ntu.edu.tw/~hylee/ml/ml2021-course-data/bert_v8.pdf 芝麻街 在介绍 Self-Supervised Learning...

简介 生成树（spanning tree） 在图论中，无向图 \(G=(V,E)\) 的生成树（spanning tree)是具有 \(G\) 的全部顶点，但边数最少的联通子图。假设 \(G\) 中一共有 \(n\) 个顶点，一颗生成树满足下列条件 \(n\) 个顶点； \(n-1\) 条边； \(n\) 个顶点联通； 一个图的生成树可能有多个。 最小生成树（minimum spanning tree， MST）/最小生成森林 ：联通加权无向图中边缘权重加和最小的生成树。给定无向图 \(G=(V,E)\) ， \((u,v)\) 代表顶点 \(u\) 与顶点 \(v\) 的边， \(w(u,v)\) 代表此边的权重，若存在生成树T使得： \[w(T) = \sum_{(u,v)\in T}w(w,v)\] 最小，则 \(T\) 为 \(G\) 的最小生成树。对于非连通无向图来说，它的每一 连通分量 同样有最小生成树，它们的并被称为 最小生成森林 。最小生成树除了继承生成树的性质之外，还存在下面两个特点： 当图的每一条边的权值都相同时，该图的所有生成树都是最小生成树；...

💡 不断排除不存在解的区间，直至最后剩下一个 这里归纳最重要的部分： 分析题意，挖掘题目中隐含的 单调性； while (left < right) 退出循环的时候有 left == right 成立，因此无需考虑返回 left 还是 right ； 始终思考下一轮搜索区间是什么，如果是 [mid, right] 就对应 left = mid ，如果是 [left, mid - 1] 就对应 right = mid - 1 ，是保留 mid 还是 +1、−1 就在这样的思考中完成； 从一个元素什么时候不是解开始考虑下一轮搜索区间是什么 ，把区间分为 2个部分（一个部分肯定不存在目标元素，另一个部分有可能存在目标元素），问题会变得简单很多，这是一条 非常有用 的经验； 每一轮区间被划分成 2 部分，理解 区间划分 决定中间数取法（ 无需记忆，需要练习 + 理解 ），在调试的过程中理解 区间和中间数划分的配对关系： 划分 [left, mid] 与 [mid + 1, right] ，mid 被分到左边，对应 int mid = left + (right - left) / 2 ;...

引入 在具体讲何为「背包 dp」前，先来看如下的例题： 题意概要：有 \( 𝑛\) 个物品和一个容量为 \( 𝑊\) 的背包，每个物品有重量 \(𝑤_𝑖\) 和价值 \(𝑣_𝑖\) 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量． 在上述例题中，由于每个物体只有两种可能的状态（取与不取），对应二进制中的 0 和 1，这类问题便被称为「0-1 背包问题」． 0-1背包 解释 例题中已知条件有第 \(𝑖\) 个物品的重量 \(𝑤_𝑖\) ，价值 \(𝑣_𝑖\) ，以及背包的总容量 \(𝑊\) ． 设 DP 状态 \(𝑓_{𝑖,𝑗} \) 为在只能放前 \(𝑖\) 个物品的情况下，容量为 \(𝑗\) 的背包所能达到的最大总价值． 考虑转移．假设当前已经处理好了前 \(𝑖 −1 \) 个物品的所有状态，那么对于第 \(𝑖\) 个物品，当其不放入背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为 \(𝑓_{𝑖−1,𝑗}\) ；当其放入背包时，背包的剩余容量会减小 \(𝑤_𝑖\) ，背包中物品的总价值会增大 \(𝑣_𝑖\)...

排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括： 冒泡排序 冒泡排序（Bubble Sort）是一种简单的排序算法，它通过重复地遍历待排序的列表，比较相邻的元素并交换它们的位置来实现排序。该算法的名称来源于较小的元素会像"气泡"一样逐渐"浮"到列表的顶端。 算法步骤 比较相邻元素 ：从列表的第一个元素开始，比较相邻的两个元素。 交换位置 ：如果前一个元素比后一个元素大，则交换它们的位置。 重复遍历 ：对列表中的每一对相邻元素重复上述步骤，直到列表的末尾。这样，最大的元素会被"冒泡"到列表的最后。 缩小范围 ：忽略已经排序好的最后一个元素，重复上述步骤，直到整个列表排序完成。 假设有一个待排序的列表 [5, 3, 8, 4, 6] ，冒泡排序的过程如下： 第一轮遍历 ： 比较 5 和 3，交换位置，列表变为 [3,...

DFS 39&40. 组合总和 题目 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。 示例 1： 输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]] 解释： 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选， 7 = 7 。 仅有这两种组合。 示例 2： 输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]] 示例 3： 输入: candidates = [2], target = 1 输出: [] 提示： 1 <=...

堆和优先队列的关系 这是一个非常经典且核心的计算机科学概念问题。一言以蔽之： 优先队列（Priority Queue）是逻辑接口（ADT），而堆（Heap）是实现这个接口最高效的物理数据结构。 它们的关系可以类比为 “接口（Interface）” 与 “实现类（Implementation）” 的关系，或者 “汽车（功能）”与 “发动机（核心组件）” 的关系。 优先队列 (Priority Queue) —— 逻辑层 (ADT) 定义 ：它是一种 抽象数据类型 (Abstract Data Type, ADT) 。它定义了数据的 行为 ，而不是数据的存储方式。 规则 ：普通的队列是“先进先出”（FIFO），而优先队列是 “优先级最高的先出” 。 核心操作 ： insert(item, priority) : 插入一个带优先级的元素。 deleteMax() 或 deleteMin() : 取出并删除优先级最高（或最低）的元素。 peek() : 查看优先级最高的元素。 堆 (Heap) —— 物理层 (Data Structure) 定义 ：它是一种具体的 数据结构 。通常指 二叉堆...