算法进阶
题目
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' ]
|
然后再对比加了数字约束的消效果,其实就是每次匹配到子串之后的串的格式约束。

最后:
清风明月,几分轻狂几分傲,我也想拥有自己的一人之下!
莫念语,清,夙命!
狂。