给你两个二进制字符串，返回它们的和（用二进制表示）。 输入为 非空 字符串且只包含数字 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 };

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 示例： 现有矩阵 matrix 如下： [ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] 给定 target = 5，返回 true。 给定 target = 20，返回 false。 限制： 0 <= n <= 1000 0 <= m <= 1000 解： 由于每行每列的元素大小都是递增的，所以在遍历时可以判断当前元素是否大于 tatget，如果大于，则开始下一轮遍历。 /** * @param {number[][]} matrix * @param {number} target * @return {boolean} */ var findNumberIn2DArray = function(matrix, target) { let result = false for(let i = 0; i < matrix.length; i++){ for(let j = 0; j < matrix[i].length; j++){ if(matrix[i][j] > target){ break } if(matrix[i][j] === target){ result = true return result } } } return result };