手撕代码系列 (三)

/** * 匹配括号 isValid * @param {String} symbolStr 符号字符串 * @return {Boolean} * * @logic * 1.定义一个栈数组(stack) * 2.定义字典(obj) * 3.遍历字符串 * 4.判断字符串中的每个字符与其对应的符号是否出现在字典(obj)中(如果是有效的，前者与后者是相对应的) * 5.最后判断，如果栈数组(stack)的长度为 0, 则证明是有效的。 */const isValid = symbolStr => {    let stack = [];    let obj = {        '(': ')',        '[': ']',        '{': '}',    };    for (let i = 0; i < symbolStr.length; i++) {        let ele = symbolStr[i];        // Object.prototype.hasOwnProperty.call(obj, ele)：方法是一个常用的，安全检测对象是否含有某个属性的方法，使用此方法可避免 hasOwnProperty 属性被污染或被重写的风险。        if (Object.prototype.hasOwnProperty.call(obj, ele)) {            stack.push(ele);        } else {            if (ele != obj[stack.pop()]) return false;        }    }    return !stack.length;};

// test:console.log("isValid('(){}') ------>", isValid('(){'));// isValid('(){}') ------> true// isValid('(){') ------> false

/** * 大驼峰转下换线 camelCasetoLineCase * @param {String} str 字符串 * @return 下划线格式字符串 */const camelCasetoLineCase = str => {    // /([A-Z])/g: 全局匹配大写字母 A-Z    // $1: 对应正则捕获到的内容。详细可看下方 demo    // _$1: 将捕获的内容采用下换线的形式并改成小写格式    return str.replace(/([A-Z])/g, '_$1').toLowerCase();};
// test:console.log("camelCasetoLineCase('helloWorld') ------>", camelCasetoLineCase('helloWorld')); // camelCasetoLineCase('helloWorld') ------> hello_world
// $1 Demo:var str = 'Doe, John';// 说明：$1,$2上就是按顺序对应小括号里面的小正则 捕获到的内容// 把 "Doe, John" 转换为 "John Doe" 的形式let res = str.replace(/(\w+)\s*, \s*(\w+)/, '$2 $1');console.log('res ------>', res); // res ------> John Doe

/** * 下划线转大驼峰 lineCasetocamelCase * @param {String} str 需要转换的字符串 * @return camelCase 格式字符串 */const lineCasetocamelCase = str => {    // \_：将下一个字符标记捕获到的字符。例如：\n 匹配换行符，\\ 匹配 \，\( 匹配 (    // \w: 全局匹配字母、数字、下划线。等价于 [A-Za-z0-9_]    return str.replace(/\_(\w)/g, (sourceLetter, letter) => {        console.log('sourceLetter ------>', sourceLetter, letter); // _w, w        return letter.toUpperCase();    });};
// test:console.log("linetoHump('hello_world') ------>", linetoHump('hello_world')); // linetoHump('hello_world') ------> helloWorld

/** * 反转字符串 reverseStr * @param {String} str 需要反转的字符串 * @return 反转后的字符串 */const reverseStr = str => {    let strArr = str.split('');    let left = 0;    let right = strArr.length;    while (left <= right) {        [strArr[left], strArr[right]] = [strArr[right], strArr[left]];        left++;        right--;    }    return strArr.join('');};
// test:console.log("reverseStr('helloworld') ------>", reverseStr('helloworld')); // reverseStr('helloworld') ------> dlrowolleh

/** * 深度优先搜索: DFS(Depth First Search) *      深度优先搜索：也就是一条路走到黑，然后再往回走，看看是否还有其他路径 *      分类：二叉树的前、中、后序遍历 *          前序遍历：根节点 -> 左子树 -> 右子树 *          中序遍历：左子树 -> 根节点 -> 右子树 *          后序遍历：左子树 -> 右子树 -> 根节点 */class Node {    constructor(val) {        this.key = val;        this.left = null;        this.right = null;    }}let root = null;let arr = [];
// 前序遍历：根节点 -> 左节点 -> 右节点const preOrder = node => {    if (node === null) return;    arr.push(node.key);    preOrder(node.left);    preOrder(node.right);    return arr;};
// 中序遍历：左节点 -> 根节点 -> 右节点const inOrder = node => {    if (node === null) return;    inOrder(node.left);    arr.push(node.key);    inOrder(node.right);    return arr;};
// 后续遍历：左节点 -> 右节点 -> 根节点const postOrder = node => {    if (node === null) return;    postOrder(node.left);    postOrder(node.right);    arr.push(node.key);    return arr;};

// test:root = new Node(1);root.left = new Node(2);root.right = new Node(3);root.right.right = new Node(6);root.left.left = new Node(4);root.left.right = new Node(5);/** *  Binary Tree:          1       2    3     4    5   6 */
// console.log(preOrder(root)); // [ 1, 2, 4, 5, 3, 6 ]// console.log(inOrder(root)); // [ 4, 2, 5, 1, 3, 6 ]// console.log(postOrder(root)); // [ 4, 5, 2, 6, 3, 1 ]