前言
算法这个活动很严，每天必须打卡，而且不限制语言，群内已有PHP、Python、Java、Javascript等语言，欢迎大家参加，并坚持。能坚持的公众号回复算法。本公众号以JS为主，解题思路均以js来举例。
上周回顾：
1、两个数组的交集 II
2、1比特与2比特字符
3、二进制求和
4、两数之和
5、加一
爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数
- 示例 1：
输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶 - 示例 2：
输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶 1. 1 阶 + 1 阶 + 1 阶 2. 1 阶 + 2 阶 3. 2 阶 + 1 阶
题解：
-
斐波那契数列公式法
dp[n] = dp[n-1] + dp[n-2]
执行用时：64ms；内存消耗：34.2MB；
var climbStairs = function(n) { const dp = []; dp[0] = 1; dp[1] = 1; for(let i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; }; -
数学公式法
image
执行用时：72ms；内存消耗：33.7MB；var climbStairs = function(n) { const sqrt_5 = Math.sqrt(5); const fib_n = Math.pow((1 + sqrt_5) / 2, n + 1) -Math.pow((1 - sqrt_5) / 2,n + 1); return Math.round(fib_n / sqrt_5); };
只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？
- 示例 1:
输入: [2,2,1] 输出: 1 - 示例 2:
输入: [4,1,2,1,2] 输出: 4
题解
-
对象计数法
用一个对象来存储出现的次数，然后取出次数为1的值；
执行用时：116ms；内存消耗：37.5MB；var singleNumber = function(nums) { let obj={}; let result=null; nums.forEach(item=>{ if(!obj[item]){ obj[item]=1 }else{ obj[item]++ } }) Object.keys(obj).forEach(item=>{ if(obj[item]===1){ result=item-0 } }) return result }; -
有序互斥法
先排序，然后利用相邻不想等来找出答案；
执行用时：156ms；内存消耗：36.9MB；var singleNumber = function(nums) { nums = nums.sort(); for (let i = 0; i < nums.length; i++) { if (nums[i] !== nums[i - 1] && nums[i] !== nums[i + 1]) return nums[i]; } }; -
XOR法（异或法）
第一次看到这种解法，也从侧面体现了对js位运算的不熟悉，XOR位运算，如果你了解它的含义，就不怀疑为什么可以解决此题了，XOR位运算会先转化为二进制，如果两位只有一位为 1 则设置每位为 1，最后转化回来；
执行用时：72ms；内存消耗：35.8MB；var singleNumber = function(nums) { let gg = function(total,num){ return total ^ num; } return nums.reduce(gg); } -
左右索引法
从左边检索和右边检索，如果相等，就找到结果；
执行用时：536ms；内存消耗：35.2MB；var singleNumber = function(nums) { for (let i = 0; i < nums.length; i++) { if (nums.lastIndexOf(nums[i]) === nums.indexOf(nums[i])) return nums[i]; } } -
循环减法
从拷贝一个数组，定义一个变量，在循环中，动态修改数组，如果拷贝数组中存在当前值，就相减，否则相加；（这是最笨的方法）
执行用时：1228ms；内存消耗：37.6MB；var singleNumber = function(nums) { let num=0; let list=[...nums] nums.forEach((item,i)=>{ list.splice(i,1,null); if(list.includes(item)){ num-=item }else{ num+=item } }) return num } -
字符串分割法（正则思想）
将数组转换成字符串，然后遍历使用每一项的值去分割字符串，若分割后数组长度为2则该项只出现一次。
执行用时：9460ms；内存消耗：41.9MB；var singleNumber = function(nums) { const numsStr = `/${nums.join('//')}/`; for (let i = 0; i < nums.length; i++) { if (numsStr.split(`/${nums[i]}/`).length === 2) return nums[i]; } }
报数
报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：
1. 1
2. 11
3. 21
4. 1211
5. 111221
1 被读作 "one 1" ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2", "one 1"（"一个二" , "一个一") , 即 1211。
给定一个正整数n（1 ≤ n ≤ 30），输出报数序列的第 n 项。
注意：整数顺序将表示为一个字符串。
- 示例 1:
输入: 1 输出: "1" - 示例 2:
输入: 4 输出: "1211"
题解：
-
对象法
用一个对象来存储报数字符串，分两种情况处理，当key为1和当key>1；当key>1的时候，获取到key-1的字符串，转化为数组，在利用对象来存储此数组中数字出现的次数，但此时会遇到一个问题，像111221这样前面的1和后面的1不同，所以我们存储时要区分开；这里用num做了区分，当值不相同的时候num再赋值。
ob中存的是每个字符串解读的对象，比如4的报数“1211”，5的报数是解读1211的字符串，所以ob中存的是
obj的每一个key值就是n，value就是报数字符串；{ 0:{count:1,value:1}, 1:{count:1,value:2}, 2:{count:2,value:1} }//拼接之后就是111221
执行用时：136ms；内存消耗：36.9MB；var countAndSay = function(n) { let obj={} for(let i=1;i<=n;i++){ obj[i]=''; if(i==1){ obj[i]+=1+'' } if(i>1){ let num=null; let ob={}; let list=obj[i-1].split(''); let flag=false; list.forEach((item,index)=>{ if(index==0){ num=0; ob[index]={ value:item, count:1 } } if(index>0){ if(ob[num]&&ob[num].value===item){ ob[num].count&&ob[num].count++ }else{ num=index ob[index]={ value:item, count:1 } } } }) for(let k in ob){ obj[i]+=ob[k].count+''+ob[k].value } } } return obj[n] } -
正则法
先观察规律，显然每一阶数中任意部分的元素一次最多连续不会超过3次，所以任一阶数的组成元素最多只有1、2、3。所以我直接使用正则/(1+)|(2+)|(3+)/g来匹配字符串即可。
执行用时：80ms；内存消耗：34.8MB；var countAndSay = function(n) { let str = '1'; for (let i = 0; i < n - 1; i++) { str = str.match(/(1+)|(2+)|(3+)/g).reduce( (pre, cur) => pre + cur.length + cur[0], ''); } return str; }; -
递归法
先从1到n这个过程中，通过数组来存储当前结果，所以我们的结构可以是这样fn(index,['...'],n),然后当index==n的时候设立递归终止条件；
执行用时：124ms；内存消耗：35.1MB；var countAndSay = function(n) { const createStr = function (index, str, n) { //终止条件：查询到了第n个数了，立即返回，否则index+1 if(index == n) return str.join('') ; index++ let newChar = [] let k = 1//保存该数存在次数：当查询到不等的时候，在下方重置k for(let j = 0; j < str.length; j++) { let char = str[j] if(char == str[j+1] && j != str.length - 1) { //不等，且遍历没到底，那就继续寻找 k++ }else { newChar.push(k) newChar.push(str[j]) k=1 } } return createStr(index, newChar, n) } return createStr(1, ['1'], n) };
最后一个单词的长度
给定一个仅包含大小写字母和空格 ' ' 的字符串，返回其最后一个单词的长度。
如果不存在最后一个单词，请返回 0 。
说明：一个单词是指由字母组成，但不包含任何空格的字符串。
- 示例:
输入: "Hello World" 输出: 5
题解：
-
字符串分割法
分割成数组，然后取最后一个；
执行用时：68ms；内存消耗：33.7MB；
当然你也可以用正则；var lengthOfLastWord = function(s) { let list=s.trim().split(' ') return list[list.length-1].length }
执行用时：76ms；内存消耗：33.5MB；var lengthOfLastWord = function(s) { s = s.replace(/(\s*$)/g, "") let arr = s.split(' ') return arr[arr.length -1].length }
各位相加
给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
- 示例:
输入: 38 输出: 2 解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。由于 2 是一位数，所以返回 2。
题解：
-
递归
分割成字符串数组，然后递归，当小于10，返回结果，大于等于则递归；
执行用时：104ms；内存消耗：36MB；ar addDigits = function(num) { let val=0; let getGe=(n)=>{ const list=(n+'').split(''); let res=0; list.forEach(item=>{ res+=item-0 }) if(res>=10){ getGe(res) } if(res<10){ val= res } } getGe(num) return val } -
条件法
有循环就有条件，看见for就想到while；
执行用时：100ms；内存消耗：36.2MB；var addDigits = function(num) { let Digit=num; while(Digit>=10){ Digit=Digit+''; let list=[...Digit]; Digit=list.reduce((a,b)=>(a-0)+(b-0)) } return Digit } -
模除法
有如下关系：num = a * 10000 + b * 1000 + c * 100 + d * 10 + e
即：num = (a + b + c + d + e) + (a * 9999 + b * 999 + c * 99 + d * 9)这道题最后的目标，就是不断将各位相加，相加到最后，当结果小于10时返回。因为最后结果在1-9之间，得到9之后将不会再对各位进行相加，因此不会出现结果为0的情况。因为 (x + y) % z = (x % z + y % z) % z，又因为 x % z % z = x % z，因此结果为 (num - 1) % 9 + 1，只模除9一次，并将模除后的结果加一返回。
北风其凉 --OSCHINA但是有1个关键的问题，如果num是9的倍数，那么就不适用上述逻辑。原本我是想得到n被打包成10个1份的份数+打不进10个1份的散落个数的和。通过与9取模，去获得那个不能整除的1，作为计算份数的方式，但是如果可以被9整除，我就无法得到那个1，也得不到个位上的数。
可以这么做的原因：原本可以被完美分成9个为一份的n样物品，我故意去掉一个，那么就又可以回到上述逻辑中去得到我要的n被打包成10个一份的份数+打不进10个一份的散落个数的和。而这个减去的1就相当于从，在10个1份打包的时候散落的个数中借走的，本来就不影响原来10个1份打包的份数，先拿走再放回来，都只影响散落的个数，所以没有关系。
liveforexperience --力扣（LeetCode）这是一种数学思维，也是算法中常见的思维方式。
执行用时：100ms；内存消耗：35.4MB；var addDigits = function(num) { return (num-1)%9+1 };
第二期结束，下期见。如果有一起学习的朋友，可以加微信群。
