贪心算法解决带长度参数的跳跃问题。 // 题目链接-来源：力扣（LeetCode） 给你一个非负整数数组 nums ，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 假设你总是可以到达数组的最后一个位置。 示例 1: 输入: nums = [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。  从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。 思路：此题容易想到较为简单的 O(n²) 复杂度算法，我们用一个数组 jumps[] 记录第 i 格距离起点所需的跳步数。对于我们遍历到的第 i 格，其跳步数为 jumps[i]，我们维护 第 i 格之后的 nums[i] 格。显然，这些格子的跳步数至多为 jumps[i] + 1。设置初始条件为 jumps[0] = 0，最终返回 jumps[n - 1] 即可。以上做法，我们可能对每一个位置进行了多次更新，考虑能否优化到 O(n) 复杂度。我们用 jump 记录 ...

二维动态规划解决通配符匹配问题 // 题目链接-来源：力扣（LeetCode） 给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 ‘?’ 和 ‘*’ 的通配符匹配。 ‘?’ 可以匹配任何单个字符。‘*’ 可以匹配任意字符串（包括空字符串）。两个字符串完全匹配才算匹配成功。 说明: s 可能为空，且只包含从 a-z 的小写字母。p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。示例 1: 输入:s = “aa”p = “a”输出: false解释: “a” 无法匹配 “aa” 整个字符串。 思路：此题与 10.正则表达式匹配 相当类似，整体而言更加简单，我们可以借鉴其思路来破解本题。我们同样记 f(i, j) 为模式串的前 i - 1 个字符与字符串的前 j - 1 个字符的匹配情况。其中 f(0, j) 与 f(i, 0) 分别表示模式串或字符串为空串的情形。对于普通字符，f(i, j) 成立当且仅当 f(i - 1, j - 1) 成立，并且 s[j - 1] == p[i - 1]，即转移方程为 f(i, ...

用字符串模拟乘法 // 题目链接-来源：力扣（LeetCode） 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。 示例 1: 输入: num1 = “2”, num2 = “3”输出: “6” 思路：因为输入是字符串的形式，直观地思考可以采用模拟竖式的形式，对两个数分别从低位向高位按位作乘法，存储当前位的结果和进位结果进入一个结果数组。考虑如下情形，我们计算 123 * 456，index 0 1 2num1 1 2 3num2 4 5 6 ... (6* 2) 1 2 (5* 3) 1 5 当计算 123 * 456 的时候，我们要计算 123 * 6，123 * 5， 123 * 4，然后分别错位累加，需要多次考虑进位，保存中间结果。我们可以对上述算法进行优化，简化我们的判断逻辑。我们用一个 res[] 数组存储结果，易知 res[] 的长度最多为两乘数长度之和 len1 + len2，最少为 len1 + len2 - 1，res[0] 对应结果的最高 ...

将大块问题分解成小块问题 // 题目链接-来源：力扣（LeetCode） 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 示例 1： 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]输出：6解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 思路：如果把每一块相连的雨水作为一个整体来考虑，时间复杂度显然是不可接受的。我们尝试按每一列来考虑雨水容量。对于任意一根柱子，其所在位置能否存放雨水，取决于其本身的高度以及「左侧最高柱子高度」以及「右侧最高柱子高度」当中的较小者（木桶原理）。于是我们需要为每一根柱子存储其「左侧最高柱子高度」以及「右侧最高柱子高度」，显然，这两个高度都能在 O(n) 时间求出，以「左侧最高柱子高度」（记为MaxLeft[i]）为例，MaxLeft[i] = max(MaxLeft[i - 1], height[i - 1])。维护了 MaxLeft 和 MaxRigh ...

用已有空间构建哈希表 // 题目链接-来源：力扣（LeetCode） 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。 示例 1： 输入：nums = [1,2,0]输出：3 思路：本题题目要求空间复杂度为 O(1)，如果不限制空间复杂度，只要将大小满足 [1, n] 区间内的数组元素存入哈希表。再遍历 [1, n] 区间，第一个不在哈希表中的整数即为所求答案。 考虑空间复杂度为常数，如果仍要使用哈希表的方法，我们只能考虑利用数组原有的空间。由于我们只需定位 [1, n] 区间内的每个元素，而数组长度恰为 n，因此我们只需实现一种 [1, n] 到 数组下标[0, n - 1] 一一对应的映射方法作为我们的哈希算法。这里为了简便起见，可以令 hash(x) = x - 1。接着我们考虑遍历数组，将 [1, n] 范围内的元素全部交换到哈希算法对应的下标位置；而对这个范围以外的元素，我们只需跳过不作考虑即可。显然，交换后的元素仍可能处于 [1, n] 范围内，我们需 ...

场景设计校招面经整理、热身 // 1. 用户登录系统： 表结构设计 为了支持多种方式用户登录，并且隔离敏感数据（如密码），防止接口暴露而泄露，我们需要分表 将用户的一些非敏感信息集合在一个 Profile 表中，字段如下： user_id（主键） | name | birthday | … 用户名和密码单独维护在一个 LocalAuth 表中，字段如下： user_id（主键） | userName | password 其他 OAuth 协议登录方式可以集成在一张 OAuth 表中，因为一个用户可能对应多种认证登录方式，不能再以 user_id 作为主键，改用一个自增 id，字段如下： id（主键） | user_id | oauth_name（比如 weibo、qq 等） | oauth_id | oauth_access_token | oauth_expires 其他登录方式类似，可以新建一个表，单独存储该种登录所需的相关信息，所有表均通过 user_id 关联到 Profile 表中 认证实现过程 用户选择任意一种登录方式（用户名密码、第三方 OAuth、HTTP A ...

计算机网络基础知识校招面经整理、热身 // 计算机网络基础知识TCP 和 UDP 区别：TCP 是面向连接的运输层协议通过三次握手、四次挥手等机制建立和拆除连接，只能一对一通信通过重传、流量控制、拥塞控制等机制实现可靠的数据传输面向字节流，将应用层传递来的数据视为无差别的字节流首部 20-60 字节 UDP 是无连接的运输层协议支持多对多交互通信不保证数据可靠到达。面向报文，将应用层传递来的报文直接加上首部后发送首部仅 8 字节 TCP 建立连接后，发送方发送一个包，接收端在收到包之前出现故障，会发生什么：这类故障的题目，抓住 2 个重点：一、端口是否关闭，若端口关闭，会返回 RST 报文，发送方收到后自行关闭连接。二、数据包是否到达接收方，接收方能否发送应答报文，应答报文能否发送回发送方。其中任何一环出问题，发送方会重传报文直到次数超限关闭连接、或者直到报文成功送达。 进程挂了接收端进程关闭后，通信的端口随之关闭，不处于监听状态，则接收端向发送端返回一个 RST 报文，发送方收到这个报文后直接关闭自己的连接。 服务器宕机发送端发送的报文无回应，会超时重传直到超出次数限制，默认 ...

Redis 基础知识校招面经整理、热身 // 1. Redis的数据结构：Redis 的数据库的基本单元是一个个「键值对」，键值对由「对象」组成， 具体是后述 5 种对象之一。键值对中的键一定是字符串对象，可以认为是这个键值对的「名字」键值对中的值可以是任意类型的某个具体的对象，可以认为是这个键值对的「本体」。 Redis 还有许多基本的数据结构如 简单动态字符串（SDS）、双端链表（linkedlist）、字典（dict）、跳跃表（skiplist）、压缩列表（ziplist）、整数集合（intset） 等，由这些数据结构的一种或多种（作为编码方式等），Redis 可以实现我们数据操作的基本单元「对象」。 2. Redis的各对象底层结构：所有redis的对象都由一个 redisObject 结构表示，有如下几个与数据有关的字段：unsigned type // 类型（如 String、List、Hash等）unsigned encoding // 编码方式（底层数据结构的实现方式）void *ptr; // 指向底层数 ...

MySQL基础知识校招面经整理、热身 // 1. 聚簇索引和普通索引：聚簇索引指其 B+ 树的叶子节点包含了指向数据的指针。查询聚簇索引时，只需顺着该指针即可访问到数据。普通索引指叶子节点处的索引项只是存储了某个聚簇索引的索引值，而非直接指向数据。查询普通索引时，还需额外回表 1 次，通过查到的索引值查找该聚簇索引，最终获得数据。MySQL中 InnoDB 主键索引一定为聚簇索引，不设主键的话第一个唯一索引字段即为聚簇索引，没有唯一索引字段的话，使用隐藏字段自增主键作为聚簇索引。由于聚簇索引在一张表中最多创建一个，所以其余索引为普通索引。 2. 普通索引和聚簇索引是单独存在表还是另外开一个表：不太确定这题要问什么。尝试从叶子结点的结构来回答。 聚簇索引的叶子结点是指向了该结点值所在的数据行的，也就是说指向了原数据表。 普通索引的叶子节点则是指向了一个新表，表中存储了当前索引值对应的所有主键值。从这个角度来说，普通索引确实创建了一个新表，而聚簇索引没有（直接在原数据表的基础上以主键构建索引） 3. HashMap 和 B 树有何异同，为什么数据库一般使用b树来当索引：相同：好像没 ...

数据结构基础知识校招面经整理、热身 // 1. 红黑树、B+ 树、B 树、二叉搜索树： 二叉搜索树：又称 BST，是为了实现在 O(logn) 时间内完成对有序集合中的元素完成一次查找，而设计的数据结构。 B树：二叉搜索树在最坏情况下，如果元素按顺序插入，会失去平衡退化为链表，查找的效率为 O(n)，为了解决这个平衡问题，引入 AVL 树、 B 树。B树中的元素会优先填满每层的结点，达到最大值以后分裂，分裂时会调整父节点和其他子节点，实现平衡。同时 B 树的一层可以设定允许容纳多个节点，进一步降低树高。 红黑树： B 树的一个缺点在于其插入、删除节点时的分裂逻辑较为复杂，对大量写操作不友好。为了解决这个问题，引入红黑树。红黑树是某棵确定的 2-3 B树的另一种表现形式（或者说，给定一种旋转规则（LL、LR、RR旋转），则一棵红黑树唯一地映射着一棵 2-3 B 树，反之亦然）。其某个红结点与其父节点（一定为黑色）可以视为对应的 2-3 B 树的某一个结点的2个元素。至此，我们将 B 树的结点分裂规则，转化为了红黑树的旋转规则，大大简化了判断逻辑。 B+ 树： B 树的另一缺点在于，对 ...