由于大学是文科专业，毕业后才转战前端，对算法方面可以算得上是一无所知，工作中很多时候也只是能解决问题，没有更多的考虑到运行提升、代码简洁。深刻认识到自己的不足之后，决定开始一步步嗑一下自己的算法方面，想要自己不仅仅会用，而且知道怎么用，怎么用得更好。从LeetCode的题目中记录自己的解题思路，借鉴大神更好的解题方法。

题目来源于LeetCode，执行统计皆指在LeetCode的运行结果，但是有时候同样的代码提交会有不同的结果，结果仅供参考

1、两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

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

最笨的方法：使用两层循环，外层循环计算当前元素与 target 之间的差值，内层循环寻找该差值，若找到该差值，则返回两个元素的下标

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        let secNum = target - nums[i];
        // 将secNum与num[i]后面的数对比
        // j = i + 1 ：题目要求不能重复利用数组中的元素，从i后面的数开始循环
        for (let j = i + 1; j < nums.length; j++) {
            if(nums[j] == secNum)
                return [i,j];
        }
    }
};

执行用时 :172 ms, 在所有 JavaScript 提交中击败了25.41%的用户
内存消耗 :34.7 MB, 在所有 JavaScript 提交中击败了58.05%的用户

可见，此解法中，两层循环非常浪费时间，特别是在数组元素多的情况下，更加浪费时间消耗性能。
更好的解法：利用另外的数组，计算遍历到的元素与target的差值，将该差值作为下标存入数组中，如果在该数组中不为 undefined 则返回该下标

var twoSum = function(nums, target) {
    let tmp = [];
    for(let i=0; i<nums.length; i++){
        let secNum = target - nums[i];
        if(tmp[secNum] != undefined){
            return [tmp[secNum], i]
        }
        tmp[nums[i]] = i; // 把元素值和下标反过来
    }
};

执行用时 :64 ms, 在所有 JavaScript 提交中击败了89.17%的用户
内存消耗 :34.6 MB, 在所有 JavaScript 提交中击败了70.95%的用户

但是用元素值作为下标，数组会扩容，比如：

let arr = [];
a[100] = 1;
a.length    // 101

有强迫症的小伙们会忍受不了，并且也会浪费内存。
用 map来解：

var twoSum = function(nums, target) {
  let map = new Map();
  for (let i = 0; i < nums.length; i++) {
    let dif = target-nums[i];
    // map.has(key)：返回一个bool值，用来表明map中是否存在指定元素
    if (map.has(dif)) {
      // map.get(key)：获取一个 Map对象中指定的元素
      return [map.get(dif), i]
    }
    // map.set(key,value)：为Map对象添加一个指定键(key)和值(value)
    // 此处用值来作为key，索引作为map的值
    map.set(nums[i], i);
  }
};

执行用时 :68 ms, 在所有 JavaScript 提交中击败了80.57%的用户
内存消耗 :35.1 MB, 在所有 JavaScript 提交中击败了36.26%的用户

map和空数组各有千秋，但是数据多的时候，个人感觉还是map会比较灵活。

2、整数反转

给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。

示例 :

• 输入: 123
  输出: 321

• 输入: -123
  输出: -321

• 输入: 120
  输出: 21

注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。

自己看到此题后的解法：采用反转 reverse()

• 版本1：记录每一步的运行过程，一步步进行运算

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
    var max = Math.pow(2, 31) - 1;
    var min = -Math.pow(2, 31);
    let flag = false;
    if(x < 0) {
        x = -x;
        flag = true;
    };
    // 转换成数组再反转再拼接成字符串并转成数字
    var y = Number(x.toString().split("").reverse().join(""));
    // 如果是负数
    if(flag) y = -y;
    
    if (y > max) return 0;
    if (y < min) return 0;
    return y;
};

执行用时 :88 ms, 在所有 JavaScript 提交中击败了63.77%的用户
内存消耗 :35.9 MB, 在所有 JavaScript 提交中击败了61.40%的用户

• 版本2：记录x的数值状态(正数？负数)并且在计算中直接进行转换，不再转换完成后再单独转换回来，在版本1的基础上进行提升

var reverse = function(x) {
    let max = Math.pow(2, 31) - 1;
    let min = -Math.pow(2, 31);
    // 先记录输入数字的状态，正数？负数
    const flag = x < 0 ? -1 : 1;
    // flag*x将x转换为正整数
    // 转换成数组再反转再拼接成字符串并转成数字
    // * flag再将转换后的x转变为原来的状态，正数or负数
    // 用Number来排除前面是0的数
    let y = Number((flag*x).toString().split("").reverse().join("")) * flag;
    
    if (y > max) return 0;
    if (y < min) return 0;
    
    return y;
};

执行用时 :76 ms, 在所有 JavaScript 提交中击败了95.60%的用户
内存消耗 :35.7 MB, 在所有 JavaScript 提交中击败了88.90%的用户
ps：这段代码，再次提交的时候执行结果有差异，但是总体来说比版本1好。

大神的解题：更加突出了以算术的方法去解决

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
    let max = Math.pow(2, 31) - 1;
    let min = -Math.pow(2, 31);
    let y = 0;
    while(x !== 0) { // 循环到最后x减位取整后为0为止
        // x % 10：获取x的最后一位
        // 10 * y：给y往前一位移动
        y = 10 * y + x % 10;
        // x / 10：将x减少一位
        // ~~ 取整(下文有更详细解释)
        x = ~~(x/10);
        // 并且不管x原来是正数还是负数，用%、*还是/来运算，都不会改变x原有的性质
    }
    if (y > max) return 0;
    if (y < min) return 0;
    return y;
};

执行用时 :76 ms, 在所有 JavaScript 提交中击败了95.64%的用户
内存消耗 :35.5 MB, 在所有 JavaScript 提交中击败了93.95%的用户

• 关于~~：
  ~是按位取反运算，~~是取反两次
  在这里~~的作用是去掉小数部分
  因为位运算的操作值要求是整数，其结果也是整数，所以经过位运算的都会自动变成整数
  除了~~x 还可以用x<<0、x>>0、x|0取整
  与Math.floor()不同的是，它只是单纯的去掉小数部分，不论正负都不会改变整数部分。

3、回文数

静思伊久阻归期
久阻归期忆别离
忆别离时闻漏转
时闻漏转静思伊

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

• 输入: 121
  输出: true

• 输入: -121
  输出: false
  解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

• 输入: 10
  输出: false
  解释: 从右向左读, 为 01 。因此它不是一个回文数。

进阶:你能不将整数转为字符串来解决这个问题吗？

此题的解题思路与上题一致，用上题的方法来解：

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    let max = Math.pow(2, 31) - 1;
    // 判断边界情况：0是回文数，负数可以直接排除，以0结尾的数也可以直接排除
    if(x<0 || (x%10 == 0 && x !=0)) return false;
    let _x = x;
    let y = 0;
    while(x !== 0) { // 循环到最后x减位取整后为0为止
        // x % 10：获取x的最后一位
        // 10 * y：给y往前一位移动
        y = 10 * y + x % 10;
        // x / 10：将x减少一位
        // ~~ 取整
        x = ~~(x/10);
    }
    if (y > max) return false;
    return y == x ? true : false;
};

执行用时 :208 ms, 在所有 JavaScript 提交中击败了87.21%的用户
内存消耗 :44.9 MB, 在所有 JavaScript 提交中击败了89.87%的用户

采用上一题的思路解题，需要考虑 排除边界情况。但是，如果该数较大，那么需要从尾到头依次取数很多次，很消耗时间和内存。
既然是回文数，数字是对称的，那么根据官方给的解题思路 翻转一半数字：

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {
    let max = Math.pow(2, 31) - 1;
    // 判断边界情况：0是回文数，负数可以直接排除，以0结尾的数也可以直接排除
    if(x<0 || (x%10 == 0 && x !=0)) return false;
    let y = 0;
    while(x > y) { // 循环到一半，如果y值比x值还大或相等，那说明循环了一半的数值
        // x % 10：获取x的最后一位
        // 10 * y：给y往前一位移动
        y = 10 * y + x % 10;
        // x / 10：将x减少一位
        // ~~ 取整
        x = ~~(x/10);
    }
    if (y > max) return false;
    // 如果数字长度为奇数，中位数不影响，所以~~(y / 10)排除掉中位数
    if(x === y || x === ~~(y / 10)){
        return true;
    }else{
        return false;
    };
};

执行用时 : 204ms, 在所有 JavaScript 提交中击败了91.68%的用户
内存消耗 : 44.8MB, 在所有 JavaScript 提交中击败了91.19%的用户

只处理原来的一半数据，立马就能看到效果了~

4、罗马数字转整数

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。

• 输入: "III"
  输出: 3

• 输入: "IV"
  输出: 4

• 输入: "IX"
  输出: 9

• 输入: "LVIII"
  输出: 58
  解释: L = 50, V= 5, III = 3.

• 输入: "MCMXCIV"
  输出: 1994
  解释: M = 1000, CM = 900, XC = 90, IV = 4.

前面才用了map，那就再用一次多熟悉一下：

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    let map = new Map();
    map.set('I', 1);
    map.set('V', 5);
    map.set('X', 10);
    map.set('L', 50);
    map.set('C', 100);
    map.set('D', 500);
    map.set('M', 1000);
    
    let result = 0;
    for(let i = 0; i<s.length; i++){
        // 如果后一位数比前一位大，说明这是需要特殊处理的数，先跳过，到下一次再进行相应的处理
        if(map.get(s[i]) < map.get(s[i + 1])) continue;
        // 首先看是否是上一次小的数在大的数前面而跳过处理的
        if(map.get(s[i - 1]) < map.get(s[i])){
            // 小的数在大的数前面，其值就是 大的数-小的数；例如：CD(400)=D(500)-C(100)
            result += map.get(s[i]) - map.get(s[i - 1]) 
        }else{
            result += map.get(s[i])
        }
    }
    return result;
};

执行用时 : 164ms, 在所有 JavaScript 提交中击败了69.30%的用户
内存消耗 : 40.4MB, 在所有 JavaScript 提交中击败了35.93%的用户

这个解法的关键在于，在遇到特殊情况的时候跳过一次循环，下次再进行处理。

看到有童鞋用正则来解，代码非常简洁，下面是用正则来解此题：

var romanToInt = function(s) {
    const romaMap = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000,
        'IV': 4,
        'IX': 9,
        'XL': 40,
        'XC': 90,
        'CD': 400,
        'CM': 900,
    }
    let result = 0;
    const romaSplit = s.match(/(CM)|(CD)|(XC)|(XL)|(IX)|(IV)|(IX)|(\w)/g);
    for (const v of romaSplit) {
        result += romaMap[v];
    }
    return result;
};

执行用时 : 436ms, 在所有 JavaScript 提交中击败了5.54%的用户
内存消耗 : 51.9MB, 在所有 JavaScript 提交中击败了5.05%的用户

代码和逻辑都简单很多，只是不知道为何会如此消耗时间和内存……正则如此消耗内存吗？不知道哪位童鞋可以帮我解个惑

5、最长公共前缀

ps：本来这题我不想写的，但是看到评论有人用every()让我又学习到了一点，所以写下来做个对比

看到题目想到的方法：用每一项来跟第一项做对比

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {
    let mostWord = '';
    if(strs.length){ // 排除掉空数组的情况
        // 第一层，拿出第一项，剩下的每一项拿来跟第一项的每个数来做对比
        for(let i = 0; i <strs[0].length; i++){
            // 第二层，后面的每一项与该项做对比
            for(let j = 1; j <strs.length; j++){
                if(strs[j][i] != strs[0][i]){
                    return mostWord;
                }
            }
            mostWord += strs[0][i];
        }
    }
    return mostWord;
};

执行用时 : 52ms, 在所有 JavaScript 提交中击败了99.69%的用户
内存消耗 : 35.2MB, 在所有 JavaScript 提交中击败了49.77%的用户

用 every的方法

var longestCommonPrefix = function(strs) {
    let arr = [];
    let result = "";
    for(let i = 0; i < strs.length; i++){
        arr.push(strs[i].length);
    }
    // 排序，找出长度最短的元素（可以不进行排序，区别就是节约一些时间多消耗一些内存）
    arr.sort((a, b) => a - b);
    for(let j = 0; j < arr[0]; j++){
        let s = strs[0][j]; // 也是用第一项来进行对比
        if(strs.every(val => val[j] == s)){ // val就是数组中的每一个元素
            result += s;
        }else{
            break;
        }
    }
    return result;
};

执行用时 : 100ms, 在所有 JavaScript 提交中击败了6.64%的用户
内存消耗 : 34.6MB, 在所有 JavaScript 提交中击败了74.66%的用户

关于 every()：

• every() 方法使用指定函数检测数组中的所有元素：
  如果数组中检测到有一个元素不满足，则整个表达式返回 false ，且剩余的元素不会再进行检测。
• 注意： every() 不会对空数组进行检测。

6、删除排序数组中的重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

• 给定数组 nums = [1,1,2],
  函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
  你不需要考虑数组中超出新长度后面的元素。

• 给定 nums = [0,0,1,1,1,2,2,3,3,4],
  函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
  你不需要考虑数组中超出新长度后面的元素。

说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

对于js er来说，一看到这题目不就是 splice吗，先撸一个再说：

/**
 * @param {number[]} nums
 * @return {number}
 * 使用一个临时数组，将数组中的每一个元素存入临时数组中，如果元素没有在临时数组中出现过，则将该元素加入数组，若是出现过，则就地删除这个元素
 */
var removeDuplicates = function(nums) {
    if (nums == []) return 0;
    var tmp = [];
    for(let i = 0; i < nums.length; i++){
        if(nums[i] == tmp[tmp.length - 1]){ // 该元素在数组中已存在，删除该元素
            nums.splice(i,1);
            i--; // 此时nums的长度已经改变
        }else{
            tmp.push(nums[i])
        }
    }
    return nums.length;
};

就感觉特别简单也特别自信，一提交代码，哦豁，执行结果……那可真是惨不忍睹，没眼看

执行用时 :108 ms, 在所有 JavaScript 提交中击败了32.19%的用户
内存消耗 :37.9 MB, 在所有 JavaScript 提交中击败了14.05%的用户

看了官方的解题，使用双指针，妙啊 妙：
数组完成排序后，我们可以放置两个指针 i 和 j，其中 i 是慢指针，而 j 是快指针。只要 nums[i] = nums[j]，我们就增加 j 以跳过重复项。

当我们遇到 nums[j] != nums[i] 时，跳过重复项的运行已经结束，因此我们必须把它（nums[j]）的值复制到 nums[i + 1]。然后递增 i，接着我们将再次重复相同的过程，直到 j 到达数组的末尾为止。

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

执行用时 :84 ms, 在所有 JavaScript 提交中击败了75.22%的用户
内存消耗 :36.9 MB, 在所有 JavaScript 提交中击败了69.44%的用户