字节跳动的笔试记录是最详细的，但是也是唯一一个没有成功的。

今天带来的一手笔试题目难度各异，分别来自美团、阿里和华为。总体来说，阿里的题目数据量大、用时紧张，很难完整得出结果；美团的题目较多，但上手也比较容易；华为题目虽然相对简单，但是输入输出的数据格式非常糟糕。

下面对部分留下记录的题目进行简单分析：

一句话介绍

支持向量机是一种分类模型，求解能够正确划分训练数据集并且几何间隔最大的分离超平面。

0.支持向量

要理解什么是支持向量（support vector），首先需要理解以下几个概念：

如果我们有一堆数据（二维），在二维平面上分布如下图所示：

我们可以用一条直线将这堆数据分成两个部分：

【当这堆数据维数是3维，这条直线就成了平面；当数据维数更高，这条分隔线就成了超平面】以下统称超平面，数学表达为：

$w^\cdot x + b^=0$

要说明的是，仅仅把这堆数据分离开，也许有无数个超平面可以做到；

我们做一些规范，最大几何间隔的分离超平面，是唯一且存在的。

很明显，分隔之后，有的点离这个超平面近，有的远，最近点到超平面的距离，称为间隔，这个最近的样本点的实例就被称为支持向量【本定义适用于线性可分情况下】。

支持向量在确定分离超平面中起决定性作用（不移动支持向量，分离超平面就不会变化），所以把这种分类模型称为支持向量机。

一句话：本章提到两种应用了概率知识和最优化方法的对数线性数学模型。

首先对本章知识进行定位：

1. 本章知识和前后联系都不是很大，但是 logistic 回归（sigmoid函数）确实十分常用的一个理论知识。
2. 最大熵模型更是宏观地把回归和分类问题转换成最优化问题的数学模型。

本章公式极多，多为推导，在此大多数将不会列出，如果有兴趣，非常建议阅读原书。

206. 反转链表

这个题其实已经做过多次了，这次总结一下：

题目要求：给出一个链表的头节点，请反转整个链表，并且返回反转后的链表的头节点。

这个题用递归的方法简直是非常之妙，而且十分经典。

1
2
3
4
5
6
7
8
9
10
11
12

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverse(self, head: ListNode) -> ListNone:
        if not head or not head.next: return head
        last = self.reverse(head.next)
        head.next.next = head
        head.next = None
        return last

这个做法简直非常精妙，充分体现了递归方法中的关键：

1）找一个最简问题，解决它

2）充分理解并相信函数能解决你的问题

424. 替换后的最长重复字符

输入：字符串 s，全部是大写字母； 整数 k

要求：最多可以将字符串s中的任意 k 个字符进行替换

输出：最长重复字符的数量

官方题解

官方题解的方法确实很妙：

如果该数值大于 k ，自然是不符合题意，那么右指针移动，左指针也移动：

如果数值小于等于 k，那么说明符合题意，右指针移动，左指针不用移动：

右指针 - 左指针 就是最长重复子字符串的长度

问题在于，怎么计算区间内非重复字符的数量？

体验

平台：牛客网

特点：

1. 标准 sys 输入和输出，给输入和输出的范例，主要是多行输入和单行输出
2. 可以自测，可以print

题目

总共有四道题目

1）环形数组 - 找座位问题

给出一个环形数组，其中全部为 0 或 1

请找到一个 0，它距离两侧的 1 应该最远

怎么样建立起一个数据仓库的

• 肯定不是说把 csv 数据导入 mysql 这么简单，确实就像 布迩 说的，我这个算是别人建好的数据仓库
• 那么究竟怎样才是自己建立数据仓库呢？

csv 文件导入 MySQL：

1
2
3
4

load data infile 'F:/MySqlData/test1.csv' -- CSV文件存放路径
into table student -- 要将数据导入的表名
fields terminated by '列的分隔符' optionally enclosed by '"' escaped by '"'
lines terminated by '\r\n' -- 回车换行符;

如果是linux下生成的文件，就是 \n 结尾

注意：这个东西很有可能会出现各种的报错，需要修改配置文件等内容

每期10题，上一期参见LeetCode刷题笔记（四）。

本期内容紧贴2021年1月leetcode每日一题，本月主要内容是并查集（包括深度优先或广度优先）及双指针，包括在周赛中也遇到双指针题目，需要重点考虑。

1018. 可被5整除的二进制前缀

输入：整数列表 - 只有 0 和 1

输出：布尔列表 - 只有 false 和 true

要求：依次选择整数列表中 从 第0位到第i位的所有数字，这是一个二进制数字，如果可以被5整除，那么布尔列表的第 i 位为true，否则为false。

一句话解释：主要针对分类问题，对已有数据，根据各个特征的表现情况进行二分类（或多分类），从而形成一个像树一样的分类结构。

这一部分公式比较多，配合例题进行理解。

一句话介绍：对给定的输入x，结合贝叶斯概率理论，通过学习到的模型，将后验概率最大的类作为x的类输出。

最好学习过贝叶斯估计方法。

在本科阶段的概率论或研究生阶段的数理统计中，都有对贝叶斯估计方法的介绍，与其他估计方法的最大不同是——加入了先验估计概念。

基础知识

部分公式：

• 先验概率分布$P(Y=c_k),k=1,2,…,K$
• 条件概率分布$P(X=x|Y=c_k)=P(X^{(1)}=x^{(1)},…,X^{(n)}=x^{(n)}|Y=c_k),k=1,2,…,K$
• 后验概率分布（贝叶斯定理）$P(Y=c_k|X=x)=\frac{P(X=x|Y=c_k)P(Y=c_k)}{\Sigma_k P(X=x|Y=c_k)P(Y=c_k)}$

补充一个忽略了很久的知识点：

arg max(f(x)) 函数：得到的结果是使得 f(x)取得最大值所对应的变量点x(或x的集合)。arg即argument，自变量。