数据结构和算法

参考数据结构和算法入门

快速排序

利用分治策略来将一个序列分为两个子序列

执行流程

从序列中选择一个轴点元素pivot从最后一个元素向前遍历

我们的策略是：每次选择第0位置的元素为轴点元素

利用pivot将数组分割成2个子数组

将小于pivot的元素放在pivot的左侧
将大于pivot的元素放在pivot的右侧
将等于pivot的元素放在pivot的哪侧都可以，本文选择左侧

对子序列进行步骤1和步骤2操作

直到不能再分割(子序列中只剩下一个元素)

先介绍了下快排的执行流程，脑海中先有个大致的思路。

总结一下，就是先把一个大数组通过第一个元素将之分割成2个小的数组，并且以该轴点为界，小于它的在左边，大于它的在右边，然后递归对2个小数组执行步骤1、2操作，直到不能再分割。

时间复杂度：nlogn

二分查找

二分查找有两个限制条件：

查找的数量只能是一个，不能是多个
查找的对象在逻辑上必须是有序的

在查找一个元素的时候，left下标和right下标会越来越靠近，甚至会指向一处，这个过程中left始终在right的左边（即：left <= right）。但如果一直找不到那个元素，两个下标必然会相互交错（即: left > right），这时循环结束。所以循环条件总结下来就是：while（left <= right）。

数组转成树结构

后台返回一个扁平的数据结构，转成树。打平的数据内容如下:

let arr = [
    {id: 1, name: '部门1', pid: 0},
    {id: 2, name: '部门2', pid: 1},
    {id: 3, name: '部门3', pid: 1},
    {id: 4, name: '部门4', pid: 3},
    {id: 5, name: '部门5', pid: 4},
]

输出结果:

[
    {
        "id": 1,
        "name": "部门1",
        "pid": 0,
        "children": [
            {
                "id": 2,
                "name": "部门2",
                "pid": 1,
                "children": []
            },
            {
                "id": 3,
                "name": "部门3",
                "pid": 1,
                "children": [
                    // 结果 ,,,
                ]
            }
        ]
    }
]

合格版本:

const flatArr = (list, parentId) => {
    if(!Array.isArray(list)) return []
    let target = [].concat(list.filter(i => i.pid === parentId))

    target.forEach(item => {
        item.children = flatArr(list, item.id)
    })
    return target  
}

性能优化版本:

function arrayToTree(items) {
  const result = [];   // 存放结果集
  const itemMap = {};  // 
  for (const item of items) {
    const id = item.id;
    const pid = item.pid;

    if (!itemMap[id]) {
      itemMap[id] = {
        children: [],
      }
    }

    itemMap[id] = {
      ...item,
      children: itemMap[id]['children']
    }

    const treeItem =  itemMap[id];

    if (pid === 0) {
        result.push(treeItem);
        continue;
    }
    if (!itemMap[pid]) {
        itemMap[pid] = {
            children: [],
        }
    }
    itemMap[pid].children.push(treeItem)
  }
  return result;
}

深拷贝

简单粗暴

function deepClone(source) {
    if(!source) return source
    return JSON.parse(JSON.stringify(source))
}

递归版本1

function deepClone(source) {
    if(typeof source !== 'object') return source
    let target = Array.isArray(source) ? [] : {}
    Object.keys(source).forEach(key => {
        target[key] = deepClone(source[key])
    })
    return target
}

递归版本2,解决内存泄漏

function forEach(array, iteratee) {
    let index = -1;
    const length = array.length;
    while (++index < length) {
        iteratee(array[index], index);
    }
    return array;
}
function clone(target, map = new WeakMap()) {
    if (typeof target === 'object') {
        const isArray = Array.isArray(target);
        let cloneTarget = isArray ? [] : {};

        if (map.get(target)) {
            return map.get(target);
        }
        map.set(target, cloneTarget);

        const keys = isArray ? undefined : Object.keys(target);
        forEach(keys || target, (value, key) => {
            if (keys) {
                key = value;
            }
            cloneTarget[key] = clone(target[key], map);
        });

        return cloneTarget;
    } else {
        return target;
    }
}

终极版本,解决其他数据类型

const map = new Map();
map.set('key', 'value');
map.set('ConardLi', 'code秘密花园');

const set = new Set();
set.add('ConardLi');
set.add('code秘密花园');

const target = {
    field1: 1,
    field2: undefined,
    field3: {
        child: 'child'
    },
    field4: [2, 4, 8],
    empty: null,
    map,
    set,
    bool: new Boolean(true),
    num: new Number(2),
    str: new String(2),
    symbol: Object(Symbol(1)),
    date: new Date(),
    reg: /\d+/,
    error: new Error(),
    func1: () => {
        console.log('code秘密花园');
    },
    func2: function (a, b) {
        return a + b;
    }
};

const mapTag = '[object Map]';
const setTag = '[object Set]';
const arrayTag = '[object Array]';
const objectTag = '[object Object]';
const argsTag = '[object Arguments]';

const boolTag = '[object Boolean]';
const dateTag = '[object Date]';
const numberTag = '[object Number]';
const stringTag = '[object String]';
const symbolTag = '[object Symbol]';
const errorTag = '[object Error]';
const regexpTag = '[object RegExp]';
const funcTag = '[object Function]';

const deepTag = [mapTag, setTag, arrayTag, objectTag, argsTag];
function isObject(target) {
    const type = typeof target;
    return target !== null && (type === 'object' || type === 'function');
}

function getType(target) {
    return Object.prototype.toString.call(target);
}

function getInit(target) {
    // new Set,new Map,new Object,new Array
    const Ctor = target.constructor;
    return new Ctor();
}

function cloneSymbol(targe) {
    return Object(Symbol.prototype.valueOf.call(targe));
}

function cloneReg(targe) {
    const reFlags = /\w*$/;
    const result = new targe.constructor(targe.source, reFlags.exec(targe));
    result.lastIndex = targe.lastIndex;
    return result;
}

function cloneFunction(func) {
    const bodyReg = /(?<={)(.|\n)+(?=})/m;
    const paramReg = /(?<=\().+(?=\)\s+{)/;
    const funcString = func.toString();
    if (func.prototype) {
        const param = paramReg.exec(funcString);
        const body = bodyReg.exec(funcString);
        if (body) {
            if (param) {
                const paramArr = param[0].split(',');
                return new Function(...paramArr, body[0]);
            } else {
                return new Function(body[0]);
            }
        } else {
            return null;
        }
    } else {
        return eval(funcString);
    }
}

function cloneOtherType(targe, type) {
    const Ctor = targe.constructor;
    switch (type) {
        case boolTag:
        case numberTag:
        case stringTag:
        case errorTag:
        case dateTag:
            return new Ctor(targe);
        case regexpTag:
            return cloneReg(targe);
        case symbolTag:
            return cloneSymbol(targe);
        case funcTag:
            return cloneFunction(targe);
        default:
            return null;
    }
}


function deepClone(obj, map = new WeakMap()) {
  // 基本类型
  if (!isObject(obj)) {
    return obj;
  }
  // 新建合适的初始化对象，便于后续拷贝赋值
  let target;
  const type = getType(obj);
  // 可遍历类型需要针对性地创建一个初始值
  if (deepTag.includes(type)) {
    target = getInit(obj, type);
  } else {
    return cloneOtherType(obj, type);
  }
  // 防止循环引用
  if (map.get(obj)) {
    return map.get(obj);
  }
  map.set(obj, target);
  // 克隆Map
  if (type === mapTag) {
    obj.forEach((value, key) => {
      target.set(key, deepClone(value, map));
    });
    return target;
  }
  // 克隆Set
  if (type === setTag) {
    obj.forEach(value => {
      target.add(deepClone(value, map));
    });
    return target;
  }
  // 克隆对象和数组
  Object.keys(obj).forEach(key => {
    target[key] = deepClone(obj[key], map);
  });
  return target;
}

根据id查找节点

let tree = {
    id: '1',
    label: 'first',
    children: [
        {
            id: '2',
            label: 'second'
        },
        {
            id: '3',
            label: 'third',
            children: [
                {
                    id: '4',
                    label: 'fourth'
                },
                {
                    id: '5',
                    label: 'fifth'
                }
            ]
        }
    ]
};

interface TreeNode {
  id: string;
  label: string;
  children?: TreeNode[];
}


//请实现一个查询函数，通过输入Tree 的 Root Node 和 Id，返回与其匹配的节点，函数原型如下（*注意：请不要在函数内部直接用 console.log 打印出来*）
function findNodeById(root: TreeNode, id: string): TreeNode {
  // 1.当前根节点匹配，直接返回结果
  if(root.id === id) return root;
  // 2.递归查看children
  if(root.children) {
    for(let i = 0; i < root.children.length; i++) {
      const child = root.children[i];
      const targetNode = findNodeById(child, id);
      if(!targetNode) return targetNode;
    }
  }
  // 3.未找到，返回null
  return null;
}

学生分组

// 成绩等级分为A、B和C三级
function getGrade(score){
	return score < 60 ? 'C' :
         score < 80 ? 'B' : 'A';
};

// 学生及其成绩
let students = [
	{name: '张三', score: 84},
	{name: '李四', score: 58},
	{name: '王五', score: 99},
	{name: '赵六', score: 69}
];


/*实现该函数： groupBy(students); 
输出为： 

{
	'A': [
		{name: '王五', score: 99},
		{name: '张三', score: 84}
	],
	'B': [{name: '赵六', score: 69}],
	'C': [{name: '李四', score: 58}]
}
*/

function groupBy(students) {
  // 请实现该 groupBy 函数，将学生按照成绩等级进行分组。
  return students.reduce((obj, student) => {
    // 获取当前学生的等级
    const grade = getGrade(student.score)
    // 获取缓存的等级对应学生列表数据。若为空，则初始化空数组
    if(obj[grade]) {
      obj[grade] = []
    }
    // 将该学生加入到对应的等级列表
    obj[grade].push(student)
    
    // next
    return obj
  }, {})
}

console.log(groupBy(students));

唯一名字

const tree = {
    id: '1',
    type: 'View',
    name: 'view',
    children: [
        {
            id: '2',
            type: 'View',
            name: 'view_1',
        },
        {
            id: '3',
            type: 'Button',
            name: 'button',
        }
    ]
}

// 获取唯一名称，如存在button、button_2，则返回button_1
// 若存在button、button_1、button_3，则返回button_2
function getIncName(srcName, tree) {
    // 1.判空
    if(!srcName) throw new Error('name不允许为空')
    
    function getIndex(name) {
        const res = name.match(/\w+_(\d+)/)
        if(!res) return 0
        return Number(res[1])
    }
    function getName(tree, type, list = []) {
        if(tree.type === type) {
            const index = getIndex(tree.name)
            list[index] = 1
        }
        if(tree.children) {
            for(let i = 0; i < tree.children.length; i++) {
                const item = tree.children[i]
                getName(item, type, list)
            }
        }
    }

    // 存放type对应的节点
    const list = []
    // 获取type
    const type = srcName.charAt(0).toUpperCase() + srcName.slice(1)
    getName(tree, type, list)

    // 若数组中的某项为undefined，则说明该索引未被占用
    // 若数组项全被占用，则取数组长度
    let targetIndex = 0
    for(let i = 0; i <= list.length; i++) {
        if(!list[i]) {
            targetIndex = i
            break;
        }
    }

    // 索引为0特殊处理
    return targetIndex === 0 ? srcName : `${srcName}_${targetIndex}`
}

字符串解析成嵌套对象

const obj = parse('Array<Array<string, bool>>')
/**
 * obj 格式：
 * {
 *     type: 'Array',
 *     typeArgs: [
 *       {
 *          type: 'Array',
 *          typeArgs: [ 
 *              {
 *                  type: 'string'
 *              },
 *              {
 *                  type: 'bool'
 *              }
 *          ] 
 *        }
 *     ]
 * }
 * 
 */
// 解析字符串
function parse(str) {
    if(!str) throw new Error('格式错误')
    const matchs = str.match(/(<|>)/gi)
    if(!matchs) return { type: str}
    if(matchs.length % 2 !== 0) throw new Error('格式错误')
    const json = str
    .replace(/\s*/gi, '')
    .replace(/(\w+)/gi, '"type":"$1"')
    .replace(/,/gi, '},{')
    .replace(/</gi, ',"typeArgs":[{')
    .replace(/>/gi, '}]')
    .replace(/(.*)/, '{$1}')

    try {
        return JSON.parse(json)
    } catch(e) {
        throw new Error('格式错误')
    }
}

# 数据结构和算法

# 快速排序

# 执行流程

# 时间复杂度：nlogn

# 二分查找

# 数组转成树结构

# 深拷贝

# 根据id查找节点

# 学生分组

# 唯一名字

# 字符串解析成嵌套对象