2.前端算法1
2.1 树 找到某节点的路径
参考答案：
查找某个节点的路径的方法通常有两种，一种是递归算法,另一种是非递归算法
定义树节点
// 树节点定义
class TreeNode{
constructor(value){
this.value = value;
this.left = null;
this.right = null;
}
}
构建树
// 构建树 let root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5);
递归算法
// 递归中序遍历二叉树
function midOrder(root) {
if(!root || !(root instanceof TreeNode)){
return;
}
// 递归访问左子树
midOrder(root.left);
console.log(root.value);
// 递归访问右子树
midOrder(root.right);
}
midOrder(root);
非递归算法
// 非递归中序遍历二叉树
function midOrderN(root) {
let p = root; // p为当前遍历的节点， 初始为根
let arr = []; // arr作为栈
while(p || arr.length !== 0){
if(p){
// 遍历左子树
arr.push(p);
// 每遇到非空二叉树先向做走
p = p.left;
}else{
// p为空，出栈
let node = arr.pop();
// 访问该节点
console.log(node.value);
// 向右走一次
p = node.right;
}
}
}
midOrderN(root)
2.2 洗完牌抽5张判断是否为同花顺
参考答案：
题目：从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2-10为数字本身，A为1，J为11，Q为12，K为13，而大小王可以看成任意数字。
思路一:
我们需要把扑克牌的背景抽象成计算机语言。不难想象，我们可以把5张牌看成由5个数字组成的数组。大小王是特殊的数字，我们不妨把它们都当成0，这样和其他扑克牌代表的数字就不重复了。接下来我们来分析怎样判断5个数字是不是连续的。最直观的是，我们把数组排序。但值得注意的是，由于0可以当成任意数字，我们可以用0去补满数组中的空缺。也就是排序之后的数组不是连续的，即相邻的两个数字相隔若干个数字，但如果我们有足够的0可以补满这两个数字的空缺，这个数组实际上还是连续的。举个例子，数组排序之后为{0，1，3，4，5}。在1和3之间空缺了一个2，刚好我们有一个0，也就是我们可以它当成2去填补这个空缺。于是我们需要做三件事情：把数组排序，统计数组中0的个数，统计排序之后的数组相邻数字之间的空缺总数。如果空缺的总数小于或者等于0的个数，那么这个数组就是连续的；反之则不连续。最后，我们还需要注意的是，如果数组中的非0数字重复出现，则该数组不是连续的。换成扑克牌的描述方式，就是如果一副牌里含有对子，则不可能是顺子。
思路二:
1）确认5张牌中除了0，其余数字没有重复的（可以用表统计的方法）;
2) 满足这样的逻辑：（max，min分别代表5张牌中的除0以外的最大值最小值）
如果没有0，则max-min=4，则为顺子，否则不是
如果有一个0，则max-min=4或者3，则为顺子，否则不是
如果有两个0，则max-min=4或者3或者2，则为顺子，否则不是最大值和最小值在1）中就可以获得，这样就 不用排序了
2.3 爬楼梯 编代码
参考答案：
题目描述：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
方法分析：
这道题主要是要明白该爬楼梯的规律其实就是符合斐波那契数列（Fibonacci Sequence） 规律的，问题就迎刃而解了。为什么说它是斐波那契数列呢？我们可以这样来思考：当我们从第 n-1 阶楼梯爬到第 n 阶楼梯时，需要1步；当我们从第 n-2 阶楼梯爬到第 n 阶楼梯时，需要2步.也就是说 到达第 n 阶楼梯的方法数等于到达第 n-1 阶楼梯的方法数加上到达第 n-2 阶楼梯的方法数，其正好符合斐波那契通项。
代码实现：
- 采用递归实现
var climbStairs = function(n) {
if(n == 1) return 1;
if(n == 2) return 2;
return climbStairs(n-1) + climbStairs(n-2);
};
递归是求解斐波那契数列最经典和最直接的方式，其简洁易懂；但是递归特别费时，在该题中使用会出现[超出时间限制]的错误提示。
- 数组方式
var climbStairs = function(n) {
let result = [1,2];
for (let i = 2; i < n; i++) {
result.push(result[i-1] + result[i-2]);
}
return result[n-1];
};
数组方式大大的减少了运行时间，我们先预设好前两项，再得到结果，返回数组最后一项即可。
- ES6的方式
var climbStairs = function(n) {
let a = b = 1;
for (let i = 0; i < n; i++) {
[a, b] = [b, a + b];
}
return a;
};
其中 [a, b] = [b, a + b] 表示解构赋值，其等价于
temp = a; a = b; b = temp + b;
2.4 怎么识别100枚硬币中的假币
参考答案：
问题描述：
在n枚外观相同的硬币中，有一枚是假币，并且已知假币与真币的重量不同，但不知道假币与真币相比较轻还是较重。可以通过一架天平来任意比较两组硬币，设计一个高效的算法来检测这枚假币(以下提供两种方法)。
解题思路1 (本例为真币重量大于假币)：
使用减治法的解题思路，将硬币分为3堆，则每堆的硬币数量为 n/3 ，但是这是在 n%3==0 的情况下才能成立，所以我们将 n 枚硬币分为 3 堆加 1 堆 余数堆(余数堆可能为0)，则可分为如下(n-n%3)/3, (n-n%3)/3, (n-n%3)/3, n%3。
如下分组：
a堆： (n-n%3)/3
b堆： (n-n%3)/3
c堆： (n-n%3)/3
d(余数堆): n%3
逻辑流程：
- 判断n中的硬币数量，如果n>2则执行2，否则执行5.
- 将n分为上图的四堆，拿 a 和 b 比较，如果 a == b ,则 假币在 c 或 d 中。否则假币在 a 或 b 中。
- 如果 a == b，则拿 a 和 c 比较。如果 a == c,则假币在d(余数堆)中。将 d 再次 执行流程1，并且n=n%3。如果不等，则假币在 c 中，将 c 再次 执行流程1，并且n=(n-n%3)/3。
- 如果 a != b，则拿 a 和 c 比较。如果 a == c,则假币在b中，将 b 再次 执行流程1，并且n=(n-n%3)/3。如果不等，则假币在 a 中，将 a 再次 执行流程 1，并且n=(n-n%3)/3。
- 如果n==2，则将两枚硬币进行比较找出假币。
- 如果n==1，则该硬币就是假币，输出结果结束。
解题思路2（以12枚硬币为例，且假币未知轻重）：
- 将硬币编号：1，2，3，4，5，6，7，8，9，10，11，12。三次称重如下安排：
- 称重：
第一次称重：左盘：1，2，3，4 右盘：5，6，7，8 其他：9，10，11，12
第二次称重：左盘：1，6，7，8 右盘：5，10，11，12 其他：9，2，3，4
第三次称重：左盘：5，6，10，2 右盘：9，7，11，3 其他：1，8，12，4
称重结果：平衡取0，左倾取1，右倾取-1。
3次称重安排可表示成矩阵形式：
.png)
其中，矩阵第一行是硬币序号，下面每一行都是一次称重结果，1表示该硬币放左盘，-1表示放右盘，0表示不放。矩阵每一列为检测结果，检测结果对应的硬币序号为假币。如果结果与上边的符合，则对应重量为重，如果结果不包含在上述表中，则进行1 -1互换，得到的重量为轻。例如：若称重结果是110，则1号为假币，且重量较重：若称重结果为1-10，1与-1进行交换后为-110，则8号为假币，且重量较轻。
2.5 手撕快排算法
参考答案：
思想：
- 在数据集之中，选择一个元素作为"基准"（pivot）。
- 所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
- 对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
实现：
var quickSort = function(arr) {
if (arr.length <= 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++){
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat([pivot], quickSort(right));
};
2.6 常见的排序算法和它们的时间复杂度是多少？
参考答案：
| 稳定的排序 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 冒泡排序(bubble sort) | 最差、平均都是O(n^2)，最好是O(n) | 1 |
| 插入排序(insertion sort) | 最差、平均都是O(n^2)，最好是O(n) | 1 |
| 归并排序(merge sort) | 最差、平均、最好都是O(n log n) | O(n) |
| 桶排序(bucket sort) | O(n) | O(k) |
| 基数排序(Radix sort) | O(nk)（k是常数） | O(n) |
| 二叉树排序(Binary tree sort) | O(n log n) | O(n) |
| 不稳定的排序 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 选择排序(selection sort) | 最差、平均都是O(n^2) | 1 |
| 希尔排序(shell sort) | O(n log n) | 1 |
| 堆排序(heapsort) | 最差、平均、最好都是O(n log n) | 1 |
| 快速排序(quicksort) | 平均是O(n log n)，最差是O(n^2) | O(log n) |
2.7 说一下归并排序思想怎么实现的
参考答案：
“归并”的意思是将两个或两个以上的有序表组合成一个新的有序表。假如初始序列含有n个记录，则可看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到[n/2]（向上取整）个长度为2或1的有序子序列；再两两归并，……，如此重复，直到得到一个长度为n的有序序列为止，这种排序方法称为2-路归并排序。
步骤解析：
1、把长度为n的输入序列分成两个长度为n/2的子序列；
2、对这两个子序列继续分为m/2的子序列，一直分下去，直为1个元素；
3、将两个排序好的子序列合并成一个最终的排序序列。
特点：
速度仅次于快速排序，为稳定排序算法，一般用于总体无序，但是各子项相对有序的数列，属于分治思想，递归归并。
动图演示：
JavsScript代码实现：
//归并排序
function mergeSort(arr){
var len = arr.length;
if(len < 2){
return arr;
}
//首先将无序数组划分为两个数组
var mid = Math.floor(len / 2);
var left = arr.slice(0,mid);
var right = arr.slice(mid,len);
return merge(mergeSort(left),mergeSort(right));//递归分别对左右两部分数组进行排序合并
}
//合并
function merge(left,right){
var result = [];
while(left.length>0 && right.length>0){
if(left[0]<=right[0]){
//如果左边的数据小于右边的数据，将左边数据取出，放在新数组中
result.push(left.shift());
}else{
result.push(right.shift());
}
}
while(left.length){
result.push(left.shift());
}
while(right.length){
result.push(right.shift());
}
return result;
}
var arr = [3,44,38,5,47,15,36,26];
console.log(mergeSort(arr));//3,5,15,26,36,38,44,47
2.8 算法：3数之和
参考答案：
题目描述：
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，*使得 *a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
//例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
//满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
var threeSum = function(nums) {
nums=nums.sort(function(a,b){return a-b});//先排序
var i=0;
var arr=[];
while(i<nums.length-1){
var a=nums[i],j=i+1,k=nums.length-1;
while(j<k){
var b=nums[j],c=nums[k];
var sum=a+b+c;
if(sum==0)arr.push([a,b,c]);//存起来
if(sum<=0)
while(nums[j]==b&&j<k)j++;//第2个
if(sum>=0)
while(nums[k]==c&&j<k)k--//最后一个数
}
while(nums[i]==a&&i<nums.length-1)i++;//第一个
}
return arr
};
2.9 算法：连续最大乘积
参考答案：
题目描述
给一个浮点数序列，取最大乘积连续子串的值，例如 -2.5，4，0，3，0.5，8，-1，则取出的最大乘积连续子串为3，0.5，8。也就是说，上述数组中，3 0.5 8这3个数的乘积30.58=12是最大的，而且是连续的。
分析与解法
此最大乘积连续子串与最大乘积子序列不同，请勿混淆，前者子串要求连续，后者子序列不要求连续。也就是说，最长公共子串（Longest CommonSubstring）和最长公共子序列（LongestCommon Subsequence，LCS）是：
- 子串（Substring）是串的一个连续的部分，
- 子序列（Subsequence）则是从不改变序列的顺序，而从序列中去掉任意的元素而获得的新序列；
更简略地说，前者（子串）的字符的位置必须连续，后者（子序列LCS）则不必。比如字符串“ acdfg ”同“ akdfc ”的最长公共子串为“ df ”，而它们的最长公共子序列LCS是“ adf ”，LCS可以使用动态规划法解决。
解法一
或许，读者初看此题，可能立马会想到用最简单粗暴的方式：两个for循环直接轮询。
double maxProductSubstring(double *a, int length)
{
double maxResult = a[0];
for (int i = 0; i < length; i++)
{
double x = 1;
for (int j = i; j < length; j++)
{
x *= a[j];
if (x > maxResult)
{
maxResult = x;
}
}
}
return maxResult;
}
但这种蛮力的方法的时间复杂度为O(n^2)，能否想办法降低时间复杂度呢？
解法二
考虑到乘积子序列中有正有负也还可能有0，我们可以把问题简化成这样：数组中找一个子序列，使得它的乘积最大；同时找一个子序列，使得它的乘积最小（负数的情况）。因为虽然我们只要一个最大积，但由于负数的存在，我们同时找这两个乘积做起来反而方便。也就是说，不但记录最大乘积，也要记录最小乘积。
假设数组为a[]，直接利用动态规划来求解，考虑到可能存在负数的情况，我们用maxend来表示以a[i]结尾的最大连续子串的乘积值，用minend表示以a[i]结尾的最小的子串的乘积值，那么状态转移方程为：
maxend = max(max(maxend * a[i], minend * a[i]), a[i]); minend = min(min(maxend * a[i], minend * a[i]), a[i]);
初始状态为maxend = minend = a[0]。
参考代码如下：
double MaxProductSubstring(double *a, int length)
{
double maxEnd = a[0];
double minEnd = a[0];
double maxResult = a[0];
for (int i = 1; i < length; ++i)
{
double end1 = maxEnd * a[i], end2 = minEnd * a[i];
maxEnd = max(max(end1, end2), a[i]);
minEnd = min(min(end1, end2), a[i]);
maxResult = max(maxResult, maxEnd);
}
return maxResult;
}
动态规划求解的方法一个for循环搞定，所以时间复杂度为O(n)。
