Skip to content

Latest commit

 

History

History
486 lines (326 loc) · 16.4 KB

202101W4.md

File metadata and controls

486 lines (326 loc) · 16.4 KB
Raw

@Author : Lewis Tian ([email protected])

@Link : github.com/taseikyo

@Range : 2021-01-24 - 2021-01-30

Weekly #13

readme | previous | next

本文总字数 6409 个，阅读时长约：12 分 16 秒，统计数据来自：算筹字数统计。

*Photo by Feng Jiaxing on Unsplash

Table of Contents

  • algorithm
    • 找出重复数（腾讯面试题）
  • review
    • 如何在 Go 中使用接口（interface）
  • tip
    • WSL2 通过 Clash 使用 Windows 代理
    • 知道这 20 个正则表达式，能让你少写 1000 行代码
    • Python 正则表达式 特殊符号和字符
  • share
    • 形式主义何时休？

algorithm ⬆

1. 找出重复数（腾讯面试题）

有 2.5 亿个数，其中只有一个数出现两次，其他的数都出现一次。在内存紧张的情况下，怎么找出这个重复数？

我们以前做过简单的类似题目：仅一个不重复，其他均重复，这时直接异或就可以搞定。现在是仅一个重复，其他不重复，异或似乎搞不定。

看下面的讨论，一个较为便捷的方法就是使用位图，对 250000000 取模，得到的数就在 [0, 250000000]，所以需要内存为 $ 250000000/8=31250000B=29.8M $，不到 30M，而且遍历一遍就够了，应该说比较高效。

当然位图有个问题是可能误判，比如 2 和 250000002 取模都是 2，这个时候可以使用布隆过滤器，它也存在误判，但是概率低多了。

有个大佬提出几种解法

Meg：

  • 如果这道题的数字是连续的，那线性时间复杂度，常数空间复杂度的，方法就比较多了，像异或法，和差法，floyd 链表环都行。
  • 如果不是连续的，如果不要求常数空间复杂度的话，考虑到有限空间，可以使用位图法。
  • 如果空间限制到位图都装不下...那就使用小根堆加归并排序进行分批排序，最后再进行遍历吧。
  • 如果连排序都不允许，那只能使用终极杀器，暴力法了。

review ⬆

1. 如何在 Go 中使用接口（interface）

接口是什么？它是一种类型，该类型具有一组方法。

An interface is two things: it is a set of methods, but it is also a type.

Go 中么有 implements 关键字，只要你实现了接口中的方法，就说明满足了该接口，一个类型是否满足一个几口是自动确定的。

// https://play.golang.org/p/yGTd4MtgD5
type Animal interface {
	Speak() string
}

type Dog struct {
}

func (d Dog) Speak() string {
	return "Woof!"
}

type Cat struct {
}

func (c Cat) Speak() string {
	return "Meow!"
}

type Llama struct {
}

func (l Llama) Speak() string {
	return "?????"
}

type JavaProgrammer struct {
}

func (j JavaProgrammer) Speak() string {
	return "Design patterns!"
}

func main() {
	animals := []Animal{Dog{}, Cat{}, Llama{}, JavaProgrammer{}}
	for _, animal := range animals {
		fmt.Println(animal.Speak())
	}
}

上面定义了四种类型的动物，在 main 函数中可以创建一个动物切片（slice），然后调用它们的 Speak 方法。

interface{} 是一个空接口类型，这是很多麻烦的根源，由于它其中没有方法，所以所有类型满足空接口。

所以对于一个形参为 interface{} 的函数，你可以传任何值进去。

func DoSomething(v interface{}) {
   // ...
}

An interface value is constructed of two words of data; one word is used to point to a method table for the value's underlying type, and the other word is used to point to the actual data being held by that value.

接口值由两个字（word）构成：一个字用于指向值类型的方法表，另一个字用于指向实际数据。

下面是一个例子，它们代表了对 interface{} 类型的一个常见误解：

// https://play.golang.org/p/4DuBoi2hJU
func PrintAll(vals []interface{}) {
    for _, val := range vals {
        fmt.Println(val)
    }
}

func main() {
    names := []string{"stanley", "david", "oscar"}
    PrintAll(names)
}
// PrintAll(names): cannot use names (type []string) as type []interface {} in argument to PrintAll

想让它运行，必须将 []string 转换为 []interface {}：

names := []string{"stanley", "david", "oscar"}
vals := make([]interface{}, len(names))
for i, v := range names {
    vals[i] = v
}
PrintAll(vals)

一个有趣的现象：指针类型可以访问其关联值类型的方法，但反之则不行。

* Dog 值可以使用在 Dog 上定义的 Speak 方法，Cat 值不能访问在 * Cat 上定义的 Speak 方法。

Go 中的所有内容都是按值传递的，每次调用一个函数时，传递给它的数据都会被复制，对于具有值接收器的方法，在调用该方法时将复制该值。

Since everything is passed by value, it should be obvious why a *Cat method is not usable by a Cat value; any one Cat value may have any number of *Cat pointers that point to it. If we try to call a *Cat method by using a Cat value, we never had a *Cat pointer to begin with. Conversely, if we have a method on the Dog type, and we have a *Dog pointer, we know exactly which Dog value to use when calling this method, because the *Dog pointer points to exactly one Dog value; the Go runtime will dereference the pointer to its associated Dog value any time it is necessary. That is, given a *Dog value d and a method Speak on the Dog type, we can just say d.Speak(); we don’t need to say something like d->Speak() as we might do in other languages.

既然所有值都是按值传递的，那么为什么 * Cat 方法不能被 Cat 值使用就显而易见了；任何一个 Cat 值都可能有任意数量的 * Cat 指针指向它。如果我们尝试通过使用 Cat 值调用 * Cat 方法，那么我们一开始就没有 * Cat 指针。相反，如果我们有一个 Dog 类型的方法，并且我们有一个 * Dog 指针，我们就能准确地知道在调用这个方法时使用哪个 Dog 值，因为 * Dog 指针正好指向一个 Dog 值。

Go 运行时会在任何必要的时候将指针解引用到它的相关 Dog 值。也就是说，给定一个 * Dog 值 d 和一个方法 Speak，我们可以只说 d.Speak()；而不需要像在其他语言中那样说 d->Speak()

  • create abstractions by considering the functionality that is common between datatypes, instead of the fields that are common between datatypes
  • an interface{} value is not of any type; it is of interface{} type
  • interfaces are two words wide; schematically they look like (type, value)
  • it is better to accept an interface{} value than it is to return an interface{} value
  • a pointer type may call the methods of its associated value type, but not vice versa
  • everything is pass by value, even the receiver of a method
  • an interface value isn’t strictly a pointer or not a pointer, it’s just an interface
  • if you need to completely overwrite a value inside of a method, use the * operator to manually dereference a pointer

tip ⬆

1. WSL2 通过 Clash 使用 Windows 代理

1、Clash for Windows 打开 “Allow LAN” 选项 2、从配置文件中查看端口 3、打开 shell 终端，输入如下命令

export hostip=$(cat /etc/resolv.conf |grep -oP '(?<=nameserver\).*')
export https_proxy="http://${hostip}:7890"
export http_proxy="http://${hostip}:7890"

这里只设置了 https_proxy、http_proxy，没有设置 all_proxy 等，并且也只使用了 http 协议代理，没有设置 sock5 协议代理，可以根据需要自己更改，但是需要注意，本例中 http 协议端口是 7890，而如果要设置 sock5 协议，那么端口需要改为 7891。

4、安装 w3m

sudo apt install w3m

5、用 w3m 进行测试

w3m www.google.com

如果成功，运行完该命令只有会在 shell 中出现如下画面：

6、一劳永逸，可以在 ~/.myrc 添加第 3 步的四条命令。

2. 知道这 20 个正则表达式，能让你少写 1000 行代码

很 UC 的标题，阅读量 256,670，被很多网站 "转载"，我是之前就看到的，一直在想要不要加进来，因为我没验证过，今天索性就全部试一下。

1、校验密码强度

密码的强度必须是包含大小写字母和数字的组合，不能使用特殊字符，长度在 8-10 之间。

^(?=.*\\d)(?=.*[a-z])(?=.*[A-Z]).{8,10}$

import re

pat = re.compile(r"^(?=.*\d)(?=.*[a-z])(?=.*[A-Z]).{8,10}$")
print(pat.match("123Aa"))
# None

print(pat.match("123Aa431"))
# <re.Match object; span=(0, 8), match='123Aa431'>

print(pat.match("123aa431"))
# None

print(pat.match("123a.431"))
# None

?= 见下面 tip#3。

2、校验中文

字符串仅能是中文。

^[\\u4e00-\\u9fa5]{0,}$

pat = re.compile(r"^[\u4e00-\u9fa5]{1,}$")
print(pat.match("123"))
# None

print(pat.match("中文"))
# <re.Match object; span=(0, 2), match='中文'>

print(pat.match("中文123"))
# None

3、由数字、26 个英文字母或下划线组成的字符串

^\\w+$

pat = re.compile(r"^\w+$")

print(pat.match("中文"))
# <re.Match object; span=(0, 2), match='中文'>

print(pat.match("123"))
# <re.Match object; span=(0, 3), match='123'>

print(pat.match("1a"))
# <re.Match object; span=(0, 2), match='1a'>

print(pat.match("1a_"))
# <re.Match object; span=(0, 3), match='1a_'>

print(pat.match("1a_."))
# None

4、校验E-Mail 地址

同密码一样，下面是 E-mail 地址合规性的正则检查语句。

[\\w!#$%&'*+/=?^_`{|}~-]+(?:\\.[\\w!#$%&'*+/=?^_`{|}~-]+)
*@(?:[\\w](?:[\\w-]*[\\w])?\\.)+[\\w](?:[\\w-]*[\\w])?

foo = (r"[\w!#$%&'*+/=?^_`{|}~-]+(?:\.[\w!#$%&'*+/=?^_`{|}~-]+)"
       r"*@(?:[\w](?:[\w-]*[\w])?\.)+[\w](?:[\w-]*[\w])?")
print(foo)
pat = re.compile(foo)

print(pat.match("[email protected]"))
# <re.Match object; span=(0, 11), match='[email protected]'>

print(pat.match("agmail.com"))
# None

5、校验身份证号码

15 位
^[1-9]\\d{7}((0\\d)|(1[0-2]))(([0|1|2]\\d)|3[0-1])\\d{3}$
18 位
^[1-9]\\d{5}[1-9]\\d{3}((0\\d)|(1[0-2]))(([0|1|2]\\d)|3[0-1])\\d{3}([0-9]|X)$

网上随便搜了一个试了下，一方面说明正则匹配是对的，另一方面说明信息泄露。。。

pat = re.compile(r"^[1-9]\d{7}((0\d)|(1[0-2]))(([0|1|2]\d)|3[0-1])\d{3}$")

print(pat.match("410901199709191000"))
# None

pat = re.compile(r"^[1-9]\d{5}[1-9]\d{3}((0\d)|(1[0-2]))(([0|1|2]\d)|3[0-1])\d{3}([0-9]|X)$")

print(pat.match("410901199709191000"))
# <re.Match object; span=(0, 18), match='410901199709191000'>

6、校验日期

"yyyy-mm-dd" 格式的日期校验，已考虑平闰年。

（太长已拆分）

^(?:(?!0000)[0-9]{4}-(?:(?:0[1-9]|1[0-2])-(?:0[1-9]|1[0-9]|2[0-8])|
(?:0[13-9]|1[0-2])-(?:29|30)|(?:0[13578]|1[02])-31)|
(?:[0-9]{2}(?:0[48]|[2468][048]|[13579][26])|
(?:0[48]|[2468][048]|[13579][26])00)-02-29)$

7、校验金额

金额校验，精确到2位小数。

^[0-9]+(.[0-9]{2})?$

8、校验手机号

下面是国内 13、15、18 开头的手机号正则表达式。（可根据目前国内收集号扩展前两位开头号码）

^(13[0-9]|14[5|7]|15[0|1|2|3|5|6|7|8|9]|18[0|1|2|3|5|6|7|8|9])\\d{8}$

9、 判断IE的版本

IE目前还没被完全取代，很多页面还是需要做版本兼容，下面是IE版本检查的表达式。

^.*MSIE [5-8](?:\\.[0-9]+)?(?!.*Trident\\/[5-9]\\.0).*$

10、 校验IP-v4地址

IP4 正则语句。

\\b(?:(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\\.){3}(?:25[0-5]|2[0-4][0-9]|[01]?[0-9][0-9]?)\\b

11、 校验IP-v6地址

IP6 正则语句。

(([0-9a-fA-F]{1,4}:){7,7}[0-9a-fA-F]{1,4}|([0-9a-fA-F]{1,4}:){1,7}:|
([0-9a-fA-F]{1,4}:){1,6}:[0-9a-fA-F]{1,4}|([0-9a-fA-F]{1,4}:){1,5}(:[0-9a-fA-F]{1,4}){1,2}|
([0-9a-fA-F]{1,4}:){1,4}(:[0-9a-fA-F]{1,4}){1,3}|([0-9a-fA-F]{1,4}:){1,3}(:[0-9a-fA-F]{1,4}){1,4}|
([0-9a-fA-F]{1,4}:){1,2}(:[0-9a-fA-F]{1,4}){1,5}|[0-9a-fA-F]{1,4}:((:[0-9a-fA-F]{1,4}){1,6})|:
((:[0-9a-fA-F]{1,4}){1,7}|:)|fe80:(:[0-9a-fA-F]{0,4}){0,4}%[0-9a-zA-Z]{1,}
|::(ffff(:0{1,4}){0,1}:){0,1}((25[0-5]|(2[0-4]|1{0,1}[0-9]){0,1}[0-9])\\.){3,3}
(25[0-5]|(2[0-4]|1{0,1}[0-9]){0,1}[0-9])|([0-9a-fA-F]{1,4}:){1,4}:((25[0-5]|
(2[0-4]|1{0,1}[0-9]){0,1}[0-9])\\.){3,3}(25[0-5]|(2[0-4]|1{0,1}[0-9]){0,1}[0-9]))

12、 检查URL的前缀

应用开发中很多时候需要区分请求是HTTPS还是HTTP，通过下面的表达式可以取出一个url的前缀然后再逻辑判断。

if (!s.match(/^[a-zA-Z]+:\\/\\//)) {
    s = 'http://' + s;
}

13、 提取URL链接

下面的这个表达式可以筛选出一段文本中的URL。

^(f|ht){1}(tp|tps):\\/\\/([\\w-]+\\.)+[\\w-]+(\\/[\\w- ./?%&=]*)?

14、 文件路径及扩展名校验

验证windows下文件路径和扩展名（下面的例子中为.txt文件）

^([a-zA-Z]\\:|\\\\)\\\\([^\\\\]+\\\\)*[^\\/:*?"<>|]+\\.txt(l)?$

15、 提取 Color Hex Codes

有时需要抽取网页中的颜色代码，可以使用下面的表达式。

^#([A-Fa-f0-9]{6}|[A-Fa-f0-9]{3})$

16、 提取网页图片

假若你想提取网页中所有图片信息，可以利用下面的表达式。

\\< *[img][^\\\\>]*[src] *= *[\\"\\']{0,1}([^\\"\\'\\ >]*)

17、 提取页面超链接

提取html中的超链接。

(<a\\s*(?!.*\\brel=)[^>]*)(href="https?:\\/\\/)((?!(?:(?:www\\.)?
'.implode('|(?:www\\.)?', $follow_list).'))[^"]+)"((?!.*\\brel=)[^>]*)(?:[^>]*)>

18、 查找CSS属性

通过下面的表达式，可以搜索到相匹配的CSS属性。

^\\s*[a-zA-Z\\-]+\\s*[:]{1}\\s[a-zA-Z0-9\\s.#]+[;]{1}

19、 抽取注释

如果你需要移除HMTL中的注释，可以使用如下的表达式。

<!--(.*?)-->

20、 匹配 HTML 标签

通过下面的表达式可以匹配出HTML中的标签属性。

<\\/?\\w+((\\s+\\w+(\\s*=\\s*(?:".*?"|'.*?'|[\\^'">\\s]+))?)+\\s*|\\s*)\\/?>

就验证了前面几个，发现确实有效果，姑且认证质量通过吧。

3. Python 正则表达式 特殊符号和字符

算是一个不错的博客，17 年写的，还是用的 python2.7，于是我将其整理为 python3 且保存为 ipynb 格式。

在线预览：GitHub | nbviewer

share ⬆

1. 形式主义何时休？

形式主义由来已久，这两天更是深受其害。

华科为了学生好，决定免费一次核酸检测，但是需要在系统上申请。

官方放假日期是 2020-01-20，学生"想"留校延迟回家得在系统申请；然而官方没通知，本来说是老师发起邀请，学生只需同意即可，结果是学生自己申请，因而时间过了我和一些同学才知晓，系统关闭，申请不了。

本来也没啥影响，也就无法申请进出学校（进出学校需要系统申请临时出校，否则不能出校），反正是最后回家，不出也没啥意义。

结果昨天（1/25）通知说可以免费做核酸检测，但是需要申请，后来听同学说只需要身份证和校园卡就可以了；然后下午去了校医院，结果排在前面的几位同学也是没有申请留校，也没法申请（"没有权限发起申请"），于是问前面负责的医生，结果医生说不能申请不能做，不然去找辅导员签字。

我就服了，本来是学校为了学生出的一个政策，结果非得卡这个申请，检查校园卡和身份证证明我是我，我是华科学生不就完了，非得申请，mdzz。于是去南一楼找辅导员签字，结果到了才发现是周日。。。

晚上辅导员通知，第二天早上写申请找书记签字，找老师盖章。于是今天早上跟几个同学一起去南一楼找书记盖章。

我也是服了，什么时候才能删繁就简，去掉那些无谓的形式呢？

readme | previous | next