每日一记之21413

每日一记之21413

四月 12, 2021 本文共计: 908 字 预计阅读时长: 4分钟

算法进阶

题目

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'
]

然后再对比加了数字约束的消效果,其实就是每次匹配到子串之后的串的格式约束。

最后:

清风明月,几分轻狂几分傲,我也想拥有自己的一人之下!

莫念语,清,夙命!

狂。