ARTS-2018-11-24

Algorithm

Two Sum

最容易想到的当然是暴力法,双重循环,O(n²)。

换个角度,因为是2个数求和,那么每个数字寻找的匹配对象肯定是固定的,那么我登记下自己的条件,让后面来的人主动来找我就好了,所以一个 O(n) 的思路诞生了:遍历数组元素,每个元素都去 hash map 中找自身 hash 值是否存在,如果存在则对应的 value 就是你找的值,反之则写入要匹配数字的 hash ,value 指向自身。

matchNumIndex, exist := indexMap[num]
if exist {
	{matchNumIndex, index}
} else {
    indexMap[target-num] = index
}

该方法需要一个额外的 hash map 来存储匹配关系。

思路转换有点类似相亲,hash map 对应的就是所谓的“相亲角”。?

Reverse Integer

没什么太大的难度,因为要关心具体的数值,就要注意溢出的问题。

//int32位 [-2147483648,2147483647]
if (result > math.MaxInt32/10 
    || (result == math.MaxInt32/10 && pop > 7)) 
	|| (result < math.MinInt32/10 || (result == math.MinInt32/10 && pop < -8)) {
    return 0
}

如果不局限在数学的话,最简单的方式其实是转换成字符串,然后变成字符串翻转问题:双指针即可解决。

Palindrome Number

这个只用判定是否是回文数接可,因为不用关心具体的数值,比 Reverse Integer 难度更小点,翻转字符串可以解决。

数学方法也可以解决:翻转这个数,然后判定是否和原数相等即可。但是这里会涉及到翻转后溢出的问题,导致无法正常比较,所以同样要注意溢出问题。

回文数的特点的就是“轴对称”,所以前面或者后面一半是否和剩下的一半相等即可,这样就不会遇到溢出问题,效率也能提升一丢丢。

for x > revertedNumber {
    revertedNumber = revertedNumber*10 + x%10
    x = x / 10
}
return x == revertedNumber || x == revertedNumber/10

取数字后面的一半会比较简单,直接模10即可。注意数字长度为奇数时候的处理。

Review

Intro to Congestion Control

TCP 协议的拥塞控制算法,这篇很简单也明了的介绍了拥塞控制算法。

TCP 的拥塞控制算法有几个很重要的概念都提到了:“滑动窗口”、“慢启动”、“快重传”,还提到了 CUBIC 和 BBR(BufferBloat)。

这篇文章适合入门和回顾,具体的细节还是得自己看书系统的学习!

Tip

:w! sudo tee %

这是一条 vim 的内置命令,当你用普通用户编辑文件,但是没有权限保存的时候,这个条命令能够让你用 sudo 权限保存当前文件。

Share

https://github.com/pda/flexihash

PHP 版本的一致性 hash 算法,代码简单,思路清晰,可以作为学习参考资料。

本作品由 程小白 创作,采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可,可自由转载、引用但需署名作者且注明文章出处。
原文地址:https://www.chengxiaobai.cn/arts/20181124.html