每天一道算法题（第二期）

前言

算法这个活动很严，每天必须打卡，而且不限制语言，群内已有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中存的是

  { 
    0:{count:1,value:1},
    1:{count:1,value:2},
    2:{count:2,value:1}
  }//拼接之后就是111221
  

  obj的每一个key值就是n，value就是报数字符串；
  执行用时：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
  };
  

---

第二期结束，下期见。如果有一起学习的朋友，可以加微信群。

image.png