Posts

否运算 not ~ 按位取反 0000 0011 ---[3] 1111 1100 1111 1101 ---[-3] 按位与 and & 两个位都是1时，结果才为1，否则为0 5 & 3 0101 0011 ---- 0001 ---[1] 按位或 or | 两个位都是0时，结果才为0，否则都为1 5 | 3 0101 0011 ---- 0111 ---[7] 异或（不带进位的加法）xor ^ 两个位相同为0，不同则为1 5 ^ 3 0101 0011 ---- 0110 ---[6] 左移 << 向左进行移位操作，高位丢弃，低位补0 在计算机中相当于 乘以2的n次方，因为在计算机中以二进制存储数据 10 << 2 === 40 0000 1010 << 2 0010 1000 ---[40(10*2^2)] 右移 >> 向右进行移位操作，对无符号数，高位补 0，对于有符号数，高位补符号位 [8] 0000 1000 >> 3 [1] 0000 0001 [-8] 1111 1000 >> 3 [-1] 1111 1111 字符串加法 字符串连接加法，会调用对象的toString方法，原生类型相应的表示，在连接一个很长的字符串加法时，JDK内部会自动转换为StringBuilder的调用，减轻内存压力，提高性能

给你两个二进制字符串，返回它们的和（用二进制表示）。 输入为 非空 字符串且只包含数字 1 和 0。 示例1： 输入: a = “11”, b = “1” 输出: “100” 示例2： 输入: a = “1010”, b = “1011” 输出: “10101” //满二进一 var addBinary = function(a, b) { let sum = 0 //保留上一次位数相加后是否进一 let result = "" for(let i = a.length -1, j = b.length-1; i >= 0 || j >= 0; i--, j--){ let count = sum //取sum的值，与本次遍历的两数相加 count += a[i] > 0 ? parseInt(a[i]) : 0 count += b[j] > 0 ? parseInt(b[j]) : 0 //count的值只可能为 0、1、2、3 result += count % 2 sum = Math.floor(count / 2) // count >= 2 时会进一 } result += sum == 1 ? sum : "" //最后要检查sum是否为1，为1则表示还需要进位 return result.split("").reverse().join("") //反转，因为是从字符串末端开始遍历 };

树 树是一种常用的数据结构，用来模拟具有树状结构性质的数据集合 树的每一个节点有一个根植和一个包含所有子节点的列表。 二叉树 二叉树是一种更为典型的树状结构。二叉树每个节点最多具有两个子树，通常子树称为“左子树”和“右子树” 二叉树前序遍历 前序遍历首先访问根节点，然后遍历左子树，最后遍历右子树（根节点 -> 左子树 -> 右子树） 算法： /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number[]} */ // 递归 const preorderTraversal = function(root) { let result = [] function fn(root){ if(root !== null){ result.push(root.val) if(root.left) fn(root.left) if(root.right) fn(root.right) } } fn(root) return result }; 二叉树中序遍历 先遍历左子树，然后访问根节点，最后遍历右子树（左子树 -> 根节点 -> 右子树） 算法： /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number[]} */ const inorderTraversal = function(root) { let result = [] function fn(root){ if(root !== null){ if(root.left) fn(root.left) result.push(root.val) if(root.right) fn(root.right) } } fn(root) return result }; 二叉树后序遍历 先遍历左子树，然后遍历右子树，最后访问根节点（左子树 -> 右子树 -> 根节点） 算法 /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number[]} */ const postorderTraversal = function(root) { let result = [] function fn(root){ if(root !== null){ if(root.left) fn(root.left) if(root.right) fn(root.right) result.push(root.val) } } fn(root) return result }; 二叉树层序遍历 算法： /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number[][]} */ // 广度优先 前序 const levelOrder = function(root) { let levels = [] if(root === null) return levels function fn(node, level){ let len = levels.length if(len === level) levels.push([]) levels[level].push(node.val) if(node.left) fn(node.left, level+1) if(node.right) fn(node.right, level+1) } fn(root, 0) return levels }; 二叉树最大深度 给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数 算法： /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {number} */ var maxDepth = function(root) { // 写递归的一个重要思路就是相信这个函数能完成任务，此题带有动态规划的感觉 // 最大深度 = 1+Math.max(根节点的左子树最大深度, 根节点的右子树最大深度) // 根节点的左子树最大深度 = 1 + Math.max(左子树的左子树最大深度, 左子树的右子树最大深度) // 根节点的右子树最大深度 = 1 + Math.max(右子树的左子树最大深度, 右子树的右子树最大深度) if(!root){ return 0 }else{ return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1 } }; 对称二叉树 给定一个二叉树，检查它是否是镜像对称的。 算法： /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @return {boolean} */ var isSymmetric = function(root) { return isMirroTree(root, root) }; function isMirroTree(root_1, root_2){ if(root_1 === null && root_2 === null) return true if(root_1 === null || root_2 === null) return false return (root_1.val === root_2.val) && isMirroTree(root_1.left, root_2.right) && isMirroTree(root_1.right, root_2.left) } 路径总和 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。 说明: 叶子节点是指没有子节点的节点。 算法： /** * Definition for a binary tree node. * function TreeNode(val) { * this.val = val; * this.left = this.right = null; * } */ /** * @param {TreeNode} root * @param {number} sum * @return {boolean} */ var hasPathSum = function(root, sum) { return helper(root, sum) }; function helper(node, sum){ if(!node){ return false }else{ sum -= node.val } if(!node.left && !node.right){ return sum === 0 } return helper(node.left, sum) || helper(node.right, sum) }

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。 示例： 输入：head = [1,3,2] 输出：[2,3,1] 限制：0 <= 链表长度 <= 10000 解： 方法一：遍历链表，使用unshift将元素添加到数组头部 /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {number[]} */ var reversePrint = function(head) { if(head === null) return [] let result = [] while(head){ result.unshift(head.val) head = head.next } return result }; 方法二：反转链表，遍历链表将元素push到数组 /** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */ /** * @param {ListNode} head * @return {number[]} */ var reversePrint = function(head) { if(head === null) return [] head = reverseList(head) let result = [] while(head){ result.push(head.val) head = head.next } return result }; function reverseList(head){ let next; let pre; while(head){ next = head.next; head.next = pre; pre = head; head = next; } return pre }

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。 输入：s = "We are happy." 输出："We%20are%20happy." 限制：0 <= s 的长度 <= 10000 解： // 方法一：正则 /** * @param {string} s * @return {string} */ var replaceSpace = function(s) { return s.replace(/ /g, "%20") }; //方法二：遍历字符串 /** * @param {string} s * @return {string} */ var replaceSpace = function(s) { if (!s || !s.length) { return ""; } let result = "" for(let i = 0; i<s.length; i++){ if(s[i] === " "){ result += "%20" }else{ result += s[i] } } return result };