【Leetcode 做题学算法周刊】第三期 #46

ChenJiaH · 2019-11-13T12:11:38Z

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

背景

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

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

Easy

35.搜索插入位置

题目地址

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例：

输入: [1,3,5,6], 5
输出: 2

输入: [1,3,5,6], 2
输出: 1

输入: [1,3,5,6], 7
输出: 4

输入: [1,3,5,6], 0
输出: 0

题目分析设想

这道题目有点明显，题干说明了是排序数组，重点是排序数组，所以很明显的第一反应会使用二分法来解题。同时可以注意一下，数组中无重复元素。所以这道题我就按两个方案来作答：

暴力法，直接遍历
二分法，可以理解成不断折半排除不可能

编写代码验证

Ⅰ.暴力法

代码：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    if (nums.length === 0 || nums[0] > target) return 0;
    if(nums[nums.length - 1] < target) return nums.length;

    for(let i = 0; i < nums.length; i++) {
        if(nums[i] >= target) return i
    }
};

结果：

62/62 cases passed (60 ms)
Your runtime beats 92.48 % of javascript submissions
Your memory usage beats 63.22 % of javascript submissions (33.8 MB)
时间复杂度 O(n)

Ⅱ.二分法

代码：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    if (nums.length === 0 || nums[0] > target) return 0;
    if(nums[nums.length - 1] < target) return nums.length;

    let left = 0; // 起点
    let right = nums.length - 1; // 终点
    while(left < right) {
         // 零填充右位移，使用位运算避免溢出，大部分情况下等于 (left + right / 2)
        let i = parseInt((left + right) >>> 1) // 这里选择取左
        if (nums[i] < target) { // 中位数小于目标值
            left = i + 1 // 排除中位数左侧
        } else {
            right = i // 排除中位数右侧
        }
    }
    return left
};

结果：

62/62 cases passed (52 ms)
Your runtime beats 99.31 % of javascript submissions
Your memory usage beats 61.31 % of javascript submissions (33.8 MB)
时间复杂度 O(log2(n))

查阅他人解法

基本上这道题就是针对二分法进行考察的，所以没有看到其他特别的解法。

思考总结

看见排序数组，查找下标，那么就可以果断选择二分法啦。

38.报数

题目地址

题目描述

报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221

1 被读作 "one 1" ("一个一"),即 11。

11 被读作 "two 1s" ("两个一"),即 21。

21 被读作 "one 2", "one 1" （"一个二" , "一个一") , 即 1211。

给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。

注意：整数顺序将表示为一个字符串。

示例:

输入: 1
输出: "1"

输入: 4
输出: "1211"

题目分析设想

这道题目有点绕，其实我们只看右侧项就可以，每次都是读上一次项。报数的规则实际上就是相同连续数字合并后进行每位的报数。最简单的想法是直接使用正则替换就可以了。当然也可以从递归和遍历的方式来作答，我们分别来看看。

正则法，替换相同连续数字为 长度 + 数字本身
递归法，不断转换成 n-1 求解
遍历法，不断转换成 n+1 求解

编写代码验证

Ⅰ.正则法

代码：

/**
 * @param {number} n
 * @return {string}
 */
var countAndSay = function(n) {
    let str = '1'
    for(let i = 1; i < n; i++) {
        // 匹配项长度+第一位即为读数
        str = str.replace(/(\d)\1*/g, (match) => (`${match.length}${match.charAt(0)}`))
    }
    return str
};

结果：

18/18 cases passed (56 ms)
Your runtime beats 98.81 % of javascript submissions
Your memory usage beats 32.53 % of javascript submissions (35.6 MB)
时间复杂度 O(n)

Ⅱ.递归法

代码：

/**
 * @param {number} n
 * @return {string}
 */
var countAndSay = function(n) {
    if (n === 1) return '1'
    debugger
    let str = countAndSay(n - 1)
    let item = str.charAt(0)

    let count = 0 // 计数器
    let res = ''
    for(let i = 0; i < str.length; i++) {
        if(str.charAt(i) === item) {
            count++
        } else {
            res += `${count}${item}`
            item = str.charAt(i)
            count = 1
        }

        if (i === str.length - 1) { // 最后一位，需要取数
            res += `${count}${item}`
        }
    }
    return res
};

结果：

18/18 cases passed (64 ms)
Your runtime beats 92.23 % of javascript submissions
Your memory usage beats 28.23 % of javascript submissions (35.7 MB)
时间复杂度 O(n^2)

Ⅲ.遍历法

代码：

/**
 * @param {number} n
 * @return {string}
 */
var countAndSay = function(n) {
    let str = '1'
    for(let i = 1; i < n; i++) {
        str = countEach(str)
    }
    function countEach(str) {
        let count = 0
        let res = ''
        for(let i = 0; i < str.length; i++) {
            if(i === 0 || str.charAt(i) === str.charAt(i - 1)) {
                count++
            } else {
                res += `${count}${str.charAt(i - 1)}`
                count = 1
            }
            if (i === str.length - 1) {
                res += `${count}${str.charAt(i)}`
            }
        }

        return res
    }

    return str
};

结果：

18/18 cases passed (60 ms)
Your runtime beats 96.98 % of javascript submissions
Your memory usage beats 41.69 % of javascript submissions (35.5 MB)
时间复杂度 O(n^2)

查阅他人解法

这里看到一个开怀一笑的解法，直接字典法，缺点很明显，但是当前情况下确实是最快的。

Ⅰ.正则法

代码：

/**
 * @param {number} n
 * @return {string}
 */
var countAndSay = function(n) {
    const map = {
        1:"1",
		2:"11",
		3:"21",
		4:"1211",
		5:"111221",
		6:"312211",
		7:"13112221",
		8:"1113213211",
		9:"31131211131221",
		10:"13211311123113112211",
		11:"11131221133112132113212221",
		12:"3113112221232112111312211312113211",
		13:"1321132132111213122112311311222113111221131221",
		14:"11131221131211131231121113112221121321132132211331222113112211",
		15:"311311222113111231131112132112311321322112111312211312111322212311322113212221",
		16:"132113213221133112132113311211131221121321131211132221123113112221131112311332111213211322211312113211",
		17:"11131221131211132221232112111312212321123113112221121113122113111231133221121321132132211331121321231231121113122113322113111221131221",
		18:"31131122211311123113321112131221123113112211121312211213211321322112311311222113311213212322211211131221131211132221232112111312111213111213211231131122212322211331222113112211",
		19:"1321132132211331121321231231121113112221121321132122311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112111331121113122112132113213211121332212311322113212221",
		20:"11131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113123112112322111213211322211312113211",
		21:"311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122211311122122111312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221131112311311121321122112132231121113122113322113111221131221",
		22:"132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113213221133122112231131122211211131221131112311332211211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211",
		23:"111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121113222123112221221321132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221",
		24:"3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113321112131221123113112211121312211213211321222113222112132113223113112221121113122113121113123112112322111213211322211312113211",
		25:"132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132132211231232112311321322112311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312111312212231131122211311123113322112111312211312111322111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113213221132213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121132211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321231231121113112221121321132122311211131122211211131221131211322113322112111312211322132113213221123113112221131112311311121321122112132231121113122113322113111221131221",
		26:"1113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123211211131211121311121321123113111231131122112213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122113221122112133221121113122113121113222123211211131211121311121321123113213221121113122113121113222113221113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211",
		27:"31131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321322123211211131211121332211231131122211311122122111312211213211312111322211231131122211311123113322112111331121113112221121113122113111231133221121113122113121113222123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221123113112221131112311332111213122112311311123112111331121113122112132113311213211321222122111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112132113213221133112132123123112111311222112132113311213211231232112311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122211311123113322113223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331221122311311222112111312211311123113322112132113213221133122211332111213112221133211322112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122211331121321232221121113122113121122132112311321322112111312211312111322211213111213122112132113121113222112132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212311222122132113213221123113112221133112132123222112111312211312111322212321121113121112133221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213212312311211131122211213211331121321122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311222113111221221113122112132113121113222112132113213221133122211332111213322112132113213221132231131122211311123113322112111312211312111322212321121113122123211231131122113221123113221113122112132113213211121332212311322113212221",
		28:"13211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221232112111312211312113211223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321322113311213212322211322132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212311222122132113213221123113112221133112132123222112111312211312111322212311322123123112111321322123122113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132132211331221122311311222112111312211311123113322112111312211312111322212311322123123112112322211211131221131211132221132213211321322113311213212322211231131122211311123113321112131221123113112211121312211213211321222113222112132113223113112221121113122113121113123112112322111213211322211312113211",
		29:"11131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211132221121311121312211213211312111322211213211321322113311213212322211231131122211311123113223112111311222112132113311213211221121332211211131221131211132221231122212213211321322112311311222113311213212322211211131221131211132221232112111312111213322112131112131221121321131211132221121321132132212321121113121112133221121321132132211331121321231231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122112131112131221121321132132211231131122111213122112311311222113111221131221221321132132211331121321231231121113112221121321133112132112211213322112311311222113111231133211121312211231131122211322311311222112111312211311123113322112132113212231121113112221121321132122211322212221121123222112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311222112111331121113112221121113122113121113222112132113213221232112111312111213322112311311222113111221221113122112132113121113222112311311222113111221132221231221132221222112112322211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312111322212321121113121112133221132211131221131211132221232112111312111213322112132113213221133112132113221321123113213221121113122123211211131221222112112322211231131122211311123113321112132132112211131221131211132221121321132132212321121113121112133221123113112221131112311332111213211322111213111213211231131211132211121311222113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331121321232221123123211231132132211231131122211331121321232221123113112221131112311332111213122112311311123112112322211211131221131211132221232112111312211322111312211213211312111322211231131122111213122112311311221132211221121332211213211321322113311213212312311211131211131221223113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112211213322112312321123113213221123113112221133112132123222112311311222113111231132231121113112221121321133112132112211213322112311311222113111231133211121312211231131112311211133112111312211213211312111322211231131122111213122112311311221132211221121332211211131221131211132221232112111312111213111213211231132132211211131221232112111312211213111213122112132113213221123113112221133112132123222112111312211312111322212311222122132113213221123113112221133112132123222112311311222113111231133211121321132211121311121321122112133221123113112221131112311332211322111312211312111322212321121113121112133221121321132132211331121321231231121113112221121321132122311211131122211211131221131211322113322112111312211322132113213221123113112221131112311311121321122112132231121113122113322113111221131221",
		30:"3113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112212211131221121321131211132221123113112221131112311332211211133112111311222112111312211311123113322112111312211312111322212321121113121112133221121321132132211331121321132213211231132132211211131221232112111312212221121123222112311311222113111231133211121321321122111312211312111322211213211321322123211211131211121332211231131122211311123113321112131221123113111231121123222112111331121113112221121113122113111231133221121113122113121113221112131221123113111231121123222112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211231131122211311123113321112131221123113111231121113311211131221121321131211132221123113112211121312211231131122211211133112111311222112111312211312111322211213211321223112111311222112132113213221133122211311221122111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321132132211322132113213221123113112221133112132123222112111312211312112213211231132132211211131221131211322113321132211221121332211213211321322113311213212312311211131122211213211331121321123123211231131122211211131221131112311332211213211321223112111311222112132113213221123123211231132132211231131122211311123113322112111312211312111322111213122112311311123112112322211213211321322113312211223113112221121113122113111231133221121321132132211331222113321112131122211332113221122112133221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213122112311311123112112322211322311311222113111231133211121312211231131112311211232221121113122113121113222123211211131221132211131221121321131211132221123113112211121312211231131122113221122112133221121321132132211331121321231231121113121113122122311311222113111231133221121113122113121113221112131221123113111231121123222112132113213221133112132123123112111312211322311211133112111312211213211311123113223112111321322123122113222122211211232221121113122113121113222123211211131211121311121321123113213221121113122123211211131221121311121312211213211321322112311311222113311213212322211211131221131211221321123113213221121113122113121113222112131112131221121321131211132221121321132132211331121321232221123113112221131112311322311211131122211213211331121321122112133221121113122113121113222123112221221321132132211231131122211331121321232221121113122113121113222123211211131211121332211213111213122112132113121113222112132113213221232112111312111213322112132113213221133112132123123112111311222112132113311213211221121332211231131122211311123113321112131221123113112221132231131122211211131221131112311332211213211321223112111311222112132113212221132221222112112322211211131221131211132221232112111312111213111213211231131112311311221122132113213221133112132123222112311311222113111231132231121113112221121321133112132112211213322112111312211312111322212321121113121112131112132112311321322112111312212321121113122122211211232221121311121312211213211312111322211213211321322123211211131211121332211213211321322113311213211322132112311321322112111312212321121113122122211211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113111231133221121321132122311211131122211213211321222113222122211211232221123113112221131112311332111213122112311311123112111331121113122112132113121113222112311311221112131221123113112221121113311211131122211211131221131211132221121321132132212321121113121112133221123113112221131112311332111213213211221113122113121113222112132113213221232112111312111213322112132113213221133112132123123112111312211322311211133112111312212221121123222112132113213221133112132123222113223113112221131112311332111213122112311311123112112322211211131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112211322212322211231131122211322111312211312111322211213211321322113311213211331121113122122211211132213211231131122212322211331222113112211"
    }

    return map[n]
};

结果：

18/18 cases passed (56 ms)
Your runtime beats 98.81 % of javascript submissions
Your memory usage beats 98.5 % of javascript submissions (33.5 MB)
时间复杂度 O(1)

思考总结

总体而言，这道题用正则去解答十分简单，考验的点在正则的匹配这块；当然递归或者遍历也是常规思路；字典法纯属一乐。推荐使用正则来解答此题。

53.最大子序和

题目地址

题目描述

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

题目分析设想

这道题首先基本解法肯定是暴力的遍历求解，直接遍历找出最大区间。当然这里我们也可以使用动态规划来思考问题，列出动态和转移方程式，等于求解 Max(d[0, i])。另外进阶里面提示分治法，分治法在之前有用过，我们也可以做为一个方向。所以大概有三种：

遍历求解，直接遍历算出各区间值
动态规划问题，求解动态问题，找到每个动态区间的最大值
分治，不断二分找区间内的最大子序和

注意一下，只要是寻找最大值最小值的，初始值需要定义为理论上的最大最小值。

编写代码验证

Ⅰ.遍历求解

代码：

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let res = Number.MIN_SAFE_INTEGER
    for(let i = 0; i < nums.length; i++) {
        let sum = 0
        // 分别算出 i 开始的最大子序和
        for(let j = i; j < nums.length; j++) {
            sum += nums[j];
            res = Math.max(res, sum)
        }
    }
    return res
};

结果：

202/202 cases passed (272 ms)
Your runtime beats 7.61 % of javascript submissions
Your memory usage beats 41.88 % of javascript submissions (35.1 MB)
时间复杂度 O(n^2)

Ⅱ.动态规划

代码：

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let res = dp = nums[0] // 初始值
    for(let i = 1; i < nums.length; i++) {
        dp = Math.max(dp + nums[i], nums[i]) // 动态取得最大值
        res = Math.max(res, dp)
    }
    return res
};

结果：

202/202 cases passed (68 ms)
Your runtime beats 90.14 % of javascript submissions
Your memory usage beats 45 % of javascript submissions (35.1 MB)
时间复杂度 O(n)

Ⅲ.分治

代码：

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    // 不断分治
    function countByDichotomy (start, end) {
        // 存储左侧结果，右侧结果，两者更大值，以及两者相加的值
        // 解释一下：最大子序列在左右两区间内要么过界要么不过界。
        // 如果不过界，则最大值为 Max(left, right)
        // 如果过界，则最大为左区间到中间的最大值加中间到右区间的最大值
        if (end === start) { // 数组就一项
            return {
                lmax: nums[start], // 左半区间包含其右端点的最大子序和
                rmax: nums[start], // 右半区间包含其左端点的最大子序和
                sum: nums[start], // 总和
                result: nums[start] // 区域内部的最大子序和
            }
        } else {
            const mid = (start + end) >>> 1 // 这个取中位数写法之前解释过，避免溢出
            const left = countByDichotomy(start, mid) // 左区间中计算结果
            const right = countByDichotomy(mid + 1, end) // 右区间中计算结果
            return {
                lmax: Math.max(left.lmax, left.sum + right.lmax),
                rmax: Math.max(right.rmax, left.rmax + right.sum),
                sum: left.sum + right.sum,
                result: Math.max(left.rmax + right.lmax, Math.max(left.result, right.result))
            }
        }
    }
    return countByDichotomy(0, nums.length - 1).result;
};

结果：

202/202 cases passed (60 ms)
Your runtime beats 97.89 % of javascript submissions
Your memory usage beats 5.01 % of javascript submissions (36.7 MB)
时间复杂度 O(n)

查阅他人解法

查阅题解的过程中发现了以下几种有意思的思路：

动态规划，使用增益的思路。其实上面我们写的动态规划是一样的
贪心法，尝试多加一位，取较大值
分治中使用贪心法求区间

Ⅰ.动态规划

代码：

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let res = nums[0]
    let sum = nums[0] // 增益
    for(let i = 1; i < nums.length; i++) {
        if (sum > 0) { // 正向增益， sum 保留并加上当前遍历数字
            sum += nums[i]
        } else { // sum 更新为当前遍历数字
            sum = nums[i]
        }
        res = Math.max(res, sum)
    }
    return res
};

结果：

202/202 cases passed (60 ms)
Your runtime beats 97.89 % of javascript submissions
Your memory usage beats 47.5 % of javascript submissions (35.1 MB)
时间复杂度 O(n)

Ⅱ.贪心法

代码：

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    let res = Number.MIN_SAFE_INTEGER // 初始值
    let sum = 0
    for(let i = 0; i < nums.length; i++) {
        sum += nums[i]
        res = Math.max(res, sum)
        if (sum < 0) { // 重新开始找子序串
            sum = 0;
        }
    }
    return res
};

结果：

202/202 cases passed (68 ms)
Your runtime beats 90.14 % of javascript submissions
Your memory usage beats 45 % of javascript submissions (35.1 MB)
时间复杂度 O(n)

Ⅲ.分治中使用贪心法求区间

代码：

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSubArray = function(nums) {
    // 获取跨边界的和
    function getMaxCross (start, mid, end) {
        let leftRes = Number.MIN_SAFE_INTEGER
        let leftSum = 0
        for(let i = mid; i >= start; i--) {
            leftSum += nums[i]
            leftRes = Math.max(leftRes, leftSum)
        }

        let rightRes = Number.MIN_SAFE_INTEGER
        let rightSum = 0
        for(let i = mid + 1; i <= end; i++) {
            rightSum += nums[i]
            rightRes = Math.max(rightRes, rightSum)
        }

        return leftRes + rightRes
    }

    function countByDichotomy (start, end) {
        if (start === end) {
            return nums[start]
        } else {
            const mid = (start + end) >>> 1
            const leftSum = countByDichotomy(start, mid)
            const rightSum = countByDichotomy(mid + 1, end)
            const midSum = getMaxCross(start, mid, end)
            // 三者比较最大的就为最大子序和
            return Math.max(leftSum, rightSum, midSum)
        }
    }

    return countByDichotomy(0, nums.length - 1)
};

结果：

202/202 cases passed (72 ms)
Your runtime beats 80.56 % of javascript submissions
Your memory usage beats 49.38 % of javascript submissions (35.1 MB)
时间复杂度 O(nlog(n))

思考总结

个人认为动态规划在这套题里面解题思路清晰，贪心法也可以理解为基于遍历基础上做的延伸，而分治法需要画图加以理解。一般看到这种最大最长的题目，基本上就可以用动态规划问题来尝试作答了。

58.最后一个单词的长度

题目地址

题目描述

给定一个仅包含大小写字母和空格 ' ' 的字符串，返回其最后一个单词的长度。

如果不存在最后一个单词，请返回 0 。

说明：一个单词是指由字母组成，但不包含任何空格的字符串。

示例：

输入: "Hello World"
输出: 5

题目分析设想

这道题看上去像是一道字符串题，我们可以从以下几个方面来尝试作答：

遍历，从末尾开始，效率高
lastIndexOf，直接找空格
正则
split

编写代码验证

Ⅰ.遍历

代码：

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLastWord = function(s) {
    if(!s.length) return 0
    let i = s.length - 1
    while(i >= 0 && s.charAt(i) === ' ') {
        i--
    }
    if(i < 0) return 0 // 全是空格

    let j = i
    while(j >= 0 && s.charAt(j) != ' ') {
        j--
    }
    return i - j
};

结果：

59/59 cases passed (64 ms)
Your runtime beats 81.14 % of javascript submissions
Your memory usage beats 29.72 % of javascript submissions (33.8 MB)
时间复杂度 O(n)

Ⅱ.lastIndexOf

代码：

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLastWord = function(s) {
    if(!s.length) return 0
    s = s.trim()
    const idx = s.lastIndexOf(' ')
    return idx === -1 ? s.length : s.length - 1 - idx
};

结果：

59/59 cases passed (48 ms)
Your runtime beats 99.48 % of javascript submissions
Your memory usage beats 36.52 % of javascript submissions (33.7 MB)
时间复杂度 O(1)

Ⅲ.正则

代码：

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLastWord = function(s) {
    if(!s.length) return 0
    const match = s.match(/([a-zA-Z]+)\s*$/)
    let res = 0
    if (match) {
        res = match.pop()
        return res.length
    }
    return res
};

结果：

59/59 cases passed (80 ms)
Your runtime beats 26.65 % of javascript submissions
Your memory usage beats 5.95 % of javascript submissions (34.2 MB)
时间复杂度 O(1)

Ⅳ.split

代码：

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLastWord = function(s) {
    if(!s.length) return 0
    s = s.trim()
    const arr = s.split(' ')
    if (arr.length) {
        let str = arr.pop()
        return str.length
    } else {
        return 0
    }
};

结果：

59/59 cases passed (60 ms)
Your runtime beats 90.57 % of javascript submissions
Your memory usage beats 13.8 % of javascript submissions (34 MB)
时间复杂度 O(1)

查阅他人解法

没有在题解中看到什么特别的解法，大部分都是基于类库解的，比如 Javascript 中 String 和 Array 的方法。或者是遍历实现的。

思考总结

直到现在也没有弄明白这道题的考察点在哪里？不过我建议感兴趣的同学，可以自己拓展实现 lastIndexOf ，参考上一期 28题的数十种解法，应该能有不小收获。

66.加一

题目地址

题目描述

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位，数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例：

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

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

题目分析设想

这道题我有两个大方向，一是数组遍历进行求解，另外一种是数组转数字再处理。但是转数字可能会溢出，所以就只想到从遍历的角度来作答。

遍历，从后往前遍历找到不为9的项，后面填0就可以了

编写代码验证

Ⅰ.遍历

代码：

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    for(let i = digits.length - 1; i >= 0; i--) {
        // 找不到不为9的数，直接加1输出就可以了
        if(digits[i] !== 9) {
            digits[i]++
            return digits
        } else {
            digits[i] = 0
        }
    }
    digits.unshift(1)
    return digits
};

结果：

109/109 cases passed (60 ms)
Your runtime beats 93.72 % of javascript submissions
Your memory usage beats 26.35 % of javascript submissions (33.8 MB)
时间复杂度 O(n)

查阅他人解法

发现思路基本都是遍历，但是具体实现会有些差距，这里只列举一个最简单的。

Ⅰ.遍历

代码：

/**
 * @param {number[]} digits
 * @return {number[]}
 */
var plusOne = function(digits) {
    for(let i = digits.length - 1; i >= 0; i--) {
        digits[i]++
        // 取10的余数，做了赋值操作，为0就继续进位
        digits[i] %= 10
        if(digits[i] !== 0) {
            return digits
        }
    }
    digits.unshift(1)
    return digits
};

结果：

109/109 cases passed (64 ms)
Your runtime beats 85.29 % of javascript submissions
Your memory usage beats 94.34 % of javascript submissions (33.4 MB)
时间复杂度 O(n)

思考总结

这道题可能大众的想法会转成数字再处理，但是做数字运算的时候，千万要记住考虑溢出的问题。另外因为是加1，所以倒序遍历就可以了。至于是判断末位为9还是对10取余，我觉得都是一个很好理解的思路，也避免了代码的繁琐。

（完）

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

The text was updated successfully, but these errors were encountered:

ChenJiaH added the leetcode leetcode做题学算法 label Nov 13, 2019

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

【Leetcode 做题学算法周刊】第三期 #46

【Leetcode 做题学算法周刊】第三期 #46

ChenJiaH commented Nov 13, 2019

【Leetcode 做题学算法周刊】第三期 #46

【Leetcode 做题学算法周刊】第三期 #46

Comments

ChenJiaH commented Nov 13, 2019

背景

目录

Easy

35.搜索插入位置

题目描述

题目分析设想

编写代码验证

查阅他人解法

思考总结

38.报数

题目描述

题目分析设想

编写代码验证

查阅他人解法

思考总结

53.最大子序和

题目描述

题目分析设想

编写代码验证

查阅他人解法

思考总结

58.最后一个单词的长度

题目描述

题目分析设想

编写代码验证

查阅他人解法

思考总结

66.加一

题目描述

题目分析设想

编写代码验证

查阅他人解法

思考总结