Posts

前言： # hash这种东西人人都会用的东西还有必要说？ 起因是…本问了hash中的一个细节…然后…我知道怎么做… 结果描述的不够清楚？如果知道那个做法的名字也许就不用费劲描述了呢。。。所以来复习一下吧2333

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

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

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

题目链接 题意：给一个二维数组。。。每一行每一列都分别递增。。问某个value是否出现过。。。 思路：单调。。显然二分。。。唯一的技巧是从右上角开始搜。 1/* *********************************************** 2Author :111qqz 3Created Time :2017年03月09日 星期四 19时03分07秒 4File Name :74.cpp 5************************************************ */ 6class Solution { 7 8public: 9 10 bool searchMatrix(vector<vector<int>>& matrix, int target) { 11 12 int n = matrix.size(); 13 if (n==0) return false; 14 int m = matrix[0].size(); 15 if (m==0) return false; 16 int row = 0 ; 17 int col = m-1; 18 while (col>=0&&row<n) 19 { 20 if (matrix[row][col]==target) return true; 21 else 22 if (matrix[row][col]>target) col--; 23 else row++; 24 } 25 return false; 26 27 } 28 29};

回想起大一的时候打cf…那个时候对C++还不怎么熟悉。。。用sort不会自定义排序方式。。 于是手写快排。。。直接取中间元素没加随机化。。。跪了。。。 后来知道sort怎么写以后。。发现sort是可以通过的。。。

起因是百度实习二面的时候被问了一道类似这样的题： 给我下面的代码，问有没有什么问题。 1/* *********************************************** 2Author :111qqz 3Created Time :2017年02月28日 星期二 14时49分37秒 4File Name :vector.cpp 5************************************************ */ 6#include <cstdio> 7#include <vector> 8#include <ctime> 9using namespace std; 10int func( int x ) //此处函数的条件是不单调...这样才可以触发问题. 11{ 12 return (x-50)*(x-50)+1; 13} 14int main() 15{ 16 17 vector<int>vec; 18 int *pint = NULL; 19 for ( int i = 0 ; i < 100 ; i++) 20 { 21 int x = func(i); 22 vec.push_back(x); 23 if (x<500) 24 { 25 pint = & vec[0]; 26 } 27 } 28 if (pint) 29 *pint = 0 ; 30 int siz = vec.size(); 31 for ( int i = 0 ; i < siz ; i++) printf("%d\n",vec[i]); 32 return 0; 33} 面试的时候只给了部分代码，func函数没有给出。

题目链接 题意：求一棵二叉树中，所有一段连续路径之和等于给定值的路径数目。 思路：想了半天就只能想到暴力。。。复杂度大概O(n^2)。。。也不是不可以接受。。。但是感觉这也太暴力了。。就去看了题解。。。发现题解就还真是暴力orz。。。

题目链接 题意：判断一棵二叉树是否是自己的镜像。做法是做个copy，相当于两棵树做比较。注意逻辑不要漏掉就好 1/** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10class Solution { 11public: 12 13 bool leaf(TreeNode* root) 14 { 15 if (root->left==NULL&&root->right==NULL) return true; 16 return false; 17 } 18 bool mirror(TreeNode* rt1,TreeNode* rt2) 19 { 20 21 if (rt1==NULL&&rt2==NULL) return true; 22 if (rt1==NULL||rt2==NULL) return false; 23 printf("%d %d\n",rt1->val,rt2->val); 24 if (leaf(rt1)&&leaf(rt2)&&rt1->val==rt2->val) return true; 25 if (leaf(rt1)||leaf(rt2)) return false; //包含了其中一个是叶子，或者两个都是叶子但是值不相等的情况。 26 if (rt1->val!=rt2->val) return false; //不是叶子，但是值不相等，没必要继续了。 27 bool res = true; 28 res = mirror(rt1->left,rt2->right); 29 if (!res) return false; 30 res = mirror(rt2->left,rt1->right); 31 if (!res) return false; 32 return true; 33 } 34 bool isSymmetric(TreeNode* root) { 35 if (root==NULL) return true; 36 return mirror(root,root); 37 38 } 39};

题目链接 题意：判断一颗二叉树是否平衡…. 思路：直接搞就好了。。。神TM又忘记dfs的时候忘记返回子调用的值。。。。我这是药丸啊。。。 1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10class Solution { //错误原因：左右子树都平衡的树未必平衡！！！！ 11public: 12 bool leaf(TreeNode* root) 13 { 14 if (root->left==NULL&&root->right==NULL) return true; 15 return false; 16 } 17 int dep(TreeNode* root) 18 { 19 if (root==NULL) return 0; 20 return max(dep(root->left),dep(root->right))+1; 21 } 22 bool dfs(TreeNode* root) 23 { 24 bool res = true; 25 if (abs(dep(root->left)-dep(root->right))>1) return false; 26 if (root->left!=NULL) res = dfs(root->left); 27 if (!res) return false; 28 if (root->right!=NULL) res = dfs(root->right); 29 if (!res) return false; 30 return true; 31 } 32 bool isBalanced(TreeNode* root) { 33 if (root==NULL) return true; 34 bool res = dfs(root); 35 return res; 36 } 37};

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

题目链接 题意：求一棵树的深度。。。。 思路：。。。定义搞即可。。按照左右子树中大的算。。。因为据说是经典题（虽然并不觉得2333。。。所以记录下。。。 1/** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10class Solution { 11public: 12 13 int dfs(TreeNode* root) 14 { 15 if (root==NULL) return 0; 16 return max(dfs(root->left),dfs(root->right))+1; 17 } 18 19 int maxDepth(TreeNode* root){ 20 if (root==NULL) return 0; 21 int res = dfs(root); 22 return res; 23 24 25 } 26};

题目链接 题意：反转一棵二叉树。。。字面意思理解即可。。就是把每一棵子树的左右孩子交换。。。 思路：直接照着题意做就好了。。。没有坑。。记录的原因是听说这题比较经典（虽然毫无难度…

题目链接 题意：给一棵树。。问是否存在一条从树根到叶子的路径，使得路径上每个点的val之和等于给定的sum。 思路：。。。直接搞就好。。。由于是比较经典的题目所以记录一下。。。注意递归的时候每一部分都要返回值orz..(我是多久没写代码了。。。

leetcode108 题意：把一个有序的数组转化成一棵高度尽量小的bst(二叉搜索树) 思路：我竟然忘记了什么是bst……..我好傻啊…不过想想可能是因为…最朴素的二叉搜索树几乎用不到…所以很容易忘记吧2333

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

1303: [CQOI2009]中位数图 # Time Limit: 1 Sec Memory Limit: 162 MB Submit: 2480 Solved: 1529 [Submit][Status][Discuss] Description # 给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。

所以还是稍微写写年终总结吧.. 感觉…2016分成了两部分吧，前11个月是一部分，后1个月是另一部分。 前11个月似乎都在做同一件事。大概先是期末花了两周时间稍微应付了下考试…然后就开始写题了…当时是第一次寒假留校…冻成狗orz

1800: [Ahoi2009]fly 飞行棋 # Time Limit: 10 Sec Memory Limit: 64 MB Submit: 1530 Solved: 1220 [Submit][Status][Discuss] Description # 给出圆周上的若干个点，已知点与点之间的弧长，其值均为正整数，并依圆周顺序排列。 请找出这些点中有没有可以围成矩形的，并希望在最短时间内找出所有不重复矩形。

1207: [HNOI2004]打鼹鼠 # Time Limit: 10 Sec Memory Limit: 162 MB Submit: 2854 Solved: 1390 [Submit][Status][Discuss] Description # 鼹鼠是一种很喜欢挖洞的动物，但每过一定的时间，它还是喜欢把头探出到地面上来透透气的。根据这个特点阿Q编写了一个打鼹鼠的游戏：在一个nn的网格中，在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠，如果i时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格，即从坐标为（i,j）的网格移向(i-1, j),(i+1, j),(i,j-1),(i,j+1)四个网格，机器人不能走出整个nn的网格。游戏开始时，你可以自由选定机器人的初始位置。现在你知道在一段时间内，鼹鼠出现的时间和地点，希望你编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠。