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)
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)
背景
本文记录刷题过程中的整个思考过程,以供参考。主要内容涵盖:
目录
Easy
35.搜索插入位置
题目地址
题目描述
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例:
题目分析设想
这道题目有点明显,题干说明了是排序数组,重点是排序数组,所以很明显的第一反应会使用二分法来解题。同时可以注意一下,数组中无重复元素。所以这道题我就按两个方案来作答:
编写代码验证
Ⅰ.暴力法
代码:
结果:
O(n)
Ⅱ.二分法
代码:
结果:
O(log2(n))
查阅他人解法
基本上这道题就是针对二分法进行考察的,所以没有看到其他特别的解法。
思考总结
看见排序数组,查找下标,那么就可以果断选择二分法啦。
38.报数
题目地址
题目描述
报数序列是一个整数序列,按照其中的整数的顺序进行报数,得到下一个数。其前五项如下:
1
被读作"one 1"
("一个一"
),即11
。11
被读作"two 1s"
("两个一"
),即21
。21
被读作"one 2"
,"one 1"
("一个二"
,"一个一"
) , 即1211
。给定一个正整数 n(1 ≤ n ≤ 30),输出报数序列的第 n 项。
注意:整数顺序将表示为一个字符串。
示例:
题目分析设想
这道题目有点绕,其实我们只看右侧项就可以,每次都是读上一次项。报数的规则实际上就是相同连续数字合并后进行每位的报数。最简单的想法是直接使用正则替换就可以了。当然也可以从递归和遍历的方式来作答,我们分别来看看。
长度 + 数字本身
n-1
求解n+1
求解编写代码验证
Ⅰ.正则法
代码:
结果:
O(n)
Ⅱ.递归法
代码:
结果:
O(n^2)
Ⅲ.遍历法
代码:
结果:
O(n^2)
查阅他人解法
这里看到一个开怀一笑的解法,直接字典法,缺点很明显,但是当前情况下确实是最快的。
Ⅰ.正则法
代码:
结果:
O(1)
思考总结
总体而言,这道题用正则去解答十分简单,考验的点在正则的匹配这块;当然递归或者遍历也是常规思路;字典法纯属一乐。推荐使用正则来解答此题。
53.最大子序和
题目地址
题目描述
给定一个整数数组
nums
,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。示例:
进阶:
如果你已经实现复杂度为 O(n) 的解法,尝试使用更为精妙的分治法求解。
题目分析设想
这道题首先基本解法肯定是暴力的遍历求解,直接遍历找出最大区间。当然这里我们也可以使用动态规划来思考问题,列出动态和转移方程式,等于求解
Max(d[0, i])
。另外进阶里面提示分治法,分治法在之前有用过,我们也可以做为一个方向。所以大概有三种:注意一下,只要是寻找最大值最小值的,初始值需要定义为理论上的最大最小值。
编写代码验证
Ⅰ.遍历求解
代码:
结果:
O(n^2)
Ⅱ.动态规划
代码:
结果:
O(n)
Ⅲ.分治
代码:
结果:
O(n)
查阅他人解法
查阅题解的过程中发现了以下几种有意思的思路:
Ⅰ.动态规划
代码:
结果:
O(n)
Ⅱ.贪心法
代码:
结果:
O(n)
Ⅲ.分治中使用贪心法求区间
代码:
结果:
O(nlog(n))
思考总结
个人认为动态规划在这套题里面解题思路清晰,贪心法也可以理解为基于遍历基础上做的延伸,而分治法需要画图加以理解。一般看到这种最大最长的题目,基本上就可以用动态规划问题来尝试作答了。
58.最后一个单词的长度
题目地址
题目描述
给定一个仅包含大小写字母和空格
' '
的字符串,返回其最后一个单词的长度。如果不存在最后一个单词,请返回
0
。说明:一个单词是指由字母组成,但不包含任何空格的字符串。
示例:
题目分析设想
这道题看上去像是一道字符串题,我们可以从以下几个方面来尝试作答:
编写代码验证
Ⅰ.遍历
代码:
结果:
O(n)
Ⅱ.lastIndexOf
代码:
结果:
O(1)
Ⅲ.正则
代码:
结果:
O(1)
Ⅳ.split
代码:
结果:
O(1)
查阅他人解法
没有在题解中看到什么特别的解法,大部分都是基于类库解的,比如
Javascript
中String
和Array
的方法。或者是遍历实现的。思考总结
直到现在也没有弄明白这道题的考察点在哪里?不过我建议感兴趣的同学,可以自己拓展实现
lastIndexOf
,参考 上一期 28题的数十种解法,应该能有不小收获。66.加一
题目地址
题目描述
给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外,这个整数不会以零开头。
示例:
题目分析设想
这道题我有两个大方向,一是数组遍历进行求解,另外一种是数组转数字再处理。但是转数字可能会溢出,所以就只想到从遍历的角度来作答。
编写代码验证
Ⅰ.遍历
代码:
结果:
O(n)
查阅他人解法
发现思路基本都是遍历,但是具体实现会有些差距,这里只列举一个最简单的。
Ⅰ.遍历
代码:
结果:
O(n)
思考总结
这道题可能大众的想法会转成数字再处理,但是做数字运算的时候,千万要记住考虑溢出的问题。另外因为是加1,所以倒序遍历就可以了。至于是判断末位为9还是对10取余,我觉得都是一个很好理解的思路,也避免了代码的繁琐。
(完)