手撕代码系列(三)

/**
 * 匹配括号 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 ]