Leetcode-做题学算法周刊第一期

35次阅读

共计 11092 个字符，预计需要花费 28 分钟才能阅读完成。

首发于微信公众号《前端成长记》，写于 2019.10.28

背景

本文记录刷题过程中的整个思考过程，以供参考。主要内容涵盖：

  • 题目分析设想
  • 编写代码验证
  • 查阅他人解法
  • 思考总结

目录

  • 1. 两数之和
  • 7. 整数反转
  • 9. 回文数
  • 13. 罗马数字转整数
  • 14. 最长公共前缀

Easy

1. 两数之和

题目地址

题目描述

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

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

示例：

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

题目分析设想

这道题首先说明了每种输入只会对应一个答案，并且不能利用数组中同样的元素，也就意味着一个数不能被使用两次，即 [0,0] 这种是不合理的。

看到这个题目，我有几个方向去尝试作答：

  • 暴力点，直接循环两次即可，预估性能最差
  • IndexOf，循环次数最多，非常不推荐
  • 空间换时间，使用 HashMap , 减少一次循环

编写代码验证

Ⅰ. 暴力法

代码：

// 暴力点
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {for(let i = 0; i < nums.length; i++) {
        // j 从 i+1 开始，去除一些无用运算
        for(let j = i + 1; j < nums.length; j++) {if (nums[i] + nums[j] === target) {return [i,j];
            }
        }
    }
};

结果：

  • 29/29 cases passed (124 ms)
  • Your runtime beats 60.13 % of javascript submissions
  • Your memory usage beats 66.05 % of javascript submissions (34.5 MB)
  • 时间复杂度：O(n^2)

Ⅱ.IndexOf

性能最差，每次判断都需要遍历剩余数组（极度不推荐，只是多展示一个实现方案）

代码：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {for(let i = 0; i < nums.length; i++) {const num = nums[i]
        const dif = target - num
        const remainArr = nums.slice(i + 1)
        if (remainArr.indexOf(dif) !== -1) {return [i, remainArr.indexOf(dif) + i + 1]
        }
    }
};

结果：

  • 29/29 cases passed (212 ms)
  • Your runtime beats 22.39 % of javascript submissions
  • Your memory usage beats 5 % of javascript submissions (49 MB)
  • 时间复杂度：O(n^2)，阶乘的时间复杂度为 O(n)

Ⅲ.HashMap

代码：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {let hash = {}
    for(let i = 0; i < nums.length; i++) {const num = nums[i]
        const dif = target - num
        if (hash[dif] !== undefined) {return [hash[dif], i]
        } else {hash[num] = i
        }
    }
};

结果：

  • 29/29 cases passed (60 ms)
  • Your runtime beats 98.7 % of javascript submissions
  • Your memory usage beats 19.05 % of javascript submissions (35.3 MB)
  • 时间复杂度：O(n)

对比发现，HashMap 方案较暴力法在速度上有明显的提升。

查阅他人解法

这里看到还有两种方式，我们一一来尝试一下。

Ⅰ. 使用数组替换 HashMap

代码：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {let arr = []
    for(let i = 0; i < nums.length; i++) {const num = nums[i]
        const dif = target - num
        if (arr[dif] !== undefined) {return [arr[dif], i]
        } else {arr[num] = i
        }
    }
};

结果：

  • 29/29 cases passed (60 ms)
  • Your runtime beats 98.7 % of javascript submissions
  • Your memory usage beats 17.89 % of javascript submissions (35.4 MB)
  • 时间复杂度：O(n)

跟使用 HashMap 性能差异不大。

Ⅱ. 两次遍历 HashMap

代码：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {let res = new Map()
    for(let i = 0; i < nums.length; i++) {res.set(nums[i], i)
    }
    for(let i = 0; i < nums.length; i++) {const num = nums[i]
        const dif = target - num
        const idx = res.get(dif)
        if (idx !== undefined && idx !== i) {return [i, idx]
        }
    }
};

结果：

  • 29/29 cases passed (64 ms)
  • Your runtime beats 96.76 % of javascript submissions
  • Your memory usage beats 10.94 % of javascript submissions (35.9 MB)
  • 时间复杂度：O(n)

思考总结

这里我做个了简单的校验：输入 [2,2,2], 4，发现期望输出是 [0, 2]，而不是 [0, 1] , 所以上面有几种解法实际上都过不了。如果是为了满足这种输出，我的推荐方案是 两次遍历 HashMap。但是我个人是觉得 HashMap 一次遍历是更合理的。

7. 整数反转

题目地址

题目描述

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

示例:

输入: 123
输出: 321

输入: -123
输出: -321

输入: 120
输出: 21

注意:

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

题目分析设想

从题干上来看，有几个要注意的点：

  • 溢出返回 0
  • 0 为首位需要去掉取自然数

这里我有两种思路：

  • 利用数组反转 reverse 来反转再做自然数转换
  • 取余拿到每位上的数字再做加法和符号及溢出处理

编写代码验证

Ⅰ. 数组反转

代码：

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
    const isNegative = x < 0
    const rev = Number(Math.abs(x).toString().split('').reverse().join(''))
    if (isNegative && -rev >= -Math.pow(2, 31)) {return -rev} else if (!isNegative && rev <= Math.pow(2,31) - 1) {return rev} else {return 0}
};

结果：

  • 1032/1032 cases passed (96 ms)
  • Your runtime beats 73.33 % of javascript submissions
  • Your memory usage beats 28.03 % of javascript submissions (35.9 MB)
  • 时间复杂度：O(1)

Ⅱ. 取余

代码：

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {
    const isNegative = x < 0
    let res = 0
    while(x !== 0) {
        res = res * 10 + x % 10
        x = parseInt(x / 10)
    }
    if ((isNegative && res >= -Math.pow(2, 31)) || (!isNegative && res <= Math.pow(2,31) - 1)) {return res} else {return 0}
};

结果：

  • 1032/1032 cases passed (80 ms)
  • Your runtime beats 96.71 % of javascript submissions
  • Your memory usage beats 56.8 % of javascript submissions (35.7 MB)
  • 时间复杂度：O(log10(n))

对比发现，使用取余的方式，性能上明显优于数组反转。

查阅他人解法

思路基本上都是这两种，未发现方向不同的解法。

思考总结

对比发现还有一些考虑不周的地方需要补全，比如说一些特殊值可直接返回，避免运算。这里我也做了一个简单的校验：输入 -0，发现期望输出是 0 而不是 -0。所以，我这里的代码做一些优化，如下：

/**
 * @param {number} x
 * @return {number}
 */
var reverse = function(x) {if (x === 0) return 0
    function isOverflow (num) {return num < -Math.pow(2, 31) || (num > Math.pow(2,31) - 1)
    }
    if (isOverflow(x)) return 0
    let res = 0
    while(x !== 0) {
        res = res * 10 + x % 10
        x = parseInt(x / 10)
    }
    return isOverflow(res) ? 0 : res
};

9. 回文数

题目地址

题目描述

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

示例：

输入: 121
输出: true

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

进阶:

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

题目分析设想

这道题的第一感觉有点类似上一题整数反转的拓展，所以我们从两个方向入手：

  • 整数转字符串
  • 取余，前后逐位判断

在写的过程中需要考虑到去掉一些运算：把 <0 和 -0 排除，因为负数和 -0 一定不为回文数；一位正整数一定是回文数；除了 0 以外，尾数为 0 的不是回文数。

编写代码验证

Ⅰ. 转字符串

代码：

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {if (x < 0 || Object.is(x, -0) || (x % 10 === 0 && x !== 0)) return false;
    if (x < 10) return true;
    const rev = parseInt(x.toString().split('').reverse().join(''))
    return rev === x
};

结果：

  • 11509/11509 cases passed (252 ms)
  • Your runtime beats 79.41 % of javascript submissions
  • Your memory usage beats 52 % of javascript submissions (45.7 MB)
  • 时间复杂度：O(1)

这里有用到 ES6 的 Object.is 来判断是否为 -0，当然 ES5 你也可以这么判断：

function (x) {return x === 0 && 1 / x < 0;    // -Infinity}

可能有人会问不需要考虑数字溢出问题吗？

输入的数字不溢出，如果是回文数的话，那么输出的数字一定不溢出；如果不是回文数，不管溢出与否，都是返回 false。

Ⅱ. 取余

代码：

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {if (x < 0 || Object.is(x, -0) || (x % 10 === 0 && x !== 0)) return false;
    if (x < 10) return true;
    let div = 1
    while (x / div >= 10) { // 用来找出位数，比如 121，那么就找到 100，得到整数位
        div *= 10
    }
    while(x > 0) {let left = parseInt(x / div); // 左侧数起
        let right = x % 10; // 右侧数起
        if (left !== right) return false;

        x = parseInt((x % div) / 10);   // 去掉左右各一位数

        div /= 100; // 除数去两位
    }
    return true;
};

结果：

  • 11509/11509 cases passed (232 ms)
  • Your runtime beats 86.88 % of javascript submissions
  • Your memory usage beats 67.99 % of javascript submissions (45.5 MB)
  • 时间复杂度：O(log10(n))

查阅他人解法

这里看到一个更为巧妙的方式，只需要翻转一半即可。比如说 1221，只需要翻转后两位 21 即可。

Ⅰ. 翻转一半

代码：

/**
 * @param {number} x
 * @return {boolean}
 */
var isPalindrome = function(x) {if (x < 0 || Object.is(x, -0) || (x % 10 === 0 && x !== 0)) return false;
    if (x < 10) return true;
    let rev = 0;    // 翻转的数字

    while(x > rev) {
        rev = rev * 10 + x % 10
        x = parseInt(x / 10)
    }

    return x === rev || x === parseInt(rev / 10);   // 奇数的话需要去掉中间数做比较
};

结果：

  • 11509/11509 cases passed (188 ms)
  • Your runtime beats 99.62 % of javascript submissions
  • Your memory usage beats 92.69 % of javascript submissions (44.8 MB)
  • 时间复杂度：O(log10(n))

思考总结

综上，最推荐翻转一半的解法。

13. 罗马数字转整数

题目地址

题目描述

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

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000

例如，罗马数字 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.

题目分析设想

这道题有个比较直观的想法，因为特殊情况有限可枚举，所以我这里有两个方向：

  • 枚举所有特殊组合，然后进行字符串遍历
  • 直接字符串遍历，判断当前位和后一位的大小

编写代码验证

Ⅰ. 枚举特殊组合

代码：

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    const hash = {
        'I': 1,
        'IV': 4,
        'V': 5,
        'IX': 9,
        'X': 10,
        'XL': 40,
        'L': 50,
        'XC': 90,
        'C': 100,
        'CD': 400,
        'D': 500,
        'CM': 900,
        'M': 1000
    }
    let res = 0
    for(let i = 0; i < s.length;) {if (i < s.length - 1 && hash[s.substring(i, i + 2)]) { // 在 hash 表中，说明是特殊组合
            res += hash[s.substring(i, i + 2)]
            i += 2
        } else {res += hash[s.charAt(i)]
            i += 1
        }
    }
    return res
};

结果:

  • 3999/3999 cases passed (176 ms)
  • Your runtime beats 77.06 % of javascript submissions
  • Your memory usage beats 80.86 % of javascript submissions (39.8 MB)
  • 时间复杂度：O(n)

Ⅱ. 直接遍历

代码：

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    const hash = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    }
    let res = 0
    for(let i = 0; i < s.length; i++) {if (i === s.length - 1) {res += hash[s.charAt(i)]
        } else {if (hash[s.charAt(i)] >= hash[s.charAt(i + 1)]) {res += hash[s.charAt(i)]
            } else {res -= hash[s.charAt(i)]
            }
        }
    }
    return res
};

结果：

  • 3999/3999 cases passed (176 ms)
  • Your runtime beats 84.42 % of javascript submissions
  • Your memory usage beats 90.55 % of javascript submissions (39.6 MB)
  • 时间复杂度：O(n)
查阅他人解法

这里还看到一种方式，全部先按加法算，如果有前一位小于后一位的情况，直接减正负差值 2/20/200。来看看代码：

Ⅰ. 差值运算

代码：

/**
 * @param {string} s
 * @return {number}
 */
var romanToInt = function(s) {
    const hash = {
        'I': 1,
        'V': 5,
        'X': 10,
        'L': 50,
        'C': 100,
        'D': 500,
        'M': 1000
    }
    let res = 0
    for(let i = 0; i < s.length; i++) {res += hash[s.charAt(i)]
        if (i < s.length - 1 && hash[s.charAt(i)] < hash[s.charAt(i + 1)]) {res -= 2 * hash[s.charAt(i)]
        }
    }
    return res
};

结果：

  • 3999/3999 cases passed (232 ms)
  • Your runtime beats 53.57 % of javascript submissions
  • Your memory usage beats 80.05 % of javascript submissions (39.8 MB)
  • 时间复杂度：O(n)

换汤不换药，只是做了个加法运算而已，没有太大的本质区别。

思考总结

综上，暂时没有看到一些方向上不一致的解法。我这里推荐字符串直接遍历的解法，性能最佳。

14. 最长公共前缀

题目地址

题目描述

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例：

输入: ["flower","flow","flight"]
输出: "fl"

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z。

题目分析设想

这道题一看觉得肯定是需要遍历的题，无非是算法上的优劣罢了。我有三个方向来尝试解题：

  • 遍历每列，取出数组第一项，逐个取字符串的每一位去遍历数组
  • 遍历每项，取出数组第一项，逐步从后截取，判断是否匹配数组中的每一项
  • 分治，将数组递归不断细成俩部分，分别求最大匹配后，再汇总求最大匹配

编写代码验证

Ⅰ. 遍历每列

代码：

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {if (strs.length === 0) return ''if (strs.length === 1) return strs[0] ||''
    const str = strs.shift()
    for(let i = 0; i < str.length; i++) {const char = str.charAt(i)
        for(let j = 0; j < strs.length; j++) {if (i === strs[j].length || strs[j].charAt(i) !== char) {return str.substring(0, i)
            }
        }
    }
    return str
};

结果：

  • 118/118 cases passed (68 ms)
  • Your runtime beats 89.17 % of javascript submissions
  • Your memory usage beats 57.83 % of javascript submissions (34.8 MB)
  • 时间复杂度：O(n)

Ⅱ. 遍历每项

代码：

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {if (strs.length === 0) return ''if (strs.length === 1) return strs[0] ||''
    let str = strs.shift()
    for(let i = 0; i < strs.length; i++) {while (strs[i].indexOf(str) !== 0) {str = str.substring(0, str.length - 1);
            if (!str) return ''
        }
    }
    return str
};

结果：

  • 118/118 cases passed (64 ms)
  • Your runtime beats 94.63 % of javascript submissions
  • Your memory usage beats 96.69 % of javascript submissions (33.5 MB)
  • 时间复杂度：O(n)

Ⅲ. 分治

代码：

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {if (strs.length === 0) return ''if (strs.length === 1) return strs[0] ||''
    function arrayToString (arr, start, end) {if (start === end) {    // 说明数组中只剩一项了
            return arr[start]
        } else {const mid = parseInt((start + end) / 2)
            const leftStr = arrayToString(arr, start, mid)
            const rightStr = arrayToString(arr, mid + 1, end)
            return getCommonPrefix(leftStr, rightStr)
        }
    }
    // 两个字符串取最长前缀
    function getCommonPrefix(left, right) {const min = Math.min(left.length, right.length)
        for(let i = 0; i < min; i++) {if (left.charAt(i) !== right.charAt(i)) {return left.substring(0, i)
            }
        }
        return left.substring(0, min)
    }
    return arrayToString(strs, 0, strs.length - 1)
};

结果：

  • 118/118 cases passed (60 ms)
  • Your runtime beats 98.09 % of javascript submissions
  • Your memory usage beats 34.54 % of javascript submissions (35.1 MB)
  • 时间复杂度：O(n)

查阅他人解法

这里还看见使用二分法，跟分治还是略有差异，是每次丢弃不包含答案的区间来减少运算量。

Ⅰ. 二分法

代码：

/**
 * @param {string[]} strs
 * @return {string}
 */
var longestCommonPrefix = function(strs) {if (strs.length === 0) return ''if (strs.length === 1) return strs[0] ||''
    // 找到最短字符串长度
    let minLen = 0
    for(let i = 0; i < strs.length; i++) {minLen = minLen === 0 ? strs[i].length : Math.min(minLen, strs[i].length)
    }

    function isCommonPrefix (arr, pos) {const str = arr[0].substring(0, pos)    // 取第一项的前一半
        for(let i = 0 ; i < arr.length; i++) {if (arr[i].indexOf(str) !== 0) {return false}
        }
        return true
    }

    let low = 1
    let high = minLen   // 截取最大数量

    while (low <= high) {const mid = parseInt((low + high) / 2)
        if (isCommonPrefix(strs, mid)) {    // 如果前半段是
            low = mid + 1   // 继续判断后半段
        } else {high = mid - 1  // 前半段继续对半分继续判断}
    }

    return strs[0].substring(0, (low + high) / 2)
};

结果：

  • 118/118 cases passed (64 ms)
  • Your runtime beats 94.63 % of javascript submissions
  • Your memory usage beats 93.96 % of javascript submissions (33.5 MB)
  • 时间复杂度：O(log(n))

思考总结

具体情况具体分析，比如分治的算法也可以应用在快速排序中。个人比较推荐分治法和二分法求解这道题。

（完）

本文为原创文章，可能会更新知识点及修正错误，因此转载请保留原出处，方便溯源，避免陈旧错误知识的误导，同时有更好的阅读体验
如果能给您带去些许帮助，欢迎 ⭐️star 或 ✏️ fork
(转载请注明出处：https://chenjiahao.xyz)

正文完
leetcode 算法
发表至： javascript
2019-10-28
 0
关于javascript:纯webpack搭建vue脚手架单页面应用
vue-formData上传图片以及其他表单数据
关于javascript:前端面试每日-31-第876天
关于javascript:JavaScript高级程序设计笔记05-基本引用类型