/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
if (s === '') return true;
if (s.length % 2) return false;
// hash 表做好索引
const hash = {
'(': ')',
'[': ']',
'{': '}'
}
let arr = []
for (let i = 0; i < s.length; i++) {
if (!hash[s.charAt(i)]) { // 推入的是右括号
if (!arr.length || hash[arr[arr.length - 1]] !== s.charAt(i)) {
return false
} else {
arr.pop()
}
} else {
if (arr.length >= s / 2) { // 长度超过一半
return false
}
arr.push(s.charAt(i))
}
}
return !arr.length
};
结果:
76/76 cases passed (64 ms)
Your runtime beats 90.67 % of javascript submissions
Your memory usage beats 64.59 % of javascript submissions (33.8 MB)
时间复杂度: O(n)
查阅他人解法
发现一个很暴力的解法,虽然效率不高,但是思路清奇。我们来看看实现:
Ⅰ.暴力正则
代码:
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
if (s === '') return true;
if (s.length % 2) return false;
while(s.length) {
const s_ = s
s = s.replace('()','').replace('[]','').replace('{}','')
if (s === s_) return false;
}
return true;
};
结果:
76/76 cases passed (104 ms)
Your runtime beats 14.95 % of javascript submissions
Your memory usage beats 19.75 % of javascript submissions (35.7 MB)
// nums 是以“引用”方式传递的。也就是说,不对实参做任何拷贝
int len = removeDuplicates(nums);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
// nums 是以“引用”方式传递的。也就是说,不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
题目分析设想
这题跟上一题非常相似,所以我们可以沿用上题的方向来解这道题:
删除数组元素
双指针法
编写代码验证
Ⅰ.删除数组元素
代码:
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function(nums, val) {
if (nums.length === 0) return 0;
for(let i = 0; i < nums.length;) {
if (nums[i] === val) {
nums.splice(i, 1)
} else {
i++
}
}
};
结果:
113/113 cases passed (64 ms)
Your runtime beats 89.43 % of javascript submissions
Your memory usage beats 47.42 % of javascript submissions (33.7 MB)
时间复杂度 O(n)
Ⅱ.双指针法
代码:
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function(nums, val) {
if (nums.length === 0) return 0;
let i = 0
for(let j = 0; j < nums.length; j++) {
if (nums[j] !== val) {
nums[i++] = nums[j]
}
}
return i
};
结果:
113/113 cases passed (60 ms)
Your runtime beats 95.11 % of javascript submissions
Your memory usage beats 98.18 % of javascript submissions (33.3 MB)
时间复杂度 O(n)
查阅他人解法
看到两个略有差异的方法:
单指针法,使用 const of 替换一次遍历,只是写法区别,没有本质提升
交换移除,相同时候与最后一项交换,同时数组长度减1
Ⅰ.单指针法
代码:
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function(nums, val) {
if (nums.length === 0) return 0;
let i = 0;
for(const num of nums) {
if(num !== val) {
nums[i++] = num;
}
}
return i;
};
结果:
113/113 cases passed (68 ms)
Your runtime beats 80.29 % of javascript submissions
Your memory usage beats 43.35 % of javascript submissions (33.7 MB)
时间复杂度 O(n)
Ⅱ.交换移除
代码:
/**
* @param {number[]} nums
* @param {number} val
* @return {number}
*/
var removeElement = function(nums, val) {
if (nums.length === 0) return 0;
let i = nums.length;
for(let j = 0; j < i;) {
if (nums[j] === val) {
nums[j] = nums[--i]
} else {
j++
}
}
return i;
};
结果:
113/113 cases passed (68 ms)
Your runtime beats 80.29 % of javascript submissions
Your memory usage beats 44.53 % of javascript submissions (33.7 MB)
背景
本文记录刷题过程中的整个思考过程,以供参考。主要内容涵盖:
目录
Easy
20.有效的括号
题目地址
题目描述
给定一个只包括
'(',')','{','}','[',']'
的字符串,判断字符串是否有效。有效字符串需满足:
注意空字符串可被认为是有效字符串。
示例:
题目分析设想
这道题从题面来看,仍然需要对字符串做遍历处理,找到相互匹配的括号,剔除后继续做处理即可。所以这道题我的解题想法是:
有几点需要注意下,可以减少一些计算量:
编写代码验证
Ⅰ.记录栈
代码:
结果:
O(n)
查阅他人解法
发现一个很暴力的解法,虽然效率不高,但是思路清奇。我们来看看实现:
Ⅰ.暴力正则
代码:
结果:
O(n)
思考总结
就这题而言,我还是更倾向于增加一个辅助栈来做记录。因为一旦去掉只包含括号的限制,那么正则将无法解答。
21.合并两个有序链表
题目地址
题目描述
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
题目分析设想
这道题从题面上就说明了这是一道链表相关问题,要进行链表合并,无非是修改链表指针指向,或者是链表拼接。所以,这道题我有两种思路的解法:
两种方式的区别很明显,修改指针的方式需要存储和不断修改指针指向,拼接的方式直接做链表拼接。
当然这里也有一些特殊值需要考虑进来。
编写代码验证
Ⅰ.修改指针
代码:
结果:
O(m + n)
,分别代表两个链表长度Ⅱ.链表拼接
代码:
结果:
O(m + n)
,分别代表两个链表长度查阅他人解法
思路基本上都是这两种,未发现方向不同的解法。
无非是有些解法额外开辟了新的链表来记录,或者一些细节上的差异。
思考总结
这里的链表拼接解法,有没有发现跟 上一期 14题中的分治思路是一样的?对,实际上这个也是分治思路的一个应用。
26.删除排序数组中的重复项
题目地址
题目描述
给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例:
说明:
为什么返回数值是整数,但输出的答案是数组呢?
请注意,输入数组是以“引用”方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
题目分析设想
如果是单纯的数组去重,那有很多种方法可以做。所以题目也加了限制条件,总结一下比较重要的几点:
O(1)
这意味着不允许使用新的数组来解题,也就是对原数组进行操作。最后一点注意点可以看出,数组项的拷贝复制是一个方向,第二点可以看出数组删除是一个方向。删除元素的话就不会超过,所以不需要考虑两者结合。所以这题我分两个方向来解:
编写代码验证
Ⅰ.拷贝数组元素
代码:
结果:
O(n)
Ⅱ.删除数组元素
代码:
结果:
O(n)
查阅他人解法
这里看见一种很巧妙的解法,双指针法。相当于一个用于计数,一个用于扫描。
Ⅰ.双指针法
代码:
结果:
O(n)
思考总结
就三种解法而言,删除数组元素会频繁修改数组,不建议使用。双指针法和拷贝数组元素代码逻辑相似,但是思路上是截然不同的。
27.移除元素
题目地址
题目描述
给定一个数组
nums
和一个值val
,你需要原地移除所有数值等于val
的元素,返回移除后数组的新长度。不要使用额外的数组空间,你必须在原地修改输入数组并在使用
O(1)
额外空间的条件下完成。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例:
说明:
为什么返回数值是整数,但输出的答案是数组呢?
请注意,输入数组是以“引用”方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
题目分析设想
这题跟上一题非常相似,所以我们可以沿用上题的方向来解这道题:
编写代码验证
Ⅰ.删除数组元素
代码:
结果:
O(n)
Ⅱ.双指针法
代码:
结果:
O(n)
查阅他人解法
看到两个略有差异的方法:
const of
替换一次遍历,只是写法区别,没有本质提升Ⅰ.单指针法
代码:
结果:
O(n)
Ⅱ.交换移除
代码:
结果:
O(n)
思考总结
这里开拓下思路:如果要移除的是多项,那么还是使用指针法做处理合适;如果是移除单项,那么使用交互移除法其实遍历次数最少。
28.实现strStr
题目地址
题目描述
实现
strStr()
函数。给定一个
haystack
字符串和一个needle
字符串,在haystack
字符串中找出needle
字符串出现的第一个位置 (从0开始)。如果不存在,则返回-1
。示例:
说明:
当
needle
是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。对于本题而言,当
needle
是空字符串时我们应当返回0
。这与C
语言的strstr()
以及Java
的indexOf()
定义相符。题目分析设想
这道题很明显是一道字符串搜索的题目,估计是在考察算法,但是受限知识面,所以我就先以现有方式实现作答,再来学习算法了。
IndexOf
这个是原生方法,考察这个就没有意义了,所以不做详细论述IndexOf
编写代码验证
Ⅰ.遍历匹配
代码:
结果:
O(n)
查阅他人解法
首先查阅《算法导论》,看到字符串匹配有以下四种:
然后再看题解,大概还找到以下三种算法:
Ⅰ.朴素字符串匹配算法
算法说明:
通过一个循环找到所有有效偏移,该循环对
n-m+1
个可能的s
值进行检测,看能否满足条件P[1..m] = T[s+1...s+m]
。其中n
是字符串长度, 'm' 是匹配字符串长度。代码:
结果:
O((n-m + 1) * m)
Ⅱ.Rabin-Karp 算法
算法说明:
进行哈希运算,将字符串转成对应的哈希值进行比对,类似16进制。这里题目是字符串,我就用
ASCII
值来表示每个字符的哈希值,那么就可以计算出模式串的哈希值,再进行滚动比较。每次滚动只需要做固定的
-*+
三个操作,即可得出滚动串的哈希值了。比如计算
bbc
,哈希值为hash = (b.charCodeAt() * 128 ^ 2 + b.charCodeAt() * 128 + c.charCodeAt())
,如果要计算后新值bca
则为(hash - b.charCodeAt() * 128 ^ 2) * 128 + c.charCodeAt()
。代码:
结果:
O(m + n)
Ⅲ.利用有限自动机进行字符串匹配
算法说明:
通过对文本字符串
T
进行扫描,找出模式P
的所有出现位置。它们只对每个文本字符检查一次,并且检查每个文本字符时所用的时间为常数。一句话概括:字符输入引起状态机状态变更,通过状态转换图得到预期结果。这里主要的核心点是判断每次输入,找到最长的后缀匹配,如果最长时的长度等于查找字符串长度,那就一定包含该查找字符串。
代码:
结果:
O(n)
Ⅳ.KMP 算法
算法说明:
可以理解为在状态机的基础上,使用了一个前缀函数来进行状态判断。本质上也是前缀后缀的思想。
代码:
结果:
O(n)
Ⅴ.BM 算法
算法说明:
基于后缀匹配,匹配从后开始,但移动还是从前开始,只是定义了两个规则:坏字符规则和好后缀规则。
通俗来讲就是先验证是否为坏字符,然后判断是否在搜索词中进行对应的偏移进行下一步验证。如果匹配的话就从后往前校验,如果仍然匹配,就为好后缀。核心思想是每次位移都在坏字符和好后缀规则中取较大值,由于两个规则都只与匹配项相关,所以可以提前生成规则表。
代码:
结果:
O(n)
Ⅵ.Horspool 算法
算法说明:
将主串中匹配窗口的最后一个字符跟模式串中的最后一个字符比较。如果相等,继续从后向前对主串和模式串进行比较,直到完全相等或者在某个字符处不匹配为止。如果不匹配,则根据主串匹配窗口中的最后一个字符在模式串中的下一个出现位置将窗口向右移动。
代码:
结果:
O(n)
Ⅶ.Sunday 算法
算法说明:
它的思想跟
BM 算法
相似,但是它是从前往后匹配,匹配失败时关注主串内参与匹配的后一位字符。如果该字符不存在匹配字符中,则多偏移一位;如果存在,则偏移匹配串长度减该字符最右出现的位置。代码:
结果:
O(n)
思考总结
就理解的难易度来讲,我建议先看
Sunday 算法
和Horspool 算法
,不过RMP 算法
的匹配思路打开了眼界,利用后缀前缀来处理问题。这里把常见的字符串算法都做了一次尝试,整体下来收获颇丰。(完)