题目还是昨天的题，昨天已经介绍了三种解法了，今天介绍一个最快的方法。   题目链接   LeetCode 面试题 08.01. 三步问题[1]   题目描述  三步问题。有个小孩正在上楼梯，楼梯有 阶台阶，小孩一次可以上 阶、 阶或 阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模 。  示例1    输入： n = 3 输出： 4 解释： 有四种走法     示例2    输入： n = 5 输出： 13     题解  昨天的题解地址：韦阳的博客：【每日算法Day 79】所有人都会做的入门题，但是能看出你的代码能力！[2]  知乎专栏：【每日算法Day 79】所...

这两天要帮老师录制一下题解视频，所以题目挑简单一点的，减（shui）轻（liang）大（pian）家（wen）压（zhang）力。   题目链接   LeetCode 面试题 08.01. 三步问题[1]   题目描述  三步问题。有个小孩正在上楼梯，楼梯有 阶台阶，小孩一次可以上 阶、 阶或 阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模 。  示例1    输入： n = 3 输出： 4 解释： 有四种走法     示例2    输入： n = 5 输出： 13     题解  这道题是动态规划入门题，我相信大家都会做，如果不会做，那就当我没说过这句话。 令 ...

题目链接   LeetCode 55. 跳跃游戏[1]   题目描述  给定一个非负整数数组，你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。  示例1    输入： [2,3,1,1,4] 输出： true 解释： 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。     示例2    输入： [3,2,1,0,4] 输出： false 解释： 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。     题解   动态规...

周赛链接     https:// leetcode-cn.com/contest /weekly-contest-181      LeetCode 5364. 按既定顺序创建目标数组   题目链接     https:// leetcode-cn.com/problem s/create-target-array-in-the-given-order/      题解  c++ vector 自带 insert 函数，直接用就行了。  代码（c++）    class Solution { public: vector<int> createTargetArray(vector...

题目链接   LeetCode 面试题 04.06. 后继者[1]   题目描述  设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。 如果指定节点没有对应的“下一个”节点，则返回 null。  示例1    输入： root = [2,1,3], p = 1 2 / \ 1 3 输出： 2     示例2    输入： root = [5,3,6,2,4,null,null,1], p = 6 5 / \ 3 6 / \ 2 4 / 1 输出： null     题解   BST+递归  首先本题中的二叉树还是个二叉搜索树，也就是中序遍历是单调递增的，所以我们可以利用这...

题目链接   LeetCode 41. 缺失的第一个正数[1]   题目描述  给定一个未排序的整数数组，找出其中没有出现的最小的正整数。  示例1    输入： [1,2,0] 输出： 3     示例2    输入： [3,4,-1,1] 输出： 2     示例3    输入： [7,8,9,11,12] 输出： 1     说明：   你的算法的时间复杂度应为 ，并且只能使用常数级别的空间。   题解  如果之前一直坚持看我题解的同学，应该前几天刚看过下面这道题：韦阳的博客：【每日算法Day 71】面试官想考我这道位运算题，结果我给出了三种解法[2]  知乎专栏：【每日算法Day 71...

题目链接  LeetCode 面试题62. 圆圈中最后剩下的数字  题目描述   这 个数字排成一个圆圈，从数字 开始，每次从这个圆圈里删除第 个数字。求出这个圆圈里剩下的最后一个数字。 例如， 这 个数字组成一个圆圈，从数字 开始每次删除第 个数字，则删除的前 个数字依次是 ，因此最后剩下的数字是 。  示例1    输入： n = 5, m = 3 输出： 3     示例2    输入： n = 10, m = 17 输出： 2     说明：       题解   循环链表  用一个循环链表按顺序存储 到 中的数，然后每 个数删除掉链表中的一个结点，最后剩下的数就是答案了。 这种方法时...

竟然甩给我一道算法题做，太可恶了嘤嘤嘤。   题目链接   LeetCode 99. 恢复二叉搜索树[1]   题目描述  二叉搜索树中的两个节点被错误地交换。 请在不改变其结构的情况下，恢复这棵树。  示例1    输入： [1,3,null,null,2] 1 / 3 \ 2 输出： [3,1,null,null,2] 3 / 1 \ 2     示例2    输入： [3,1,4,null,null,2] 3 / \ 1 4 / 2 输出： [2,1,4,null,null,3] 2 / \ 1 4 / 3     进阶：   使用 空间复杂度的解法很容易实现。 你能想出一个只使用常数空...

题目链接   LeetCode 137. 只出现一次的数字 II[1]   题目描述  给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。 说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？  示例1    输入： [2,2,3,2] 输出： 3     示例2    输入： [0,1,0,1,0,1,99] 输出： 99     题解   逐位考虑  我们单独看二进制某一位，先不看单独的那个数，其他所有数字都出现了 3 次，所以那一位是 1 的个数一定是 3 的倍数。 再考虑这个出现一次的数，如果这一位是 1 ，那么这...

题目链接   LeetCode 面试题 17.19. 消失的两个数字[1]   题目描述  给定一个数组，包含从 到 所有的整数，但其中缺了两个数字。你能在 时间内只用 的空间找到它们吗？ 以任意顺序返回这两个数字均可。  示例1    输入： [1] 输出： [2,3]     示例2    输入： [2,3] 输出： [1,4]     提示：      题解   位运算  首先将数组里的数再加上 到 中所有的数构成一个更大的集合，那么问题就变成了一个数组里有两个数只出现了一次，其余数都出现了两次，求这两个数是多少？ 是不是很熟悉？这其实就是 LeetCode 另一道位运算题目：  Lee...

题目链接   LeetCode 959. 由斜杠划分区域[1]   题目描述  在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。 （请注意，反斜杠字符是转义的，因此 \ 用 "\\" 表示。）。 返回区域的数目。  示例1    输入： [ " /", "/ " ] 输出： 2 解释： 2x2 网格如下：       示例2    输入： [ " /", " " ] 输出： 1 解释： 2x2 网格...

题目链接   LeetCode 135. 分发糖果[1]   题目描述  老师想给孩子们分发糖果，有 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。 你需要按照以下要求，帮助老师给这些孩子分发糖果：  每个孩子至少分配到 个糖果。 相邻的孩子中，评分高的孩子必须获得更多的糖果。  那么这样下来，老师至少需要准备多少颗糖果呢？  示例1    输入： [1,0,2] 输出： 5 解释： 你可以分别给这三个孩子分发 2、1、2 颗糖果。     示例2    输入： [1,2,2] 输出： 4 解释： 你可以分别给这三个孩子分发 1、2、1 颗糖果。 第三个孩子只得到 1 颗糖果...

题目链接   LeetCode 1227. 飞机座位分配概率[1]   题目描述  有 位乘客即将登机，飞机正好有 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。 剩下的乘客将会：  如果他们自己的座位还空着，就坐到自己的座位上。 当他们自己的座位被占用时，随机选择其他座位。  第 位乘客坐在自己的座位上的概率是多少？  示例1    输入： n = 1 输出： 1.00000 解释： 第一个人只会坐在自己的位置上。     示例2    输入： n = 2 输出： 0.50000 解释： 在第一个人选好座位坐下后，第二个人坐在自己的座位上的概率是 0.5。     题解  这题呢代码相...

题目链接   LeetCode 69. x 的平方根[1]   题目描述  实现 int sqrt(int n) 函数。 计算并返回 的平方根，其中 是非负整数。 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。  示例1    输入： 4 输出： 2     示例2    输入： 8 输出： 2 解释： 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。     题解  为了更加通用，我们这里直接实现 double sqrt(double n) 函数。也就是求出 的精确值，然后取整就行了。 今天要教给大家的主要有三种方法：牛顿法、二分法和梯度下降法，速...