【程序员面试经典】快速刷 2 道题
一 目录
不折腾的前端，和咸鱼有什么区别
| 目录 |
|---|
| 一 目录 |
| 二 面试题 08.06-汉诺塔问题 |
| 三 096-不同的二叉搜索树 |
三 面试题 08.06-汉诺塔问题
返回目录
-
题目描述：
在经典汉诺塔问题中，
有 3 根柱子及 N 个不同大小的穿孔圆盘，
盘子可以滑入任意一根柱子。
一开始，所有盘子自上而下按升序，
依次套在第一根柱子上
(即每一个盘子只能放在更大的盘子上面)。
移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。
请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。
你需要原地修改栈。
示例1:
输入：A = [2, 1, 0], B = [], C = []
输出：C = [2, 1, 0]
示例2:
输入：A = [1, 0], B = [], C = []
输出：C = [1, 0]
提示:
A中盘子的数目不大于14个。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/hanota-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/**
* @param {number[]} A
* @param {number[]} B
* @param {number[]} C
* @return {void} Do not return anything, modify C in-place instead.
*/
const hanota = (A, B, C) => {
};
根据上面的已知函数，小伙伴们可以先尝试破解本题，确定了自己的答案后再看下面代码。
-
jsliang 题解：
已知 A、B、C 3 个数组，需要将 A 数组所有内容移动到 C 数组，那么最快的方式是什么？
-
C = A
但是这样是不行的，因为题目要求原地遍历，所以你需要将 A 的元素一个一个塞进 C 里面去。
作弊码
const hanota = (A, B, C) => {
for (let i = 0; i < A.length; i++) {
C[i] = A[i];
}
A.forEach((item, index) => C[index] = item);
};
这时候有小伙伴就说了，哎你就不能再简洁点嘛？
一行求解
const hanota = (A, B, C) => {
A.forEach((item, index) => C[index] = item);
};
至于用栈来实现，后面有时间补补，上班去。（2020-7-15 09:02:46）
三 096-不同的二叉搜索树
-
题目描述：
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
示例:
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/**
* @param {number} n
* @return {number}
*/
var numTrees = function(n) {
};
根据上面的已知函数，小伙伴们可以先尝试破解本题，确定了自己的答案后再看下面代码。
-
jsliang 题解：
这是一道数学题：
1 2 5 14 42 132
1 --- 1:
2 --- 2: 1 * 3 - 1
3 --- 5: 2 * 4 - 1
4 --- 14: 3 * 5 - 1
5 --- 42: 4 * 6 - 1?
拿到题目的时候直接查看前 6 个测试用例，发现数字：1 2 5 14 42 132。
作为一枚纠结 Boy，看到这种情况想着一般都有通项公式，于是去搜索了下，发现：
-
【博客园】 buptLizer 《数论二（hdoj 卡特兰数）》 -
【博客园】 jialuchun 《js实现阶乘问题》
所以它的通用公式是：!(2 * n) / !(1 + n) * !(n)，然后直接搞定这道题。
! 是阶乘的意思，!5 = 1 * 2 * 3 * 4 * 5
/**
* @param {number} n
* @return {number}
*/
const numTrees = (n) => {
let top = 1, bottomLeft = 1, bottomRight = 1;
for (let i = 2; i <= 2 * n; i++) {
top *= i;
}
for (let i = 2; i <= n + 1; i++) {
bottomLeft *= i;
}
for (let i = 2; i <= n; i++) {
bottomRight *= i;
}
return top / (bottomLeft * bottomRight);
};
console.log(numTrees(5));
简简单单又是一个早上~
不折腾的前端，和咸鱼有什么区别！
jsliang 会每天更新一道 LeetCode 题解，从而帮助小伙伴们夯实原生 JS 基础，了解与学习算法与数据结构。
浪子神剑 会每天更新面试题，以面试题为驱动来带动大家学习，坚持每天学习与思考，每天进步一点！
jsliang 的文档库 由 梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。