算法进阶
题目
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| 第350题：两个数组的交集
给定两个数组，编写一个函数来计算它们的交集。
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
|
废话不多说，直接上最优解！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| const nums1 = [1,2,2,1, 2,2,2,2];
const nums2 = [2,2, 2, 1, 1, 1];
const queryOmit = (nums1, nums2) => {
nums1 = nums1.sort((a, b) => a-b)
nums2 = nums2.sort((a, b) => a-b)
let point1 = 0, point2 = 0;
const res = []
for (let i = 0; i < nums1.length > nums2.length ? nums1.length : nums2.length; i ++) {
if (nums1[point1] === nums2[point2]) {
res.push(nums1[point1]);
point1++;
point2++;
} else {
if (nums1[point1] > nums2[point2]) {
point2++;
} else {
point1++;
}
}
if (point1 === nums1.length || point2 === nums2.length) {
break;
}
}
return res;
}
console.log(queryOmit(nums1, nums2));
|
正则玩法
权威参考
前瞻后瞩
?=前瞻，就是匹配xxx之前的串，?<=后瞩，就是匹配xxx之后的串。
example，这里只展示前瞻，后瞩暂不做演示
1
| 给定字符串'你好，李焕英！'，匹配'！'之前的字符串；
|
we can do as follow!
1
2
3
| const str = '你好，李焕英！'
console.log(str.match(/.*(?=！)/))
|
1
2
3
| // printf
[ '你好，李焕英', index: 0, input: '你好，李焕英！', groups: undefined ]
|
分组匹配
以一道题目入门分组匹配（题目来源于：热心网友 单女士）：
1
| 题目：[1,2,2,2,3,1,4] 变成 1，222，3，1，4
|
乍一看，肯定有小可爱想上去就是一梭子遍历了吧！
1
2
3
4
|
const arr = [1, 2, 2, 2, 3, 1, 4];
console.log(arr.join('').match(/(\d)\1*/g))
|
1
2
3
| // printf
[ '1', '222', '3', '1', '4' ]
|
perfect，完美解决！
另外一种解法，来源于圈圈的朋友；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| function sameItem (arr) {
if (!arr) return arr
let i = 0
let j = 1
let item = arr[i]
const res = []
while(j < arr.length) {
if (arr[j] === arr[i]) {
item = item + arr[i] * Math.pow(10, (j - i))
j++
} else {
res.push(item)
i = j
item = arr[i]
j ++
}
}
res.push(item)
return res
}
|
时间复杂度T(n)，空间复杂度O(2n + 1)
零宽断言
权威参考
一听这么高大上的名字，肯定被吓到了吧！其实零宽断言就是所谓的前瞻.
以一道题目开始（来源：单女士）：
1
2
3
| // const arr = [1,2,3, 1,2,3,4,6, 4, 5, 6,7,8]
// 输出： ["1-3", "1-4", "6", "4-8"]
|
看到这个题目，我的第一直觉是，零宽断言可以实现！
直接上代码:
1
2
3
| const a = '1235679'
console.log(a.match(/(0(?=1)|1(?=2)|2(?=3)|3(?=4)|4(?=5)|5(?=6)|6(?=7)|7(?=8)|8(?=9))*\d/g))
|
1
2
3
4
| // printf
[ '123', '567', '9' ]
|
简明扼要的叙述下上述正则：
?=就不说了吧，上文有介绍(0(?=1)|1(?=2)|2(?=3)|3(?=4)|4(?=5)|5(?=6)|6(?=7)|7(?=8)|8(?=9))*，匹配0-9的任意连续数字，并以此为一个组，匹配0次或多次，其实换+也ok。\d的效果，就是约束匹配组后面的东西，说到这里你可能不太理解，继续往下看！
1
2
3
4
|
const a = '123sssss5679zsss'
console.log(a.match(/(0(?=1)|1(?=2)|2(?=3)|3(?=4)|4(?=5)|5(?=6)|6(?=7)|7(?=8)|8(?=9))*./g))
|
1
2
3
4
5
6
7
| [
'123', 's', 's',
's', 's', 's',
'567', '9', 'z',
's', 's', 's'
]
|
然后再对比加了数字约束的消效果，其实就是每次匹配到子串之后的串的格式约束。
最后：
清风明月，几分轻狂几分傲，我也想拥有自己的一人之下！
莫念语，清，夙命！
狂。
