前端常用算法
2021-07-27 本文已影响0人
wxyzcctn
1. 通过parentId生成树形结构
let data = [
{
id: '1-2-1',
lable: '第1-2-1级',
parentId: '1-2'
},
{
id: '1',
lable: '第1级'
},
{
id: '1-1',
lable: '第1-1级',
parentId: '1'
},
{
id: '2-1',
lable: '第2-1级',
parentId: '2'
},
{
id: '4',
lable: '第4级'
},
{
id: '2-2',
lable: '第2-2级',
parentId: '2'
},
{
id: '1-2',
lable: '第1-2级',
parentId: '1'
},
{
id: '2',
lable: '第2级'
},
{
id: '3',
lable: '第3级'
},
{
id: '2-2-1',
lable: '第2-2-1级',
parentId: '2-2'
},
]
- 第一种
function generateTree(data) {
const tree = [];
const parentMap = {};
data.forEach(item => {
parentMap[item.id] = true;
});
data.forEach(item => {
if (!item.parentId) {
// 在原始数据中不存在parentId时就是根节点，tree中首先放入这类节点
item._root = true;
tree.push(item);
} else if (!parentMap[item.parentId]) {
// 一个节点有parentId，但这个parentId对应id节点没有也作为一个根节点
tree.push(item);
}
data.forEach(each => {
// 对每一个节点遍历所有节点，找到该节点的子节点
// 在遍历所有节点过程中，如果遍历到该节点本身直接跳过
// 如果遍历到的节点的parentId与该节点的id相同，此节点就是该节点的子节点
if (each.id === item.id) return;
if (each.parentId === item.id) {
if (!item.children) return (item.children = [each]);
item.children.push(each);
}
});
});
return tree
}
- 第二种（时间复杂度最小）
function createTree(data){
const treeList = [];
const treeMap = {};
// 如果原始数组长度为0或数组不存在，返回树结构为[]
if (!data || data.length === 0) {
return treeList;
}
// 将原始数据的每个节点存入一个对象中，这个对象的key为节点id，value为节点自身
for (let i = 0; i < data.length; i++) {
treeMap[data[i].id] = { ...data[i], children: [] };
}
// 遍历上一步生成的节点对象,如果对象一个value的parentId存在,将该节点作为key为parentId的节点的children值
// 如果对象一个value的parentId不存在则为根节点存入树结构数组中
for (let key in treeMap) {
const value = treeMap[key];
if (value.parentId !== null && value.parentId !== '' && value.parentId !== undefined) {
if (!treeMap[value.parentId]) continue;
treeMap[value.parentId].children.push(value);
} else {
treeList.push(value);
}
}
return treeList
}
2. 实现数组的随机排序
var arr = [1,2,3,4,5,6];
function randomOrder(i,j){
return Math.random() > 0.5 ? -1 : i
}
arr.sort(randomOrder)
3. 兼容性较强的事件侦听器函数
const EventUtils = {
// 视能力分别使用dom0||dom2||IE方式 来绑定事件
// 添加事件
addEvent: function(element, type, handler) {
if (element.addEventListener) {
element.addEventListener(type, handler, false);
} else if (element.attachEvent) {
element.attachEvent("on" + type, handler);
} else {
element["on" + type] = handler;
}
},
// 移除事件
removeEvent: function(element, type, handler) {
if (element.removeEventListener) {
element.removeEventListener(type, handler, false);
} else if (element.detachEvent) {
element.detachEvent("on" + type, handler);
} else {
element["on" + type] = null;
}
},
// 获取事件目标
getTarget: function(event) {
return event.target || event.srcElement;
},
// 获取 event 对象的引用，取到事件的所有信息，确保随时能使用 event
getEvent: function(event) {
return event || window.event;
},
// 阻止事件（主要是事件冒泡，因为 IE 不支持事件捕获）
stopPropagation: function(event) {
if (event.stopPropagation) {
event.stopPropagation();
} else {
event.cancelBubble = true;
}
},
// 取消事件的默认行为
preventDefault: function(event) {
if (event.preventDefault) {
event.preventDefault();
} else {
event.returnValue = false;
}
}
};
4. 实现 flatten 函数
var arr = [1, 2, 3, [4, 5], [6, [7, [8]]]]
- 第一种方法：使用数组的reduce方法
function flatten(arr) {
return arr.reduce((result,item)=>{
return result.concat(Array.isArray(item) ? flatten(item) : item)
},[])
}
reduce包含两个参数：回调函数，传给total的初始值
求数组的各项值相加的和：
arr.reduce((total, item)=> { // total为之前的计算结果，item为数组的各项值
return total + item;
}, 0);
- 第二种方法：将数组转换为字符串，然后转换为一维数组
function flatten(arr) {
return arr.toString().split(",").map((item)=>{
return +item
})
}
或者（arr.join(",")能将数组多维或一维arr转换为以,分隔的字符串）
function flatten(arr) {
return arr.join(',').split(",").map((item)=>{
return +item
})
}
- 第三种方法：递归
function flatten(arr) {
var res = [];
for(let item of arr){
if(Array.isArray(item)){
res = res.concat(flatten(item))
}else{
res.push(item)
}
}
return res
}
- 第四种方法：扩展运算符
es6的扩展运算符能将二维数组变为一维
[].concat(...[1, 2, 3, [4, 5]]); // [1, 2, 3, 4, 5]
function flatten(arr) {
while(arr.some(item=>Array.isArray(item))){
arr = [].concat(...arr)
}
return arr
}
5. 实现一个sleep
sleep函数作用是让线程休眠，指定时间一到便重新唤起。
function sleep(delay){
var start = (new Date()).getTime()
while((new Date()).getTime() - start < delay){
continue;
}
}
function test(){
console.log("11111");
sleep(2000);
console.log("22222");
}
test() // 先打印出11111，2秒之后打印22222
6. 解析 URL 的查询参数为对象
let url = 'http://www.domain.com/?user=anonymous&id=123&id=456&city=%E5%8C%97%E4%BA%AC&enabled';
parseParam(url)
/* 结果
{ user: 'anonymous',
id: [ 123, 456 ], // 重复出现的 key 要组装成数组，能被转成数字的就转成数字类型
city: '北京', // 中文需解码
enabled: true, // 未指定值得 key 约定为 true
}
*/
let url = 'http://www.domain.com/?user=anonymous&id=123&id=456&city=%E5%8C%97%E4%BA%AC&enabled';
let uel2 = window.location.search; // 获取url查询字符串参数
function parseParam(url){
let message = /.+\?(.+)/.exec(url)[1]; // 获取查询字符串
let messArr = message.split('&'); // 获得将字符串以&分割得到的数组
let messObj = {}; // 结果对象
for(let item of messArr){
if(/=/.test(item)){ // 处理有value的参数
let [key,value] = item.split('=');
value = decodeURI(value); // 解码
value = decodeURIComponent(value); // 解码
value = /^\d+$/.test(value) ? parseFloat(value) : value;
// 参数值全为数字时就变为数字
if(messObj.hasOwnProperty(key)){ // 一个参数多次出现时，参数的值变为数组
messObj[key] = [].concat(messObj[key],value)
} else {
messObj[key] = value;
}
}else{ // 没有value的参数设为true
messObj[item] = true;
}
}
return messObj;
}
7. 模板引擎实现
var template1 = '我是{{name}}，年龄{{age}}，性别{{sex}}';
var data1 = {
name: '小明',
age: 18
}
render(template1, data1); // 我是小明，年龄18，性别undefined
function render(template,data){
var reg = /\{\{(\w+)\}\}/g;
const orgTem = template;
while(true) {
var match = reg.exec(orgTem);
// 正则的exec函数在每次匹配时是从上一次匹配的结束位置开始，
// 因此，为了保证匹配的位置不变，循环时需要保证其中的值保持不变
if (!match) break;
template = template.replace(match[0], data[match[1]])
}
return template
}
8. 转化为驼峰命名
var name = "get-element-by-id"
function changeName(name){
var newName = name.replace(/(\-\w)/g, function(match){
return match[1].toUpperCase()
})
return newName
}
changeName(name)
9. 查找字符串中出现最多的字符和个数
var str1 = "abcabcabcbbccccc";
function findMostL(str){
let obj = {};
for(let i = 0; i < str.length; i++){
if(obj[str[i]]){
obj[str[i]] += 1
}else{
obj[str[i]] = 1;
}
}
let max = 0;
let moreLetter = [];
for(let key in obj){
max = Math.max(obj[key],max)
}
for(let key in obj){
if(obj[key] === max){
moreLetter.push(key);
}
}
console.log('出现次数最多的字母是：',moreLetter,'出现次数为',max);
}
findMostL(str1)
