Jungle

剑指 Offer 53 - I. 在排序数组中查找数字 I 题目描述：统计一个数字在排序数组中出现的次数。 示例： 输入: nums = [5,7,7,8,8,10], target = 8输出: 2 输入: nums = [5,7,7,8,8,10], target = 6输出: 0 思路：遍历数组即可！ 代码：1234567891011121314var search = function(nums, target) { // let count = 0; // nums.forEach((a)=>{ // if(a === target) count++; // if(a > target) return count // }) // return count let count = 0; for(let i=0;i<nums.length;i++){ if(nums[i] === target) count++ } ...

剑指 Offer 40. 最小的k个数 题目描述：输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 示例： 输入：arr = [3,2,1], k = 2输出：[1,2] 或者 [2,1] 输入：arr = [0,1,2,1], k = 1输出：[0] 思路：先判断k是否超过数组的长度然后进行排序（升序或者降序都可以，最后再进行slice() 代码：12345678var getLeastNumbers = function(arr, k) { if(k>arr.length) return []; arr.sort((a,b)=>a-b); return arr.slice(0,k); // return arr.sort((a, b) => a - b).slice(0, k);};

剑指 Offer 65. 不用加减乘除做加法 题目描述：写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。 示例： 输入: a = 1, b = 1输出: 2 思路：不考虑进位直接相加可以看出，1+0=1，1+1=0，0+0=0，这是异或操作（^），对加 0 、0 加 1 、1 加 0 而言， 都不会产生进位，只有 1 加 1 时，会向前产生一个进位。此时我们可以想象成是两个数先做位与运算，然后再向左移动一位 代码：12345678var add = function(a, b) { //采用位运算 //无进位：异或运算 //有进位：与运算+左移运算 if(a === 0) return b; if(b === 0) return a; return add((a^b),((a&b)<<1))};

剑指 Offer 28. 对称的二叉树 题目描述：请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。 示例： 二叉树 [1,2,2,3,4,4,3] 是对称的。 这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 思路：采用递归方法，先判断根节点的左子树和右子树是否为空，同时为空，则返回true，一个为空，则为false。同时不为空，则判断其值是否相等，然后递归判断左子树和右子树的 代码：123456789var isSymmetric = function(root) { return isSymmetricFunction(root,root); function isSymmetricFunction(left,right){ if(left==null && right==null) return true; if(left==null || right==null) return false; if(left.val ! ...

剑指 Offer 55 - II. 平衡二叉树 题目描述：输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。 示例：示例 1: 给定二叉树 [3,9,20,null,null,15,7]返回 true 示例 2: 给定二叉树 [1,2,2,3,3,null,null,4,4]返回 false 思路：思路：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。遍历左子树和右子树的深度，然后比较二者差值 代码：12345678910111213var isBalanced = function(root) { if(!root) return true let left = dfs(root.left) let right = dfs(root.right) if(Math.abs(right - left) > 1) return false //判断当前子树的 左子树 和 右子树 是否是平衡树； return isBalanced( ...

剑指 Offer 18. 删除链表的节点 题目描述：给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。 返回删除后的链表的头节点。 示例： 输入: head = [4,5,1,9], val = 5输出: [4,1,9]解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9. 输入: head = [4,5,1,9], val = 1输出: [4,5,9]解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9. 思路：改变val值的head.next指向 代码：12345678910111213141516var deleteNode = function(head, val) { if(head.val == val){ return head.next } /** * 假设【1，2，3】，目标值是2 * 当前head是1. * 本来head.nex ...

剑指 Offer 42. 连续子数组的最大和 题目描述：输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。 要求时间复杂度为O(n)。 示例： 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。 思路：如果和为负数，则重新开始，如果和为正数，则继续加，然后比较大小，选出最大和即可。 代码：123456789et maxSubArray = function(nums) { if(nums.length==0) return; let tempSum=0,sum=-Number.MAX_VALUE; nums.map(function(a){ tempSum=(tempSum<0)?a:tempSum+a; sum=(sum<tempSum)?tempSum:sum; }) return sum;};

剑指 Offer 50. 第一个只出现一次的字符 题目描述：找出字符串中第一个只出现一次的字符 示例： s = “abaccdeff”返回 “b” s = “”返回 “ “ 思路：只需要判断第一次出现的位置和最后出现的位置是否相等 拓展JavaScript lastIndexOf() 方法：lastIndexOf() 方法可返回一个指定的字符串值最后出现的位置，在一个字符串中的指定位置从后向前搜索。 代码：123456var firstUniqChar = function(s) { for(let x of s){ if(s.indexOf(x) === s.lastIndexOf(x)) return x } return ' '};

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 题目描述：入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。 示例： 输入：nums = [1,2,3,4]输出：[1,3,2,4]注：[3,1,2,4] 也是正确的答案之一。 思路：①先定义一个新数组result，然后遍历原来的nums数组，若为奇数则unshift()到新数组result中，反之则pop()到新数组中 unshift()将一个数添加到数组的头部;pop()将一个数添加到数组的尾部！ ②通过map函数，判断每个数组元素是否为偶数 代码：123456789var exchange = function(nums) { var result = []; for(let i=0;i<nums.length;i++){ if(nums[i]%2 == 0){ result.push(nums[i]) } } return ...

剑指 Offer 62. 圆圈中最后剩下的数字 题目描述：0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。 示例： 输入: n = 5, m = 3输出: 3 输入: n = 10, m = 17输出: 2 思路：思路①：创立数组，每当到m-1位置时，删除数组中元素，然后将位置计0重新开始 思路②： n个人编号0,1,2,…,n-1，每数m次删掉一个人 假设有函数f(n)表示n个人最终剩下人的编号 n个人删掉1个人后可以看做n-1的状态，不过有自己的编号。 n个人删掉的第一个人的编号是(m-1)%n，那么n个人时删掉第一个人的后面那个人(m-1+1)%n一定是n-1个人时候编号为0的那个人，即n个人时的编号m%n（这个编号是对于n个人来考虑的），n-1个人时编号为i的人就是n个人时(m+i)%n 所以f(n)=(m+f(n-1))%n f(1)=0，因为1个人时只 ...