如果每天做一道算法题，那是不是每天都在进步？
前言
这个活动是从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() };
第一期结束，下期见。如果有一起学习的朋友，可以加微信群。
每天一道算法题（第一期）
镇楼
网友评论