前端

学习数据结构与算法基本概念

JavaScript, 数据结构

为什么学习

工作：可以看到很多大厂招聘都会问数据结构和算法的基本概念
提升：看完后联系自己的工作经历，突然明白了很多问题的原理，谈到性能时的必备知识武器
喜欢数学，烧脑也开心

举一反三

1.Js总问的pop、push、shift、unshift做一个基本的栈和队

1
2
3
4
5
6
7
8
9
10
11
12
13
var arr = [];
arr.push(1);
console.log(arr); // [1]
arr.push(2);
console.log(arr); // [1,2]
arr.push(3);
console.log(arr); // [1,2,3]
arr.pop();
console.log(arr); // [1,2]
arr.pop();
console.log(arr); // [1]
arr.pop();
console.log(arr); // []

push与pop组合，实现数组的栈方法后进先出，应用方面：进制转换、回文、递归

1
2
3
4
5
6
7
8
9
10
11
12
13
var arr = [];
arr.push(1);
console.log(arr); // [1]
arr.push(2);
console.log(arr); // [1,2]
arr.push(3);
console.log(arr); // [1,2,3]
arr.shift();
console.log(arr); // [2,3]
arr.shift();
console.log(arr); // [3]
arr.shift();
console.log(arr); // []

push与shift组合，实现数组的队列方法先进先出，应用方面：基数排序、优先队列

2.Dom嵌套太深的渲染效率问题

1
2
3
4
5
6
7
8
9
//二叉树中序遍历
function inOrder(node)
{
    if(!(node == null)) {
      inOrder(node.left);
      putstr(node.show()+ " ");
      inOrder(node.right);
    }
}
  • 遍历所需时间和节点的多少有关；
  • 无论那种遍历方法，可以推测多一个深度，递归方法会多执行一遍，而同一层的话只是在该次遍历的下一个语句。
    所以渲染优化有一条建议–减少 DOM 节点：DOM 节点太多影响页面的渲染，应尽量减少 DOM 节点。

3.网易有道的一道面试题

1
2
3
4
5
将一个table转换为数组
table
  tr>td.rowspan=2{3},td.colspan=2{2}
  tr>td.rowspan=2{6},td{5}
  tr>td{1},td{4}

表格的绘制情况：

122
134
536

输出：
[
[3,2,” “],
[“ “,6,5],
[1,” “,4]
]

解题：
抽象看可以理解为一个树结构转换为数组结构，
1.i,j初始化为0，先序遍历每个节点；
2.当遇到tr节点，j=j+1,i=0；
3.当遇到td节点，判断arr[i,j]是否占位，如果占位i=i+1;
4.判断属性，arr[i,j]=value,
如果包含colspan，for(num=1,numvalue,num++),arr[i+num,j]=””;
如果包含rowspan，for(num=1,numvalue,num++),arr[i,j+num]=””;
i++;

ps:一线有个传统需要手写代码

推荐阅读

JavaScript 算法与数据结构
数据结构与算法——从零开始学习 C语言

分享到