阅读 49

【Leetcode 做题学算法周刊】第一期

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

背景

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

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

目录

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)

这里有用到 ES6Object.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,DM

字符 数值
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 (转载请注明出处:chenjiahao.xyz)