Jungle

剑指 Offer 56 - II. 数组中数字出现的次数 II 题目描述：在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。 示例： 输入：nums = [3,4,3,3]输出：4 输入：nums = [9,1,7,9,7,9,7]输出：1 思路：使用对象或者Map（本处用对象）记录每一个数字出现次数,遍历对象或者Map，然后再找出出现次数为1的数字 代码：123456789var singleNumber = function(nums) { let obj = {}; for(let i = 0;i<nums.length;i++){ obj[nums[i]]?obj[nums[i]]++:obj[nums[i]]=1 } for(let k in obj){ if(obj[k] == 1) return k }};

剑指 Offer 64. 求1+2+…+n 题目描述：求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。 示例： 输入: n = 3输出: 6 输入: n = 9输出: 45 思路：因为不能用for、if等来判断边界，所以可以通过右移运算， 代码：1234567var sumNums = function(n) {// return n && sumNums(n-1) + n;//右移几位就相当于除以2的几次方（如100>>4 等效 100/2^4）//负数的右移不等于除法 return (n ** 2 + n) >> 1 ;};

剑指 Offer 10- I. 斐波那契数列 题目描述：写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下： F(0) = 0, F(1) = 1F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 示例： 输入：n = 2输出：1 输入：n = 5输出：5 思路：f(n)=f(n-1)+f(n-2) 1234567//f(n)=f(n-1)+f(n-2)var fib = function(n) { if(n === 0 || n === 1) { return n } return fib(n-1) + fib(n-2) }; 代码：结果要记得取模！！ 1234567891011var fib = function(n) { let result = [] for(let i=0; i<= n; i++) { if(i=== 0 || i=== 1) { ...

剑指 Offer 10- II. 青蛙跳台阶问题 题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。 示例： 输入：n = 2输出：2 输入：n = 7输出：21 输入：n = 0输出：1 思路：斐波那契数列：跳1个台阶有一种方法，跳2个台阶可以有两种跳法，而跳3个台阶则就是跳一个台阶和跳2个台阶方法总和， 代码：12345678910111213var numWays = function(n) { if(n <= 1) return 1; if(n == 2) return 2; let n1 = 1; let n2 = 2; let sum = 0; for(let i=3;i<=n;i++){ sum = (n1 + n2) % 1000000007; n1 = n2; n2 = sum
...

剑指 Offer 58 - I. 翻转单词顺序 题目描述：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。 示例： 输入: “the sky is blue”输出: “blue is sky the” 输入: “ hello world! “输出: “world! hello”解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。 输入: “a good example”输出: “example good a”解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。 思路：先用trim()把字符串两端空格去掉，split(‘ ‘)把字符串切割成以空格为界限的单词块，filter()过滤掉数组中的纯空格，reverse()进行数组反转，join(‘ ‘)把数组变成中间只带一个空格的字符串 代码：123var reverseWords = function(s){ re ...

剑指 Offer 59 - I. 滑动窗口的最大值 题目描述：给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。 示例： 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3输出: [3,3,5,5,6,7]解释:滑动窗口的位置 最大值 [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 思路：算出滑动窗口个数=(数组元素个数-滑动窗口大小)+1，然后遍历循环，将队列头元素取出，存入新元素。 代码：1234567891011121314var maxSlidingWindow = function(nums, k) { if(k==0) return ...

剑指 Offer 29. 顺时针打印矩阵 题目描述：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。 示例： 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]输出：[1,2,3,6,9,8,7,4,5] 输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]输出：[1,2,3,4,8,12,11,10,9,5,6,7] 思路：剥洋葱，一层一层从矩阵中剥掉 代码：12345678910111213141516171819202122232425var spiralOrder = function(matrix) { var res = [] let flag = true while(matrix.length) { // 从左到右 if(flag){ // 第一层 res = res.concat(matrix.shift()) // '现在' ...

剑指 Offer 53 - II. 0～n-1中缺失的数字 题目描述：一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。 示例： 输入: [0,1,3]输出: 2 输入: [0,1,2,3,4,5,6,7,9]输出: 8 思路：对比索引和对应的值是否相等即可 代码：123456789var missingNumber = function(nums) { ////防止缺失的是最后一个 nums.push('x'); for(let i=0;i<nums.length;i++){ if(nums[i] != i){ return i } }};

剑指 Offer 61. 扑克牌中的顺子 题目描述：从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。 示例： 输入: [1,2,3,4,5]输出: True 输入: [0,0,1,2,5]输出: True 思路：要直接获取数组最大数与最小数,就必须将数组进行排序以上条件都需要除去0,故使用了数组的 filter方法 将数组中的 0 过滤掉获取到 最大数 与 最小数 之后，判断它们的差是否大于 4,大于 4 则不符题意,返回 false遍历一次新数组判断是否有重复的数字,有重复则不符题意,返回 false以上都判断都通过,说明符合题意，返回 true 代码：123456789101112var isStraight = function (nums) { // 先将 nums 从小到大进行排序，再把数组中的 0 去掉 nums = nums.sort((a, b) => a - b).filter(item => item ...

剑指 Offer 11. 旋转数组的最小数字 题目描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。 示例： 输入：[3,4,5,1,2]输出：1 输入：[2,2,2,0,1]输出：0 思路：先进行升序排列，然后输入第一个值即可 代码：1234var minArray = function(numbers) { numbers.sort((a,b)=>a-b); return numbers[0];};