题目难度: 简单   原题链接   今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~  题目描述 三步问题。有个小孩正在上楼梯，楼梯有 n 阶台阶，小孩一次可以上 1 阶、2 阶或 3 阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模 1000000007。 示例 1:  输入：n = 3 输出：4 说明: 有四种走法  示例 2:  输入：n = 5 输出：13  提示:  n 范围在[1, 1000000]之间  题目思考  第 n 阶台阶的跳法数目可以根据什么得出?  解决方案 思路...

题目难度: 中等   原题链接   今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~  题目描述 绘制直线。有个单色屏幕存储在一个一维数组中，使得 32 个连续像素可以存放在一个 int 里。屏幕宽度为 w，且 w 可被 32 整除（即一个 int 不会分布在两行上），屏幕高度可由数组长度及屏幕宽度推算得出。请实现一个函数，绘制从点(x1, y)到点(x2, y)的水平线。 给出数组的长度 length，宽度 w（以比特为单位）、直线开始位置 x1（比特为单位）、直线结束位置 x2（比特为单位）、直线所在行数 y。返...

题目难度: 简单   原题链接   今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~  题目描述 配对交换。编写程序，交换某个整数的奇数位和偶数位，尽量使用较少的指令（也就是说，位 0 与位 1 交换，位 2 与位 3 交换，以此类推）。 示例 1:  输入：num = 2（或者 0b10） 输出 1 (或者 0b01)  示例 2:  输入：num = 3 输出：3  提示:  num 的范围在[0, 2^30 - 1]之间，不会发生整数溢出。  题目思考  可以使用什么位运算来尽可能减少操作指令数目?  解决方案...

题目难度: 简单   原题链接   今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~  题目描述 整数转换。编写一个函数，确定需要改变几个位才能将整数 A 转成整数 B。 示例 1:  输入：A = 29 （或者 0b11101）, B = 15（或者 0b01111） 输出：2  示例 2:  输入：A = 1，B = 2 输出：2  提示:  A，B 范围在[-2147483648, 2147483647]之间  题目思考  如何找到 A 与 B 有几位不同?  解决方案 思路  想要得到 A 与 B 有几位不同...

题目难度: 中等   原题链接   今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~  题目描述 下一个数。给定一个正整数，找出与其二进制表达式中 1 的个数相同且大小最接近的那两个数（一个略大，一个略小）。 示例 1:  输入：num = 2（或者 0b10） 输出：[4, 1] 或者（[0b100, 0b1]）  示例 2:  输入：num = 1 输出：[2, -1]  提示:  num 的范围在[1, 2147483647]之间； 如果找不到前一个或者后一个满足条件的正数，那么输出 -1。  题目思考  与原...

题目难度: 简单   原题链接   今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~  题目描述 给定一个 32 位整数 num，你可以将一个数位从 0 变为 1。请编写一个程序，找出你能够获得的最长的一串 1 的长度。 示例 1：  输入: num = 1775(11011101111) 输出: 8  示例 2：  输入: num = 7(0111) 输出: 4  题目思考  根据题目描述, 有没有什么简单直接的思路? 如何优化, 能够通过一次遍历就得到结果?  解决方案 方案 1 思路  最直接的方法, 既然要求...

题目难度: 中等   原题链接   今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~  题目描述 二进制数转字符串。给定一个介于 0 和 1 之间的实数（如 0.72），类型为 double，打印它的二进制表达式。如果该数字无法精确地用 32 位以内的二进制表示，则打印“ERROR”。 示例 1:  输入：0.625 输出："0.101"  示例 2:  输入：0.1 输出："ERROR" 提示：0.1 无法被二进制准确表示  提示： 32 位包括输出中的"0.&qu...

题目难度: 简单   原题链接   今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~  题目描述 给定两个整型数字 N 与 M，以及表示比特位置的 i 与 j（i <= j，且从 0 位开始计算）。 编写一种方法，使 M 对应的二进制数字插入 N 对应的二进制数字的第 i ~ j 位区域，不足之处用 0 补齐。具体插入过程如图所示。  题目保证从 i 位到 j 位足以容纳 M， 例如： M = 10011，则 i ～ j 区域至少可容纳 5 位。 示例 1:  输入：N = 1024(10000000000),...

题目难度: 中等   原题链接   今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~  题目描述 给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。 示例: 给定如下二叉树，以及目标和 sum = 22，  5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 返回: 3 解释：和为 22 的路径有：[5,4,1...

题目难度: 中等   原题链接   今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~  题目描述 检查子树。你有两棵非常大的二叉树：T1，有几万个节点；T2，有几万个节点。设计一个算法，判断 T2 是否为 T1 的子树。 如果 T1 有这么一个节点 n，其子树与 T2 一模一样，则 T2 为 T1 的子树，也就是说，从节点 n 处把树砍断，得到的树与 T2 完全相同。 示例 1:  输入：t1 = [1, 2, 3], t2 = [2] 输出：true  示例 2:  输入：t1 = [1, null, 2, 4],...

题目难度: 困难   原题链接   今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~  题目描述 从左向右遍历一个数组，通过不断将其中的元素插入树中可以逐步地生成一棵二叉搜索树。给定一个由不同节点组成的二叉搜索树，输出所有可能生成此树的数组。 示例： 给定如下二叉树  2 / \ 1 3返回： [ [2,1,3], [2,3,1] ]题目思考  从左向右遍历, 那么根节点一定是数组第一个元素, 可以利用到这一特性吗? 对于数组某个元素而言, 其有效插入位置可能有哪些?  解决方案 思路  使用一个集合存储下个所有可能...

题目难度: 中等   原题链接   今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~  题目描述 设计并实现一个算法，找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。注意：这不一定是二叉搜索树。 例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]  3 / \ 5 1 / \ / \ 6 2 0 8 / \ 7 4示例 1:  输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 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  题目思考  可以利用哪...

题目难度: 中等   原题链接   今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~  题目描述 实现一个函数，检查一棵二叉树是否为二叉搜索树。 示例 1:  输入:   2 / \ 1 3 输出: true  示例 2:  输入:   5 / \ 1 4 / \ 3 6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ，但是其右子节点值为 4 。  题目思考  可以利用二叉搜索树的哪些性质来判断?  解决方案 方案 1 思路  二叉搜索树最直观的性质就是: 当前...