Bruce Chen's Blog

quick notes

0%

前端面试中的常见的算法问题

发表于 分类于

Q1 判断一个单词是否是回文？

回文是指把相同的词汇或句子，在下文中调换位置或颠倒过来，产生首尾回环的情趣，叫做回文，也叫回环。比如 mamam redivider .

很多人拿到这样的题目非常容易想到用 for 将字符串颠倒字母顺序然后匹配就行了。其实重要的考察的就是对于 reverse 的实现。其实我们可以利用现成的函数，将字符串转换成数组，这个思路很重要，我们可以拥有更多的自由度去进行字符串的一些操作。

1
2
3
function checkPalindrom(str) {
    return str == str.split('').reverse().join('');
}

Q2 去掉一组整型数组重复的值

1
2
3
比如输入: [1,13,24,11,11,14,1,2]
输出: [1,13,24,11,14,2]
需要去掉重复的11 和 1 这两个元素。

这道问题出现在诸多的前端面试题中，主要考察个人对 Object 的使用，利用 key 来进行筛选。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* unique an array
**/
let unique = function(arr) {
  let hashTable = {};
  let data = [];
  for(let i=0,l=arr.length;i<l;i++) {
    if(!hashTable[arr[i]]) {
      hashTable[arr[i]] = true;
      data.push(arr[i]);
    }
  }
  return data

}

module.exports = unique;

Q3 统计一个字符串出现最多的字母

给出一段英文连续的英文字符串，找出重复出现次数最多的字母

1
2
3
输入 ： afjghdfraaaasdenas

输出 ： a

前面出现过去重的算法，这里需要是统计重复次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function findMaxDuplicateChar(str) {
  if(str.length == 1) {
    return str;
  }
  let charObj = {};
  for(let i=0;i<str.length;i++) {
    if(!charObj[str.charAt(i)]) {
      charObj[str.charAt(i)] = 1;
    }else{
      charObj[str.charAt(i)] += 1;
    }
  }
  let maxChar = '',
      maxValue = 1;
  for(var k in charObj) {
    if(charObj[k] >= maxValue) {
      maxChar = k;
      maxValue = charObj[k];
    }
  }
  return maxChar;

}

module.exports = findMaxDuplicateChar;

Q4 排序算法

如果抽到算法题目的话，应该大多都是比较开放的题目，不限定算法的实现，但是一定要求掌握其中的几种，所以冒泡排序，这种较为基础并且便于理解记忆的算法一定需要熟记于心。冒泡排序算法就是依次比较大小，小的的大的进行位置上的交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
function bubbleSort(arr) {
    for(let i = 0,l=arr.length;i<l-1;i++) {
        for(let j = i+1;j<l;j++) {
          if(arr[i]>arr[j]) {
                let tem = arr[i];
                arr[i] = arr[j];
                arr[j] = tem;
            }
        }
    }
    return arr;
}
module.exports = bubbleSort;

除了冒泡排序外，其实还有很多诸如 插入排序,快速排序，希尔排序等。每一种排序算法都有各自的特点。全部掌握也不需要，但是心底一定要熟悉几种算法。 比如快速排序，其效率很高，而其基本原理如图(来自 wiki)：

image

算法参考某个元素值，将小于它的值，放到左数组中，大于它的值的元素就放到右数组中，然后递归进行上一次左右数组的操作，返回合并的数组就是已经排好顺序的数组了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function quickSort(arr) {

    if(arr.length<=1) {
        return arr;
    }

    let leftArr = [];
    let rightArr = [];
    let q = arr[0];
    for(let i = 1,l=arr.length; i<l; i++) {
        if(arr[i]>q) {
            rightArr.push(arr[i]);
        }else{
            leftArr.push(arr[i]);
        }
    }

    return [].concat(quickSort(leftArr),[q],quickSort(rightArr));
}

module.exports = quickSort;

安利大家一个学习的地址，通过动画演示算法的实现。
HTML5 Canvas Demo: Sorting Algorithms

Q5 不借助临时变量，进行两个整数的交换

1
输入 a = 2, b = 4 输出 a = 4, b =2

这种问题非常巧妙，需要大家跳出惯有的思维，利用 a , b 进行置换。

主要是利用 + - 去进行运算，类似 a = a + ( b - a) 实际上等同于最后 的 a = b;

1
2
3
4
5
6
7
8
function swap(a , b) {
  b = b - a;
  a = a + b;
  b = a - b;
  return [a,b];
}

module.exports = swap;

Q6 使用 canvas 绘制一个有限度的斐波那契数列的曲线？

image

数列长度限定在 9.

斐波那契数列，又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列主要考察递归的调用。我们一般都知道定义

1
fibo[i] = fibo[i-1]+fibo[i-2];

生成斐波那契数组的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function getFibonacci(n) {
  var fibarr = [];
  var i = 0;
  while(i<n) {
    if(i<=1) {
      fibarr.push(i);
    }else{
      fibarr.push(fibarr[i-1] + fibarr[i-2])
    }
    i++;
  }

  return fibarr;
}

剩余的工作就是利用 canvas arc 方法进行曲线绘制了

DEMO

Q7 找出下列正数组的最大差值比如:

1
2
3
输入 [10,5,11,7,8,9]

输出 6

这是通过一道题目去测试对于基本的数组的最大值的查找，很明显我们知道，最大差值肯定是一个数组中最大值与最小值的差。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function getMaxProfit(arr) {

    var minPrice = arr[0];
    var maxProfit = 0;

    for (var i = 0; i < arr.length; i++) {
        var currentPrice = arr[i];

        minPrice = Math.min(minPrice, currentPrice);

        var potentialProfit = currentPrice - minPrice;

        maxProfit = Math.max(maxProfit, potentialProfit);
    }

    return maxProfit;
}

Q8 随机生成指定长度的字符串

实现一个算法，随机生成指定长度的字符串。

1
比如给定 长度 8  输出 4ldkfg9j
1
2
3
4
5
6
7
8
9
10
11
12
function randomString(n) {
  let str = 'abcdefghijklmnopqrstuvwxyz9876543210';
  let tmp = '',
      i = 0,
      l = str.length;
  for (i = 0; i < n; i++) {
    tmp += str.charAt(Math.floor(Math.random() * l));
  }
  return tmp;
}

module.exports = randomString;

Q9 实现类似 getElementsByClassName 的功能

自己实现一个函数，查找某个 DOM 节点下面的包含某个 class 的所有 DOM 节点？不允许使用原生提供的 getElementsByClassName querySelectorAll 等原生提供 DOM 查找函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function queryClassName(node, name) {
  var starts = '(^|[ \n\r\t\f])',
       ends = '([ \n\r\t\f]|$)';
  var array = [],
        regex = new RegExp(starts + name + ends),
        elements = node.getElementsByTagName("*"),
        length = elements.length,
        i = 0,
        element;

    while (i < length) {
        element = elements[i];
        if (regex.test(element.className)) {
            array.push(element);
        }

        i += 1;
    }

    return array;
}

Q10 使用 JS 实现二叉查找树(Binary Search Tree)

一般叫全部写完的概率比较少，但是重点考察你对它的理解和一些基本特点的实现。 二叉查找树，也称二叉搜索树、有序二叉树（英语：ordered binary tree）是指一棵空树或者具有下列性质的二叉树：

  • 任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  • 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  • 任意节点的左、右子树也分别为二叉查找树；
  • 没有键值相等的节点。二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低。为 O(log n)。二叉查找树是基础性数据结构，用于构建更为抽象的数据结构，如集合、multiset、关联数组等。

image

在写的时候需要足够理解二叉搜素树的特点，需要先设定好每个节点的数据结构

1
2
3
4
5
6
7
8
class Node {
  constructor(data, left, right) {
    this.data = data;
    this.left = left;
    this.right = right;
  }

}

树是有节点构成，由根节点逐渐延生到各个子节点，因此它具备基本的结构就是具备一个根节点，具备添加，查找和删除节点的方法.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
class BinarySearchTree {

  constructor() {
    this.root = null;
  }

  insert(data) {
    let n = new Node(data, null, null);
    if (!this.root) {
      return this.root = n;
    }
    let currentNode = this.root;
    let parent = null;
    while (1) {
      parent = currentNode;
      if (data < currentNode.data) {
        currentNode = currentNode.left;
        if (currentNode === null) {
          parent.left = n;
          break;
        }
      } else {
        currentNode = currentNode.right;
        if (currentNode === null) {
          parent.right = n;
          break;
        }
      }
    }
  }

  remove(data) {
    this.root = this.removeNode(this.root, data)
  }

  removeNode(node, data) {
    if (node == null) {
      return null;
    }

    if (data == node.data) {
      // no children node
      if (node.left == null && node.right == null) {
        return null;
      }
      if (node.left == null) {
        return node.right;
      }
      if (node.right == null) {
        return node.left;
      }

      let getSmallest = function(node) {
        if(node.left === null && node.right == null) {
          return node;
        }
        if(node.left != null) {
          return node.left;
        }
        if(node.right !== null) {
          return getSmallest(node.right);
        }

      }
      let temNode = getSmallest(node.right);
      node.data = temNode.data;
      node.right = this.removeNode(temNode.right,temNode.data);
      return node;

    } else if (data < node.data) {
      node.left = this.removeNode(node.left,data);
      return node;
    } else {
      node.right = this.removeNode(node.right,data);
      return node;
    }
  }

  find(data) {
    var current = this.root;
    while (current != null) {
      if (data == current.data) {
        break;
      }
      if (data < current.data) {
        current = current.left;
      } else {
        current = current.right
      }
    }
    return current.data;
  }

}

module.exports = BinarySearchTree;

Q11 数组全排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var arr = ['foo','bar','hello','world'];
var count = 1;
function getStr(a){
	for (var i = 0; i < arr.length; i++) {
		// indexOf 是es6数组的方法,如果不存在返回-1，存在返回下标
		if(a.indexOf(arr[i])<0){

			//数组 a 中不存在 arr[i],将arr[i]添加到数组末尾
			a.push(arr[i]);

			if(a.length==arr.length){
				console.log(count++ + ': ' +a.join(""));
			}else{
				//结束一次for循环  进行了4次递归 getStr(['foo']) getStr(['bar']) getStr(['hello']) getStr(['world'])
				getStr(a);

			}
			//一定从数组 a 中删除arr[i],进行下次循环，如果不删除就只能获得一种结果了
			a.pop();
		}
	}
}
getStr([])

除去注释只用了 15 行代码，通过上面的方法 我们实现了单个数组全排
更多方法阅读

Q12 最大连续子序列和

思路： 比较若干个连续

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
var arr = [1, 6, -1, 5, 4, -7, 2, 3];
var maxSum = arr[0],
	sum = arr[0];
for(var i=1;i<arr.length;i++) {
	if(sum< 0) {
		sum = arr[i];
	} else {
		sum += arr[i];
	}
	if (sum > maxSum) {
		maxSum = sum;
	}
 	console.log(sum, maxSum);

}
console.log(maxSum);


function maxSeq(arr) {
    var sum=arr[0], maxSum = arr[0]

    for(var i=1; i< arr.length; i++) {
        if (sum < 0) {
            sum = arr[i]
        } else {
            sum += arr[i]
        }

        if (sum > maxSum) {
            msxSum = sum
        }
    }

    return maxSum
}

Q13 DOM 遍历深度优先和广度优先算法

1. 深度优先

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 递归
let arr = []
function deepTraversal(node) {
  if(!node) return;
  arr.push(node)
  for (var i = 0; i< node.children.length; i++) {
    deepTraversal(node.children[i])
  }

}
// 非递归
let arr =[]
function deepTraversal(node) {
  if(!node) return;
  var stack = [node];
  while (stack.length) {
    var item = stack.shift();
    arr.push(item);
    var children = item.children;
    for (var i = children.length - 1; i >= 0 ; i--) {
      stack.unshift(children[i]);
    }
  }
}

2. 广度优先

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 递归
let nodes = []; //nodes可放函数中
let i = 0;
function wideTraversal(node) {
  if (node) {
    nodes.push(node);
    wideTraversal(node.nextElementSibling);
    node = nodes[i++];
    wideTraversal(node.firstElementChild);
  }
}
wideTraversal(rootElement);
console.log(nodes);

let nodes = [rootElement]; //nodes可放函数中
let stack = []
function wideTraversal(node) {
  if (node) {
    for(var i =0; i< node.children.length; i++) {
      nodes.push(node.children[i]);
      stack.push(node.children[i])
    }
    wideTraversal(stack.shift())
  }
}
wideTraversal(rootElement);

// 非递归  先进先出
let arr = [];
let stack = [rootElement]
function wideTraversal(node) {
  while(stack.length) {
    let item = stack.shift()
    arr.push(item)
    for (var i = 0; i < item.children.length;i++) {
      stack.push(item.children[i]);
    }
  }
}
wideTraversal(rootElement);
console.log(arr);

Q14 JS 洗牌算法

塔罗牌

举例来说，我们有一个如下图所示的数组，数组长度为 9，数组内元素的值顺次分别是 1~9：

image

从上面这个数组入手，我们要做的就是打乱数组内元素的顺序：

image

代码实现

1
2
3
4
5
6
7
8
9
10
Array.prototype.shuffle = function () {
    let input = this;
    for (let i = input.length - 1; i>= 0; i--) {
        let randomIndex = Math.floor(Math.random() * (i + 1));
        let itemAtIndex = input[randomIndex];
        input[randomIndex] = input[i];
        input[i] = itemAtIndex;
    }
    return input;
}

在上面的代码中，我们创建了一个 shuffle() 方法，该方法用于随机排列数组内的元素。

此外，我们将该方法挂载在了 Array 对象的原型下面，所以任何数组都可以直接调用该方法：

1
2
let tempArray = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
tempArray.shuffle();

Q15 假设现在有两个函数 function A()和 function B()，现在希望创建一个新的函数 function C()，新函数的逻辑是将自己接收到的前两个参数传给函数 A，剩余所有参数传给函数 B，请用原生 javascript 实现函数 C

举例：

如果调用函数 C：C[a,b,c,d,e]

相当于调用函数 A 和函数 B：A(a,b),B(c,d,e)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function C(){
     var a_args=Array.prototype.slice.call(arguments,0,2);
     var b_args=Array.prototype.slice.call(arguments,2);
     A.apply(this,a_args);
     B.apply(this,b_args);
}



function C(...s){
      A.call(this,s[0],s[1]);
      B.apply(this,s.slice(2));
}



function C(...s){
      A.apply(this,s.slice(0,2));
      B.apply(this,s.slice(2));
}



function C(){
   A(arguments[0],arguments[1]);
   B(Array.prototype.slice.call(arguments,2));
}


function C(a1,a2,...args) {
    A(a1,a2)
    B(...args)
}

Array.prototype.slice 表示数组的原型中的 slice 方法。这个 slice 方法返回的是一个 Array 类型的对象。可以把类数组对象转化成真正的数组，与 Array.from 类似。

Q16 请实现以下 template 方法，用于模板解析

var compiled = template(“hello <%=user%>!”);
compiled({“user”:”world”}); => hello world!

var compiled = template(“welocm to <%=location%>!”);
compiled({“location”:”CVTE”}); => welcom to CVTE!;

1
2
3
4
5
6
7
8
9
10
11
function template(source){
   var temp=source;
   return function(obj){
       for(var prop in obj){
              var tpl="<%="+prop+"%>";
              temp=temp.replace(tpl,obj[prop]);
       }
       console.log(temp);
   }
}

Q17 写一个函数，将传进去的数组按深度展开

例子：
list:[1,2,[3,4],[5,6,[7,8],9],10,11]

depth 等于 1 时输出

depth = 1 :[1,2,3,4,5,6,[7,8],9,10,11]

depth 等于 2 时输出

depth = 2 :[1,2,3,4,5,6,7,8,9,10,11]

1
2
3
4
5
6
7
8
9
function flattern(array,num = 0) {
	var newArray = array;
	for(let i = 0; i < num; i ++) {
		newArray = [].concat(...newArray)
	}
	return newArray;
}

console.log(flattern([1,2,3,[4,5,[6,7]]],2))

Q18 实现一个简单的模板引擎

例子：

1
2
3
4
5
6
let template = '我是{{name}}，年龄{{age}}，性别{{sex}}';
let data = {
  name: '姓名',
  age: 18
}
render(template, data); // 我是姓名，年龄18，性别undefined
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
方法1：先将模板与数据中均存在的属性替换掉，再将数据中不存在模板中存在的属性设置为undefined
function render(template, data) {
	for(let key in data) {
		if(template.indexOf(key)) {
			var reg =new RegExp("{{" + key + "}}","g");
			template = template.replace(reg,data[key])
		}
	}

	template = template.replace(/\{\{(\w+)\}\}/g,'undefined')

	return template;
}


方法2 迭代，一个一个替换，注意exec匹配到的第一项是匹配字符串，第二项为分组内的字符串[{{name}},name]
function render(template, data) {
  const reg = /\{\{(\w+)\}\}/; // 模板字符串正则
  if (reg.test(template)) { // 判断模板里是否有模板字符串
    const name = reg.exec(template)[1]; // 查找当前模板里第一个模板字符串的字段
    template = template.replace(reg, data[name]); // 将第一个模板字符串渲染
    return render(template, data); // 递归的渲染并返回渲染后的结构
  }
  return template; // 如果模板没有模板字符串直接返回
}

Q19 动态规划

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。例如，给定三角形：

[[2],[3,4],[6,5,7],[4,1,8,3]]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

动态规划我个人的理解是：能将一个大问题分解为一个个小问题，并且这些小问题之间有共性能重复调用。那么如何判断这道题是否可以用到动态规划，首先从底往上看，[6,5,7]对应的最小路径很明显可以看出分别是[1,1,3]，那么后两层的最短路径是[7,6,10]，再往上看[3,4]的最短路径也能明显看出是[9,10]，那么 2 对应的最短路径很明显就是 11。其实从这里就能看出每层分析判断的逻辑是一致的。js 代码如下：

1
2
3
4
5
6
7
8
9
10
11
const minimumTotal = triangle => {
    // es6方法填充数组
    const dp = Array.of(...triangle[triangle.length - 1])
	for (let i = dp.length - 2; i >= 0; i--) {
        for (let j = 0; j < triangle[i].length; j++) {
            // 状态转移方程
            dp[j] = Math.min(dp[j], dp[j + 1]) + triangle[i][j]
          }
    }
    return dp[0]
}