Jungle

剑指 Offer 57. 和为s的两个数字 题目描述：输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。 示例： 输入：nums = [2,7,11,15], target = 9输出：[2,7] 或者 [7,2] 输入：nums = [10,26,30,31,47,60], target = 40输出：[10,30] 或者 [30,10] 思路： 初始化： 双指针 i , j 分别指向数组 nums 的左右两端 （俗称对撞双指针）。 循环搜索： 当双指针相遇时跳出； 计算和 s = nums[i] + nums[j]；若 s > targets ，则指针 jj 向左移动，即执行 j = j - 1 ；若 s < targets ，则指针 ii 向右移动，即执行 i = i + 1 ；若 s = targets，立即返回数组 [nums[i], nums[j]] ； 返回空数组，代表无和为 target 的数字组合。 代码：12345678910var twoSum = function ...

剑指 Offer 39. 数组中出现次数超过一半的数字 题目描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例： 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]输出: 2 思路：新建一个空对象来保存数组中数字出现的次数；遍历数组，如果该数字出现过，则obj中以该数字为key的value加1；若该数字未出现过，则obj中以该数字为key的value设为1；遍历obj对象，返回value大于数组长度一半的key，即为所求数字。 代码：1234567891011121314151617var majorityElement = function(nums) { let obj = {}; let len = nums.length; nums.forEach(function(s){ if(obj[s]){ obj[s]++; }else{ ...

剑指 Offer 03. 数组中重复的数字 题目描述：找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 示例： 输入：[2, 3, 1, 0, 2, 5, 3] 输出：2 或 3 思路：使用JavaScript 标准内置对象Set,因为Set自动忽略重复元素，遍历数组中元素，若长度未增加，则输出当前元素 代码：12345678var findRepeatNumber = function(nums) { let s = new Set(); for(let i in nums){ let curLenth = s.size; s.add(nums[i]); if(s.size == curLenth) return nums[i] }};

剑指 Offer 32 - II. 从上到下打印二叉树 II 题目描述：从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。 示例： 给定二叉树: [3,9,20,null,null,15,7], 返回结果为： 思路：从题目中可以看到，本题考察的是二叉树的层序遍历，并且在结果中要体现出“层次”。稍微改变一下对队列的使用，就可以在遍历过程中体现出层次，大致过程如下： 初始化 queue，用于存储当前层的节点 检查 queue 是否为空 2.1:如果不为空：依次遍历当前 queue 内的所有节点，检查每个节点的左右子节点，将不为空的子节点放入 queue，继续循环 2.2:如果为空：跳出循环 代码：123456789101112131415161718192021222324252627282930313233var levelOrder = function(root) { if (!root) return []; // 1. 设置结果集 const result = []; // 2. 设置当前层 let nowRoot ...

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 题目描述：给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 示例： 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8输出: 6解释: 节点 2 和节点 8 的最近公共祖先是 6。 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4输出: 2解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身 思路：这道题和二叉树的最近公共祖先的唯一差别就是本题的树是二叉搜索树（BST），也就暗示我们需要使用BST的特性。由于lowestCommonAncestor(root, p, q)的功能是找出以root为根节点的两个节点p和q的最近公共祖先。 我们考虑： 如果p和q分别在 ...

剑指 Offer 68 - II. 二叉树的最近公共祖先 题目描述：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” 示例： 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1输出: 3解释: 节点 5 和节点 1 的最近公共祖先是节点 3。 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4输出: 5解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。 思路：由于lowestCommonAncestor(root, p, q)的功能是找出以root为根节点的两个节点p和q的最近公共祖先。我们考虑：如果p和q分别是root的左右节点，那么root就是我们要找的最近公共祖先如果root是None，说明我们在这条寻址线路没有找 ...

剑指 Offer 57 - II. 和为s的连续正数序列 题目描述：输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。 示例： 输入：target = 9输出：[[2,3,4],[4,5]] 输入：target = 15输出：[[1,2,3,4,5],[4,5,6],[7,8]] 思路：设定两个指针，如果和大于sum，左指针向后移位，如果小于，右指针向后移位。如果两个指针碰在一起，则跳出，//左指针一直小于sum的一半， 代码：123456789101112131415161718192021222324252627var findContinuousSequence = function(sum) {if(sum<2) return[]; var result=[]; var a=1,b=2,s=3; while(a<=Math.floor(sum/2)){ if(s<sum){ ...

剑指 Offer 09. 用两个栈实现队列 题目描述：用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 ) 题目解释：输入： [“CQueue”,”appendTail”,”deleteHead”,”deleteHead”]这一行表示每一行代码的操作 [[],[3],[],[]]这个表示每一行代码操作所需要的参数 举例：CQueue 表示新建一个CQueue对象，对应的所需参数为[]，即此操作不需要参数。appendTail 表示执行一个appendTail()操作，对应要被操作的元素为3。deleteHead 表示执行一个deleteHead操作，对应的所需参数为[]，即此操作不需要参数。deleteHead 表示执行一个deleteHead操作，对应的所需参数为[]，即此操作不需要参数。 以上的输入其实是一个代码执行的步骤描述与其对应所需参数。 即两个纬度：1、操作描述2、此次操作所需参数3、操作描述与操作所需参数 ...

剑指 Offer 25. 合并两个排序的链表 题目描述：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。 示例： 输入：1->2->4, 1->3->4输出：1->1->2->3->4->4 思路：两个指针分别指向链表元素，然后比较两个元素大小，小的则连到合成后链表，直到达到一个链表的末尾。然后如果哪一个链表还有元素，直接连到合成后链表后面即可。 代码：123456789101112131415161718192021var mergeTwoLists = function(l1, l2) { var head = new ListNode(0); var pHead = head; while(l1 != null && l2 != null){ if(l1.val >= l2.val){ head.next=l2; l2=l2.next; }else& ...

剑指 Offer 15. 二进制中1的个数 题目描述：请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。 示例： 输入：00000000000000000000000000001011输出：3解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 ‘1’。 思路：把一个整数减去1，再和原来的整数做与运算，会把该整数最右边的一个1变为0。那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。 代码：12345678var hammingWeight = function(n) { var count=0; while(n!=0){ n=n&(n-1); count++ } return count };