Posts

前言： # 其实有了前文simhash算法的基础，局部敏感hash算法已经不存在理解上的问题了吧。。。毕竟simhash算法应该是局部敏感哈希算法的一种。。所以我就直接转载几篇我认为比较好的文档结合一下好了。。。会把比较重要的概念或者定义标记重点。

先放原始论文。。以此表达对这个算法的敬意 orz 论文链接 问题引出： # 那天百度一面，frog 学姐问了我如何判断两篇新闻稿相似度的问题….我满篇口胡，也只是回答了一些诸如从图片上考虑、或者去掉 stop word 之后得到特征向量再计算余弦值之类的传统想法。

面京东被这个问题卡了QAQ，来补补这方面的课。 转自：链接 蓄水池抽样算法是随机算法的一种，用来从 N 个样本中随机选择 K 个样本，其中 N 非常大（以至于 N 个样本不能同时放入内存）或者 N 是一个未知数。其时间复杂度为 O(N)，包含下列步骤 (假设有一维数组 S, 长度未知，需要从中随机选择 k 个元素， 数组下标从 1 开始), 伪代码如下：

题目链接 题意：给一个二维数组。。。每一行每一列都分别递增。。问某个value是否出现过。。。

回想起大一的时候打cf…那个时候对C++还不怎么熟悉。。。用sort不会自定义排序方式。。

起因是百度实习二面的时候被问了一道类似这样的题： 给我下面的代码，问有没有什么问题。

题目链接 题意：求一棵二叉树中，所有一段连续路径之和等于给定值的路径数目。

题目链接 题意：判断一棵二叉树是否是自己的镜像。做法是做个copy，相当于两棵树做比较。注意逻辑不要漏掉就好

题目链接 题意：判断一颗二叉树是否平衡…. 思路：直接搞就好了。。。神TM又忘记dfs的时候忘记返回子调用的值。。。。我这是药丸啊。。。

题目链接 题意：求一个BST中某两个节点LCA…. 思路：卧槽。。。竟然求LCA…直接想到的显然是Tarjan的方法或者。。。RMQ+DFS。。。但是感觉。。。leetcode怎么可能考算法。。。。于是想到。。。可以从BST下手。。。

题目链接 题意：求一棵树的深度。。。。 思路：。。。定义搞即可。。按照左右子树中大的算。。。因为据说是经典题（虽然并不觉得2333。。。所以记录下。。。

题目链接 题意：反转一棵二叉树。。。字面意思理解即可。。就是把每一棵子树的左右孩子交换。。。

题目链接 题意：给一棵树。。问是否存在一条从树根到叶子的路径，使得路径上每个点的val之和等于给定的sum。

leetcode108 题意：把一个有序的数组转化成一棵高度尽量小的bst(二叉搜索树)

最近要准备面试…虽然leetcode的题目难度比较水..不过白板写代码还是要练下的。。。我所理解的白板写代码。。。大概就是。。。用记事本。。一遍写对代码的能力吧。。。所以我来记录一下。。思路想错的或者没有秒的题目。

1303: [CQOI2009]中位数图 # Time Limit: 1 Sec Memory Limit: 162 MB Submit: 2480 Solved: 1529 [Submit][Status][Discuss]

所以还是稍微写写年终总结吧.. 感觉…2016分成了两部分吧，前11个月是一部分，后1个月是另一部分。

1800: [Ahoi2009]fly 飞行棋 # Time Limit: 10 Sec Memory Limit: 64 MB Submit: 1530 Solved: 1220 [Submit][Status][Discuss]

1207: [HNOI2004]打鼹鼠 # Time Limit: 10 Sec Memory Limit: 162 MB Submit: 2854 Solved: 1390 [Submit][Status][Discuss]

绝望什么的… 总要有个具体的事情吧… 可是又说不清…好像突然每件事都让我绝望…