用回溯 + DFS 搜索全排列（去重） // 题目链接-来源：力扣（LeetCode） 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。 示例 1： 输入：nums = [1,1,2]输出：[[1,1,2], [1,2,1], [2,1,1]] 思路：此题沿用 上一题 的模板即可。唯一的区别是，本题所给的数组中拥有重复元素，我们需要动用一点小技巧进行去重操作。首先将原数组排序，方便我们后续的比较。在每轮 dfs 查找数组中的每个元素时，我们用一个局部变量 prev 记录上一次访问过的元素，后续元素必须满足与 prev 不相同的条件我们才进行考虑。prev 的初始化可以选择一个不在值域中的数字，比如本题的值域是 [-10, 10]，我取 -11。其他代码与上一题完全一样。 时间复杂度：O(n * n!)空间复杂度：O(n) 实现：12345678910111213141516171819202122232425262728293031323334353637class Solution { public List<Lis ...

用回溯 + DFS 查找全排列 // 题目链接-来源：力扣（LeetCode） 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。 示例 1： 输入：nums = [1,2,3]输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 思路：全排列的问题很直观，对于 nums 数组中的数字，我们可以用一个布尔型数组 visited[]将其标记为两类，一类是已经取到我们的结果集中的元素，另一类是尚未选择的元素。我们每次递归中，就按照一定的顺序（如，从后往前，或者从前往后，保证不遗漏即可），搜索 nums 中的尚未选择的元素，将其标为已选择（visited[i] 标记为 true），加入结果集，并在此基础上继续进行更深一层的 dfs。回溯发生在深层 dfs 返回之后，我们要恢复现场，将相关变量恢复为好像没有发生过本次 dfs 一样，包括从结果集中删除选择的元素（对于本题，即为结果列表最后一个元素），修改 visited[i]。递归中止的条件为结果集大小恰为 nums 的长度，表示 ...

贪心算法解决带长度参数的跳跃问题。 // 题目链接-来源：力扣（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; // 指向底层数 ...