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

如果每天做一道算法题，那是不是每天都在进步？

前言

这个活动是从2019年7月中旬开始的，人数不算多，也就几个好友和好友的好友，过程中也会有人因为工作的缘故或其他原因放弃，或许未来还会有人离开。

活动的主要形式就是在leetcode刷题，每个工作日一道题，每周做总结，目前已经是第十二期，接下来我会把每期的题做一个总结，由于我是侧重javascript，所以活动中的每道题都是以js语言来实现解题方法。

活动的规则比较严谨，群里每天早上10点之前发题，晚上10点审核，审核有管理员专门审核，称为打卡，没有打卡的人，需要发红包给管理员作为每天统计费用。

活动的目的就是培养算法思维，了解常见的算法，比如分治算法、贪心算法、动态优化等等。

微信公众号惊天码盗同步第一期。

两个数组的交集 II

给定两个数组，编写一个函数来计算它们的交集。

• 示例 1:

  输入: nums1 = [1,2,2,1], nums2 = [2,2]
  输出: [2,2]
  

• 示例 2:

  输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
  输出: [4,9]
  

题解：

• 替换法
  循环nums1，在循环中判断nums2中是否存在当前元素，如果存在就push到新的数组，然后在通过splice替换到当前元素，最后排序；
  执行用时：88ms；内存消耗：35.5MB;

  var intersect = function(nums1, nums2) {
      let arr = [];
      nums1.forEach((cur, i) => {
        if (nums2.indexOf(cur) > -1) {
          arr.push(cur)
          nums2.splice(nums2.indexOf(cur), 1, null)
        }
      })
      return arr.sort()
  }; 
  

• 双指针法
  两个数组排序，设定两个为0的指针，比较两个指针的元素是否相等，如果相等，元素push到返回值里，两个指针同时往前，如果不相等，元素小的指针往前。
  执行用时：84ms；内存消耗：35MB；

  var intersect = function(nums1, nums2) {
      let p1 = 0
      let p2 = 0
      let res = []
      nums1 = nums1.sort((a, b) => a - b)
      nums2 = nums2.sort((a, b) => a - b)
      while(p1 < nums1.length && p2 < nums2.length) {
          if(nums1[p1] == nums2[p2]) {
              res.push(nums1[p1])
              p1++
              p2++
          } else if(nums1[p1] < nums2[p2]) {
              p1++
          } else {
              p2++
          }
      }
      return res
  }
  

---

1比特与2比特字符

有两种特殊字符。第一种字符可以用一比特0来表示。第二种字符可以用两比特(10 或 11)来表示。

现给一个由若干比特组成的字符串。问最后一个字符是否必定为一个一比特字符。给定的字符串总是由0结束。

• 示例 1:

  输入: bits = [1, 0, 0]
  输出: True
  解释: 唯一的编码方式是一个两比特字符和一个一比特字符。所以最后一个字符是一比特字符。
  

• 示例 2:

  输入: bits = [1, 1, 1, 0]
  输出: False
  解释: 唯一的编码方式是两比特字符和两比特字符。所以最后一个字符不是一比特字符。
  

题解：

• 正则
  这是我见过最暴力直接的方式，由群内小伙伴提出的解题方式。
  执行用时：84ms；内存消耗：34.4MB；（我感觉这个测试不准，每次提交的用时和消耗均不同）

   var isOneBitCharacter = function(bits) {
    return /^(10||11||0)*0$/.test(bits.join(""))
   };
  

• 对象存储
  通过对象的方式；在循环中判断，如果遇到0、10或者11等情况添加到对象的属性上，这种方式可以有效的记录一共出现1比特和2比特出现的次数和顺序；最后判断最后一个比特是1比特还是2比特。
  执行用时：88ms；内存消耗：37.6MB；

  var isOneBitCharacter = function(bits) {
      let obj = {};
      let count = 1;
      bits.forEach((item, i) => {
        if (!obj[count]) obj[count] = [];
        if (obj[count].length >= 2) {count++; obj[count] = []};
        obj[count].push(item)
        if (obj[count][0] == 0 && i!=bits.length-1) count++;
      })
      return obj[count]&&obj[count][0] === 0 ? true : false
  };
    //对象结构如下
    {
      1:[0],
      2:[1,1],
      3:[1,0],
      ...
    } 
  

• 循环跳跃法
  循环，遇1就++，如果++后跳出循环，就返回false，如果还在循环内，当循环到最后一个的时候返回true；
  执行用时：72ms；内存消耗：34.2MB；

  var isOneBitCharacter = function(bits) {
    let bitsSize = bits.length
    for (let i = 0; i < bitsSize; ++i) {
      if (i == bitsSize - 1) return true
      if (bits[i])++i;
    }
    return false;
  };
  

---

二进制求和

给定两个二进制字符串，返回他们的和（用二进制表示）。
输入为非空字符串且只包含数字 1 和 0。

• 示例 1:

  输入: a = "11", b = "1"
  输出: "100"
  

• 示例 2:

  输入: a = "1010", b = "1011"
  输出: "10101"
  

题析：

面对这道题，很多人立马想到的是2转10，然后转2，但是这会面临精度丢失的问题，如果解决了精度丢失的问题，那么也不失为一个好的解题方法。那么就只有一种方法那就是逐位相加法。

题解：

• 补位法
  字符串转数组，然后翻转数组，取数组最长的length循环，在循环中数组短的自动补0，在循环中相加，判断相加为0或1或2的情况。然后push到新数组中，最后翻转，转成字符串。
  执行用时：108ms；内存消耗：35.6MB；（最笨的办法）

  var addBinary = function(a, b) {
    const alist=a.split('').reverse();
    const blist=b.split('').reverse();
    const arr=[];
    const len=alist.length>blist.length?alist.length:blist.length;
    for (let i = 0; i <= len-1; i++) {
        if (alist[i] != 0 && alist[i] != 1) {
          alist[i] = 0
        }
        if (blist[i] != 0 && blist[i] != 1) {
          blist[i] = 0
        }
        alist[i] = alist[i] - 0
        blist[i] = blist[i] - 0
  
        if (alist[i] + blist[i] > 1) {
          if (arr[i] == 0) {
            arr[i] = 1
          } else if (arr[i] == 1) {
            arr[i] = 1
            arr.push(1)
         } else {
            arr[i] = 0
            arr.push(1)
          }
        }
        if (alist[i] + blist[i] == 1) {
          if (arr[i]) {
            arr[i] = 0
            arr.push(1)
          } else {
            arr[i] = 1
          }
        }
        if (alist[i] + blist[i] == 0) {
          if (arr[i]) {
            arr[i] = 1
          } else {
            arr[i] = 0
          }
        }
      }
      return arr.reverse().join('')
  };
  

• 进位拼接法
  与补位法类似，区别就是在进行计算时直接拼接字符串，会得到一个反向字符，需要最后再进行翻转；按照位置给结果字符赋值，最后如果有进位，则在前方进行字符串拼接添加进位。
  执行用时：112ms；内存消耗：35.9MB；（性能不好）

  var addBinary = function(a, b) {
    let ans = "";
    let ca = 0;
    for(let i = a.length - 1, j = b.length - 1;i >= 0 || j >= 0; i--, j--) {
        let sum = ca;
        sum += i >= 0 ? parseInt(a[i]) : 0;
        sum += j >= 0 ? parseInt(b[j]) : 0;
        ans += sum % 2;
        ca = Math.floor(sum / 2);
    }
    ans += ca == 1 ? ca : "";
    return ans.split('').reverse().join('');
  }
  

---

两数之和

给定一个整数数组 nums和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

• 示例:

  给定 nums = [2, 7, 11, 15], target = 9
  因为nums[0] + nums[1] = 2 + 7 = 9
  所以返回 [0, 1]
  

题解：

• 双循环法
  两层循环，外层取第一元素，内层取相加元素;
  执行用时：164ms；内存消耗：34.6MB；

  var twoSum = function(nums, target) {
   for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j]
       }
     }
   }
  };
  

• 替换法
  复制原数组，循环原数组，防止重复，通过splice替换复制的数组，如果复制数组中存在相加元素，找到索引，即可得到结果数组。
  执行用时：304ms；内存消耗：36MB；

  var twoSum = function(nums, target) {
    let list = [...nums];
    let arr = []
    nums.forEach((item, i) => {
      list.splice(i, 1, null)
      const sum = target - item;
      if (list.includes(sum)) {
        arr = [i, list.indexOf(sum)].sort()
      }
    })
    return arr
  }
  

• map
  通过新的数据类型Map来实现；
  执行用时：72ms；内存消耗：35.1MB；

  var twoSum = function(nums, target) {
    let map = new Map()
    for (let i = 0; i < nums.length; i++) {
       if (map.has(target - nums[i])) {
          return [map.get(target - nums[i]), i]
        }
        map.set(nums[i], i)
     }
  }
  

---

加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

• 示例 1:

  输入: [1,2,3]
  输出: [1,2,4]
  解释: 输入数组表示数字 123。
  

• 示例 2:

  输入: [4,3,2,1]
  输出: [4,3,2,2]
  解释: 输入数组表示数字 4321。
  

题解：

• 递减相加法
  循环递减，在循环中判断相加是否为10，如果为10，就把当前值改为0，下一值加一；
  执行用时：72ms；内存消耗：33.6MB；（性能不好）

  var plusOne = function(digits) {
    for(let i=digits.length-1;i>=0;i--){
        if(i==digits.length-1){
            digits[i]++
        }
        if(digits[i]==10){
            digits[i]=0
            if(i-1<0){
                digits.unshift(1)
            }else{    
                digits[i-1]++
            }
        }
    }
    return digits
  };
  

• 迭代
  for循环可以实现的，while也可以实现；
  执行用时：72ms；内存消耗：34.2MB；

  var plusOne = function(digits) {
    const values = digits.reverse();
    let i = 0;
    values[i] += 1;
    while (true) {
      if (values[i] >= 10) {
        values[i] = 0;
        if (values[i + 1] === undefined) {
          values[i + 1] = 1;
          break;
        } else {
          values[i + 1] += 1
        }
        i++
      } else {
        break;
      }
    }
    return values.reverse()
  };
  

---

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

每天一道算法题（第一期） 镇楼