未分类
Maximum Manhattan Distance of Two Points in Points Set
Manhattan Distance Definition: The Manhattan distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ in a 2D plane is defined as $dis = |…
未分类
Python
Dynamic Segment Tree
Why Dynamic Segment Tree? As know for segment tree, the space complexity is is up to 4 n, which n is upper bound of data range. However, :-…
数据结构/图论
红黑树-旋转的艺术
红黑树的定义和性质 红黑树的出现之前，先有的二叉查找树(BST)以及平衡二叉树(AVL树)： BST根节点的值大于所有左子树的所有值，小于右子树的所有值。 AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的高度差为小于等于1。 AVL的出现改变了BS…
Python
哈希(Hash)，字典(Dict)，集合(Set)
哈希(Hash) Hash又称为预映射，是通过散列算法将任意长度的输入变换成固定长度的输出，输出值称为散列值。这种转换是一种压缩映射，也就是散列值的空间通常远小于输入的空间，不同的输入可能得到相同的输出，所以不可能从散列值来确定唯一的输入值。 将输入映射为输出的过程可以称之为h…
未分类
mysql的各种连接生成了什么样的中间数据
数据准备 创建两个表，一个存放用户信息，另一个存放用户订购的信息 往表中插入数据 插入数据之后 插入数据之后： 笛卡尔积 也就是前面三列来自于Customer，后三列来自于Orders。数据行数为Customer的行数乘以Orders行数(63=7*9)。所有的数据都是两个表的…
未分类
MVCC真能解决幻读问题吗？
先说结论，MVCC不能完全解决幻读。只能解决快照读下的幻读，当前读的幻读依然需要借助next-key锁来解决幻读。 什么是幻读？ 使用InnoDB作为引擎的MySQL有四种事务隔离级别，分别是： - Read Uncommitted：读未提交 - Read Committed：…
未分类
类和对象的那点事
类和对象 class关键词声明的类其实也是 对象 ，比较特殊的是，它是 的实例对象。因此类也可以和对象一样作为参数进行传递等一系列操作。以下两种方法创造的类是一样的： 进一步验证： 输出为： 进一步说明了，无论是声明的类，还是实例化的对象，还是自带的数据类型。最终都是由type…
未分类
背包问题-完全背包
问题描述 完全背包问题和01背包问题不同的在于，每一个物体的数量可以是无限的，每一个物体的重量为C[i]，其产生的价值为 W[i]，一共N件物品。背包的容量为V。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 问题求解 和01背包问题的区别在于，0…
未分类
背包问题-01背包问题
01背包问题 问题抽象：有N个物体，每一个重量为c[i]，各自的价值为w[i]，背包最大容量为V,求背包能放下的物品总和的最大价值 DP思想解决问题 每一个物体都有被放入和不被放入的可能，当前被选择的物体是否被放入所产生的最大价值和后续的物体无关(无后效性)，只和前面已经放入的…
未分类
一致性Hash算法及python实现
普通Hash算法 我们在实现服务器负载均衡时候可供选择的负载均衡的算法有很多，包括： 轮循算法（Round Robin）、哈希算法（HASH）、最少连接算法（Least Connection）、响应速度算法（Response Time）、加权法（Weighted ）等。其中哈希…
未分类
实习秋招的面经篇-鹅厂
最近参加了鹅厂的实习面试，总结一下问题和答案如下： 最近的鹅厂的一面经历如下： - 1）自我介绍 这个环节是每个公司每一轮面试都会有的，一般是三五分钟，突出自己的重点和亮点就行。 - 1.1）问了问是什么类型的硕士，以及什么时间可以去实习 - 1.2）问了在本科和研究生阶段做过…
未分类
并查集-LeetCode无向图寻找闭环
并查集适用来高效地处理不相交集合（disjoint sets）的合并及查询问题。尤其是出现判断数据的相交情况时，尤其的高效。例如LeetCode的684题：无向图寻找闭环。原题如下： 对于此题，可以通过遍历每一条边的两个端点，寻找两个端点的祖父节点来查看他们是否为同一集合，如果…