Algorithm

二叉查找树 二叉查找树(binary search tree)：当前根节点的左边全部比根节点小，当前根节点的右边全部比根节点大。 class TreeNode { constructor(data) { this.data = data; this.left = null; this.right = null; } } class BinarySearchTree { constructor() { this.root = null; } insert(data) { var newNode = new TreeNode(data); if (this.root === null) { …

树的概念 节点分类： 根节点 子节点 叶子节点 兄弟节点 其他： 树的深度：从根节点到最底层节点的层数。 树的深度：树中节点的最大层次称为树的深度（或树的高度）。 节点的度：节点拥有的子树数称为节点的度。 叶子节点：度为0的节点称为叶节点（或终端节点）。 分支节点：度不为0的节点称为分支节点（或非终端节点）。 树的度：树内各节点的度的最大值。 节点层次：从根开始，根为第一层，根的孩子为第二层。 二叉树 二叉树：每个节点最多有两个子节点。 10 / \ 9 20 / \ 15 35 二叉树的操作： 1、创建二叉树； 2、遍历二叉树； 先序遍历：先访问根节点，然后访问左节点，最后访问右节点（ …

树结构多种多样，我们最常用的还是二叉树。 特殊二叉树 1、满二叉树； 2、完全二叉树； 二叉树的存储 1、基于指针或者引用的二叉链式存储法； 2、基于数组的顺序存储法； 我们把根节点存储在下标 i = 1 的位置，那左子节点存储在下标 2 * i = 2 的位置，右子节点存储在 2 * i + 1 = 3 的位置。 如果节点x存储在数组中下标为 i 的位置，下标为 2 * i 的位置存储的就是左子节点，下标为 2 * i + 1 的位置存储的就是右子节点。反过来，下标为 i / 2 的位置存储的就是它的父节点。 通过这种方式，我们只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点 …

查找第一个等于给定值的元素（有重复元素） const binarySearch = (arr, value) => { let low = 0, high = arr.length - 1; while (low <= high) { const mid = parseInt(low + (high - low) / 2); if (arr[mid] === value) { if (mid === 0 || arr[mid - 1] != value) { return mid; } else { high = mid - 1; } } else if (arr[mid] …

循环实现（无重复元素） const binarySearch = (arr, value) => { let low = 0, high = arr.length - 1; while (low <= high) { const mid = parseInt((low + high) / 2, 10); if (arr[mid] === value) { return mid; } else if (arr[mid] < value) { low = mid + 1; } else { high = mid - 1; } } return -1; }; 递归实现（无重复元素） …

题目 对于给定的n，打印出如下型式的蛇形矩阵。例如 n=3时，输出： 1 2 3 8 9 4 7 6 5 n=4时，输出： 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7 参考 var snake = (n) => { let row = n, col = row; var q = Math.ceil(n / 2); // 旋转几圈 // 创建存放的数组 var result = new Array(row); for (var i = 0; i < row; i++) { result[i] = new Array(col); } var n = …

数据结构 // 节点类 class Node { constructor(value) { this.value = value; // 存储值 this.next = null; // 存储下一个节点的引用 } } //链表类 class LinkedList { constructor() { this.length = 0; //链表的长度 this.head = null; //链表的头结点 } //链表的插入方法 append(value) { var node = new Node(value); //创建节点 if (!this.head) { this.head = node; …

将两个有序数组合并成一个有序数组。 实现1 //O(n) time & O(n) space var mergeArr1 = (arr1, arr2) => { var result = [], index1 = 0, index2 = 0, current = 0; while (current < arr1.length + arr2.length) { //debugger; var element1 = arr1[index1]; var element2 = arr2[index2]; if (element1 < element2) { …

两个数组的交集 集合论中，设A，B是两个集合，由所有属于集合A且属于集合B的元素所组成的集合，叫做集合A与集合B的交集。 集合 {1,2,3} 和 {2,3,4} 的交集为 {2,3}。 //filter实现 let intersect = (a,b) => a.filter(x => b.indexOf(x) > -1); //Set实现 let intersect1 = (a, b) => { return a.filter(x => new Set(b).has(x)); } let intersect2 = (a, b) => { let …

如何判断左右小括号是否全部匹配。如 (( ))()((((()))))？ var isValid = function (str) { var stack = []; var map = { "(": ")", "[": "]", "{": "}", }; for (var char of str) { if (char in map) { stack.push(char); } else { if (!stack.length || char != map[stack.pop()]) { …