乐趣区

关于javascript:手写题目之算法篇

jiezi
  • 二叉树广度遍历
  • 二叉树层序遍历
  • 二叉树深度遍历：前序，中序，后序
  • 二叉树的最大深度
  • 二分查找
  • 给定 path，遍历树查找有无指定 path 的节点
  • 疾速排序
  • 第 K 大
  • 最长公共前缀
  • 无反复字符的最长子串

树遍历很多先定义一个树型构造。

// 树形构造定义
const tree = {
      data: 1,
      left: {
        data: 2,
        left: {
          data: 4,
          left: {data: 8,},
          right: {data: 9}
        },
        right: {
          data: 5,
          left: {data: 10,},
          right: {data: 11}
        }
      },
      right: {
        data: 3,
        left: {
          data: 6,
          left: {data: 12}
        },
        right: {data: 7}
      }
    };

二叉树广度遍历

广度遍历就是遍历每一层，下面的 tree 广度遍历之后的后果是[1,2,3,4,5,6,7,8,9,10,11,12]。实现形式是通过栈保留遍历状态，按父节点，左子树，右子树的程序压栈。取出栈顶保留到后果数组中，等栈为空时遍历完结。

代码如下：

// 广度遍历
function bfs(tree){
    // 通过栈保留遍历状态
    let stack = [tree];
    let result = [];
    
    while(stack.length){
        // 取出栈顶
        const node = stack.shift();
        
        result.push(node.data);
        // 有左子树压到栈中
        if(node.left){stack.push(node.left);
        }
        // 右右子树压到栈中
        if(node.right){stack.push(node.right);
        }
    }

    return result;

}

console.log('广度遍历', bfs(tree));

二叉树层序遍历

层序遍历是每个档次保留到一个数组项。

    // 层序遍历
        function levelOrder(tree){const output = [];

            let level = 0;

            if(level === null){return output;}

            const visitLoop = (node, level) => {if(!output[level]){output[level] = [];}

                output[level].push(node.data);

                if(node.left){visitLoop(node.left, level + 1);
                }

                if(node.right){visitLoop(node.right, level + 1);
                }
            };

            visitLoop(tree, 0);

            return output;

        }

        console.log('层序遍历', levelOrder(tree));

二叉树前序遍历

前序遍历的程序是先拜访根，再拜访左子树，再拜访右子树。前序遍历的后果是 [1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 12, 7]。
利用栈的个性保留以后遍历状态。初始化根节点先压栈。每次循环中取出栈顶保留到后果数组中，如果有右子树压栈，有左子树压栈。

// 前序遍历
function preOrder(tree){let stack = [tree];
    let result = [];
    let node;

    while(stack.length){let node = stack.pop();

        result.push(node.data);

        if(node.right){stack.push(node.right);
        }

        if(node.left){stack.push(node.left);
        }

    }

    return result;
}

console.log('前序遍历', preOrder(tree));

前序遍历的递归实现

// 前序遍历递归实现
function preOrderRcs(tree){let result = [];
    const visitLoop = function(node){result.push(node.data);

        if(node.left){result.concat(visitLoop(node.left));
        }

        if(node.right){result.concat(visitLoop(node.right));
        }
    };

    visitLoop(tree);

    return result;
}

console.log('前序遍历 - 递归实现', preOrderRcs(tree));

二叉树中序遍历

中序遍历是先拜访左子树，在拜访根，最初拜访右子树。中序遍历后果为 [8, 4, 9, 2, 10, 5, 11, 1, 12, 6, 3, 7]。
中序遍历非递归实现用到了回溯算法。

回溯法（back tracking）（摸索与回溯法）是一种选优搜寻法，又称为试探法，按选优条件向前搜寻，以达到目标。但当摸索到某一步时，发现原先抉择并不优或达不到指标，就退回一步从新抉择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

非递归遍历还是利用栈保留遍历程序，加一个变量存储以后遍历节点。
遍历条件：栈不为空或者以后节点不为空
有以后节点存入栈中，顺次让左子树入栈，不存在左子树时，从栈顶弹出元素存入后果数组，如果弹出元素有右子树，右子树为以后遍历节点，压栈。

// 中序遍历 须要用到回溯算法
        function inOrder(tree){const stack = [];
            const result = [];

            // 以后遍历节点存储
            let node = tree;
            
            while(stack.length || node){
                // 有节点就压栈，并往下找左子树
                if(node){stack.push(node);

                    node = node.left;
                }else{
                    // 没有左子树了，从栈顶弹出
                    const current = stack.pop();
                    // 存到后果数组中
                    result.push(current.data);
                    
                    // 有右子树，以后遍历节点为右子树
                    if(current.right){node = current.right;}
                }
            }

            return result;

        }


        console.log('中序遍历', inOrder(tree));
// 递归实现
function inOrderRcs(tree){let result = [];
    
    const visitLoop = function(node){if(node.left){result.concat(visitLoop(node.left));
        }

        result.push(node.data);

        if(node.right){result.concat(visitLoop(node.right));
        }
    };

    visitLoop(tree);

    return result;
}

console.log('中序遍历 - 递归实现', inOrderRcs(tree));

二叉树后序遍历

先遍历左子树，再遍历右子树，最初拜访根。后序遍历后果为 [8, 9, 4, 10, 11, 5, 2, 12, 6, 7, 3, 1]。

除了保留遍历程序的栈和存储以后遍历节点之外，每个节点加上 touched 属性。以后节点有左子树时顺次遍历压栈，以后节点 touched 设为 left。以后节点有右子树时顺次遍历压栈，以后 touched 设为 false。如果遍历到叶子节点或者左右子树都已遍历过，存到后果数组。并把以后遍历节点设为栈顶元素。

// 后序遍历
function postOrder(tree){const stack = [tree];
    const result = [];
    let node = tree;

    while(stack.length){
        // 顺次把左子树压栈，以后节点标记为拜访过左子树
        if(node.left && !node.touched){
            node.touched = 'left';
            node = node.left;
            stack.push(node);
            continue;

        }

        // 顺次把右子树压栈，以后节点标记为拜访过右子树
        if(node.right && node.touched !== 'right'){
            node.touched = 'right';
            node = node.right;
            stack.push(node);

            continue;
        }


        // 如果是叶子结点或者左右子节点被拜访过
        const current = stack.pop();
        result.push(current.data);
        
        // 设置栈顶为下一个拜访的元素
        node = stack[stack.length - 1];
    }

    return result;
}

console.log('后序遍历', postOrder(tree))

// 后续遍历 - 递归
function postOrderRcs(tree){let result = [];
    const visitLoop = function(node){if(node.left){result.concat(visitLoop(node.left));
        }

        if(node.right){result.concat(visitLoop(node.right));
        }

        result.push(node.data);
    };

    visitLoop(tree);

    return result;
}

console.log('后序遍历 - 递归实现', postOrderRcs(tree))

二叉树的最大深度

// 二叉树的最大深度
function maxDepth(tree){if(tree === null){return 0;}

    let res = 0;

    const visitLoop = (node, level) => {if(!node){return 0;}

        if(!node.left && !node.right){res = Math.max(res, level);
        }


        if(node.left){visitLoop(node.left, level + 1);
        }

        if(node.right){visitLoop(node.right, level + 1);
        }
    };

    visitLoop(tree, 1);

    return res;
}

console.log('二叉树的最大深度', maxDepth(depthTree));

二分查找

function binarySearch(nums, target){if(!nums.length){return -1;}

    let start = 0
        let end = nums.length - 1;

        let mid;

        while(start <= end){let mid = Math.floor((start + end) /2);

            if(target === nums[mid]){return mid;}
            if(target < nums[mid]){end = mid - 1;}

            if(target > nums[mid]){start = mid + 1;}

        }

        return -1;
}

console.log('二分查找', binarySearch([-1,0,3,5,9,12], 9));

疾速排序

分两个过程：

  1. 划分：依据 partition 函数把数组从基准位划分为 2 局部，基准位之前的比它小，之后的比它大。排序时采纳左右两个指针，遍历之后如果碰到右边比基准值大左边的小的值时替换两个值，并返回右边的指针。
  2. 递归：有个主函数 quickSortHandler，通过执行 partition 取到左指针坐标，依据该坐标拆分数组进行递归。终止条件是数组长度。
// 疾速排序
function quickSort(nums = []){const swap = (nums, i ,j) => {const temp = nums[j];
        nums[j] = nums[i];
        nums[i] = temp;
    };


    // 划分过程
    const partition = (nums, i, j) => {
        let left = i;
        let right = j;

        let mid = Math.floor((right + left)/2);

        // 左指针比右指针大时
        while(left <= right){while(nums[left] < nums[mid]){left++;}

            while(nums[right] > nums[mid]){right --;}

            if(left <= right){swap(nums, left, right);
                left++;
                right --;

            }
        }
        return left;
    };

    // 拆分数组递归调用排序
    const quickSortHandler = (nums, left, right) => {

        let index;

        // 终止条件
        if(nums.length > 1){index = partition(nums, left, right);

            if(left < index - 1){quickSortHandler(nums, left, index - 1);
            }

            if(index < right){quickSortHandler(nums, index, right);
            }
        }

        return nums;

    };

    quickSortHandler(nums, 0, nums.length - 1);

    return nums;
}

console.log('疾速排序', quickSort([5,1,1,2,0,0]));

第 K 大

疾速排序之后找出数组中 arr.length – k 的元素即可。

最长公共前缀

// 最长公共前缀
function longestCommonPrefix(strs = []){if(!strs.length){return '';}

    let res = strs[0];

    for(let i = 1; i < strs.length; i++){
        let j = 0;

        for(;j < strs[i].length; j++){if(strs[i][j] !== res[j]){break;}
        }

        res = res.substring(0, j);

        if(!res){return '';}
    }

    return res;    
}

console.log('最长公共前缀', longestCommonPrefix(["flower","flow","flight"]));

无反复字符的最长子串

// 无反复字符的最长子串
function lengthOfLongestSubstring(s){
    let max = 0;
    const arr = [];

    if(!s){return '';}

    for(let i = 0; i< s.length; i++){if(arr.find(item => item ===s[i])){let index = arr.findIndex(item => item === s[i]);
            arr.splice(0, index + 1);
        }

        arr.push(s[i]);

        max = Math.max(arr.length, max);
    }

    return max;

}
console.log('无反复字符的最长子串', lengthOfLongestSubstring('abcabcbb'));

参考文章：
二叉树遍历
学习 javascript 数据结构与算法

退出移动版