数据结构知识 ø
对算法的理解
对前端er来说,算法并非银弹「极端有效的解决方案」,对前端er最重要的,最关键的,是工程能力,所谓工程能力,本质是“解决问题的能力”,无论是硬编码实力、还是架构思想,其本质都是为了解决问题这个终极目标而服务。
前端er学习算法的路径
# 基础数据结构
# 数组「JS」
1.创建数组
const arr = new Array();
2.for循环的方法
(1).forEach()方法:
arr.forEach((item, index)=> {
// 输出数组的元素值,输出当前索引
console.log(item, index)
})
(2).map 方法
map 方法在调用形式上与 forEach 无异,区别在于 map 方法会根据你传入的函数逻辑对数组中每个元素进行处理、进而返回一个全新的数组。
所以其实 map 做的事情不仅仅是遍历,而是在遍历的基础上“再加工”。当我们需要对数组内容做批量修改、同时修改的逻辑又高度一致时,就可以调用 map 来达到我们的目的
const newArr = arr.map((item, index)=> {
// 输出数组的元素值,输出当前索引
console.log(item, index)
// 在当前元素值的基础上加1
return item+1
})
1.初始化二维数组
const len = arr.length
for(let i=0;i<len;i++) {
// 将数组的每一个坑位初始化为数组
arr[i] = []
}
# 链表
处理链表的本质,是处理链表结点之间的指针关系。
链表常见方法
- dummy节点
链表问题中,比较常见的就是无法找到前驱节点,那么如果无法找到的话,就人为造一个!
# 基本API
1.反转字符串:
const str = 'juejin';
const res = str.split('').reverse().join('');
console.log(res);
2.判断一个字符串是否是回文字符
(1)通过反转判断两者是否相等来做
function isPalindrome(str){
const res = str.split('').reverse().join('');
// if(res === str){
// return true;
// }
// return false;
return res === str;
}
(2)通过对称性来做
function isPalidrome(str) {
const len = str.length;
for(let i=0;i<len;i++){
if(str[i]!==str[len-i-1]){
return false;
}
}
return true;
}
(3)工具方法:判断一个字符串是否回文
function isP(l,r){
while(l<r){
if(s[l]!==s[r]) return false;
l ++;
r --;
}
return true;
}
# 树
# 最小生成树
# 推文
# 克鲁斯克尔算法
这是一个小网站,可以帮助你理解克鲁斯克尔算法
(还挺好玩的
# DFS
# 深度优先搜索的本质——栈结构
- 当你可以使用DFS即递归的时候,你会不自觉的使用栈的思路,只不过没有必要专门去建一个栈,只需要用递归的思路放进去循环就好了。
- 当你无法用DFS即递归的思路去解决这个问题的时候,不妨想一下,能不能用DFS的本质,即栈的思路去解决这个问题!
# 模版
function xxx(入参) {
前期的变量定义、缓存等准备工作
// 定义路径栈
const path = []
// 进入 dfs
dfs(起点)
// 定义 dfs
dfs(递归参数) {
if(到达了递归边界) {
结合题意处理边界逻辑,往往和 path 内容有关
return
}
// 注意这里也可能不是 for,视题意决定
for(遍历坑位的可选值) {
path.push(当前选中值)
处理坑位本身的相关逻辑
path.pop()
}
}
}
遍历所有情况的模版
function dfs(index) {
// 每次进入,都意味着组合内容更新了一次,故直接推入结果数组
res.push(subset.slice())
// 从当前数字的索引开始,遍历 nums
for(let i=index;i<len;i++) {
// 这是当前数字存在于组合中的情况
subset.push(nums[i])
// 基于当前数字存在于组合中的情况,进一步 dfs
dfs(i+1)
// 这是当前数字不存在与组合中的情况
subset.pop()
}
}
// 返回结果数组
return res
};
# 高频函数 & some details & some tips
- splice()
删除函数(也可以用来添加函数)
- slice()
复制元素到新的数组里,复制左闭右开(
展开运算符
indexOf(),从前往后找第一个要的这个数的位置
找出字符串中的最长单词
"The quick brown fox jumped over the lazy dog"
大致是这样的一个字符串,怎么找捏?
let str = "The quick brown fox jumped over the lazy dog"
// 首先把空格去掉
// 这里就相当于把他变成了字符串构成的数组了
str = str.split(' ')
// 然后我们可以遍历每个元素来找
let maxlen = 0;
for(let i=0;i<str.length;i++){
if(str[i].length>maxlen) maxlen = str[i].length;
}
return maxlen