Du Yao's blog

ConcurrentHashMap是Java 5中支持高并发、 高吞吐的HashMap。它的关键技术是：锁分离技术。 它使用了多个锁来控制对hash表的不同部分进行修改。 实现ConcurrentHashMap包含了两个静态内部类： HashEntry用来封装映射表的键值对 Segment用来充当锁的角色， 是一种可重入锁ReentrantLock 利用了锁分离技术来保护不同的segmen... 阅读全文...

IntroductionA Queue that additionally supports operations that wait for the queue to become non-empty when retrieving an element, and wait for space to become available in the queue when storing an... 阅读全文...

字典树通常用于查找字符串，比如在搜索框中搜索会自动提示，或者lucene常用操作有 插入和查找, 删除 代码习题 208. Implement Trie (Prefix Tree) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575... 阅读全文...

比较在集合框架中有两种比较接口： Comparable 接口和 Comparator 接口。Comparable 是通用的接口，用户可以实现它来完成自己特定的比较，在java.lang下Comparator 可以看成一种算法的实现，在需要容器集合实现比较功能的时候，来指定这个比较器，这可以看成一种设计模式，将算法和数据分离，在java.util下。 前者应该比较固定，和一个具体类相绑定，而后... 阅读全文...

红黑树Red-Black Tree(R B-tree) 性质本质是一个有限制的二叉搜索树BST,即每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。 ... 阅读全文...

各种关系浅蓝色是接口深蓝色是类 collection的关系 Collection接口继承于接口Iterator1234567891011121314151617181920public... 阅读全文...

330. Patching Array 思路贪心设置miss为缺少的数字，sum为当前所有选中数字的的最小和挑选miss的规则 若数组中x <= sum + 1则选中x 若数组没有，就选中sum + 1为miss直到sum > n 思路参考 123456789101112131415161718public int minPatches(int[] nums, int n) ... 阅读全文...

331. Verify Preorder Serialization of a Binary Tree 思路一砍掉叶子节点两个叶子节点访问后就将该父节点置为叶子节点，这样一个树访问完成后只剩下一个叶子节点因此需要一个栈来存放先序遍历，对于连续栈中两个##，删除##，并且将栈顶替换为#12345678910111213141516171819202122232425public boolean... 阅读全文...

332. Reconstruct Itinerary 思路 要先将思维转换到图，每个点都可以看做是图上的一个点 这不是dfs，因为不只是遍历，而是顺序遍历所有路径，即一笔画欧拉路径问题 参考wikipedia Hierholzer’s algorithmEulerian Path and Circuit Fleury’s algorithmDon’t burn your bridge... 阅读全文...

46. Permutations相似问题78. Subsets题解78 Answer 回溯法backtrack 递归和非递归 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465//递归public st... 阅读全文...