Posts

给定 x, k ，求满足 x + y = x | y 的第 k 小的正整数 y 。 | 是二进制的或(or)运算，例如 3 | 5 = 7。 比如当 x=5，k=1时返回 2，因为5+1=6 不等于 5|1=5，而 5+2=7 等于 5 | 2 = 7。

有一个由很多木棒构成的集合，每个木棒有对应的长度，请问能否用集合中的这些木棒以某个顺序首尾相连构成一个面积大于 0 的简单多边形且所有木棒都要用上，简单多边形即不会自交的多边形。

有 n 个字符串，每个字符串都是由 A-J 的大写字符构成。现在你将每个字符映射为一个 0-9 的数字，不同字符映射为不同的数字。这样每个字符串就可以看做一个整数，唯一的要求是这些整数必须是正整数且它们的字符串不能有前导零。现在问你怎样映射字符才能使得这些字符串表示的整数之和最大？ 输入描述：每组测试用例仅包含一组数据，每组数据第一行为一个正整数 n ， 接下来有 n 行，每行一个长度不超过 12 且仅包含大写字母 A-J 的字符串。 n 不大于 50，且至少存在一个字符不是任何字符串的首字母。 输出描述：输出一个数，表示最大和是多少。 输入例子： 2 ABC BCA 输出例子： 1875 一开始看漏了首位不能映射到0的条件…直接贪了..结果发现不太对…

分析 levelDB 源码的时候遇到的，发现是一个广泛应用的 hash 算法，而且是纯 C 写的，于是找来了源码看。 MurmurHash 是一种非加密型哈希函数，适用于一般的哈希检索操作。[1][2][3]由Austin Appleby在2008年发明，[4][5] 并出现了多个变种，[6] 都已经发布到了公有领域(public domain)。与其它流行的哈希函数相比，对于规律性较强的key，MurmurHash的随机分布特征表现更良好。[7]

起因是最近在看 levelDB 源码，其中 port 里的atomic_pointer.h 文件用到了内存屏障。。 于是来学习一下。 粗略地说下我自己的理解。 代码的顺序并不和执行的顺序完全对应，出于对效率的追求，CPU 和编译器会对指令进行重排，以期得到最大的执行效率。

参考资料 看 leveldb 源码中遇到的，关于 lock-free 和 wait-free..感觉这个讲得不错，我试着翻译一下？ There are two types of non-blocking thread synchronization algorithms - lock-free, and wait-free. Their meaning is often confused. In lock-free systems, while any particular computation may be blocked for some period of time, all CPUs are able to continue performing other computations. To put it differently, while a given thread might be blocked by other threads in a lock-free system, all CPUs can continue doing other useful work without stalls. Lock-free algorithms increase the overall throughput of a system by occassionally increasing the latency of a particular transaction. Most high- end database systems are based on lock-free algorithms, to varying degrees.

参考资料： awk_维基百科 awk简明教程 awk是一门比较古老但是很好用的文本处理工具（语言？） 语法还是很好懂的。。转载了一篇文章，算是简明手册？不过台词有点糟糕 orz 有一些网友看了前两天的《Linux下应该知道的技巧》希望我能教教他们用awk和sed，所以，出现了这篇文章。我估计这些80后的年轻朋友可能对awk/sed这类上古神器有点陌生了，所以需要我这个老家伙来炒炒冷饭。况且，AWK是贝尔实验室1977年搞出来的文本处理神器，今年是蛇年，是AWK的本命年，而且年纪和我相仿，所以非常有必要为他写篇文章。 之所以叫AWK是因为其取了三位创始人 Alfred Aho，Peter Weinberger, 和 Brian Kernighan 的Family Name的首字符。要学AWK，就得提一提AWK的一本相当经典的书《The AWK Programming Language》，它在豆瓣上的评分是9.4分！在亚马逊上居然卖1022.30元。

基本全文照搬了：关于C++ const 的全面总结 总结全面还是要一点时间的orz..感谢原作者，暂时没发现有什么错误（? 其中对我而言比较陌生的是“const修饰成员函数”的用法。。已经加粗。

系统信息： 表现为不管外放还是耳机。。都没有声音。。。 解决办法： 1pacmd set-card-profile alsa_card.pci-0000_00_1b.0 output:analog-stereo+input:analog-stereo 参考资料

原始论文：一致性哈希 本来不打算放的。。被批评说太不严谨 orz 说说自己的理解好了。 大概就是 hash 的时候，一开始有 n 个桶，你设计的函数是 y=x%n，看起来美滋滋。 然后这时候突然一个桶不见了，如果按照之前设计的 hash 函数，就变成了 x%(n-1)。

参考：FHS（Filesystem Hierarchy Standard） 其实这东西虽然有一个统一的标准，但是不同发行版，或者同一个发行版的不同版本，差异貌似都蛮大的。所以这里只是理论上各个目录的作用，可能和具体的发行版不符。。

参考链接 简要概述原理： 每个文件都由各种不同代码组成，比如01代码。这类文件只有数字0与1组合。 压缩原理就是 【通过寻找其中的规律，简化数字的排列】。 比如 00000110001111111111 可以简化成 5个0,2个1,3个0,10个1的排列 100000000000 可以简化成数学的 10^10

参考博客 计组块忘光了呜呜呜。。。来复习一波。。 1. LRU # 1.1. 原理 LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

I want to match those five numbers 3, 7, 8, 9, 87 through regular express. Here is my thought: match those four numbers 3 7 8 9 var ^[3|7|8|9]\( match number 87 var ^87\) Then combine them together, (^[3|7|8|9]\(|^87\)). With some test, it seems correct. Is there any way to do that more efficiently? Q: 已知三个升序整数数组a[l], b[m]和c[n]。请在三个数组中各找一个元素，使得组成的三元组距离最小。 三元组的距离定义是：假设a[i]、b[j]和c[k]是一个三元组，那么距离为： Distance = max(|a[i] – b[j]|, |a[i] – c[k]|, |b[j] – c[k]|) 请设计一个求最小三元组距离的最优算法，并分析时间复杂度。

转自：http://blog.csdn.net/v_july_v/article/details/6279498 第一部分、十道海量数据处理面试题 1、海量日志数据，提取出某日访问百度次数最多的那个IP。

题意：定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数，要求时间复杂度为O(1) 思路：标题党去死一死好么。。。真是无趣。。。就是用两个栈封装成一个。。。一个栈s1正常搞。。。一个是辅助栈s2。。每次去存min(value,s2.top());

题意：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

虽然说感觉这届学弟蛮厉害…不知道能不能拿到校内资格。。。 以及没有太多时间训练… 不过只要假期实习的地方。。。加班不是很多的话。。。 大概。。。晚上+周末。。。还是可以补补多校的。。。？

思路： 一个元素入队的时候直接插入到stack1中。。。 一个元素出队的时候。。。如果stack2不为空。。stack2顶的元素就是要出队的。。 如果stakc2为空。。。就将stack1清空，按照元素出栈的顺序依次入栈到stack2

思路： 分治搞之。 实际上两个vector就够了。。。4个会MLE(在leetcode上。。。 代码实现 1/** 2 * Definition for binary tree 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 TreeNode* res; 13 TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) { 14 int siz = pre.size(); 15 if (siz==0) return NULL; 16 int rt = pre[0]; 17 int pos=-1; 18 for ( int i = 0 ; i < siz; i++) 19 if (vin[i]==rt) 20 { 21 pos = i; 22 break; 23 } 24 vector<int>preL,preR,vinL,vinR; 25 for ( int i = 0 ; i < pos ; i++) 26 { 27 preL.push_back(pre[i+1]); 28 vinL.push_back(vin[i]); 29 } 30 for ( int i = pos + 1 ; i < siz ; i++) 31 { 32 preR.push_back(pre[i]); 33 vinR.push_back(vin[i]); 34 } 35 TreeNode *head = new TreeNode(rt); 36 head->left = reConstructBinaryTree(preL,vinL); 37 head->right = reConstructBinaryTree(preR,vinR); 38 return head; 39 40 41 } 42}; 43 44 45 46 47/* *********************************************** 48Author :111qqz 49Created Time :2017年04月05日 星期三 16时21分35秒 50File Name :105.cpp 51************************************************ */ 52/** 53 54 * Definition for a binary tree node. 55 56 * struct TreeNode { 57 58 * int val; 59 60 * TreeNode *left; 61 62 * TreeNode *right; 63 64 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 65 66 * }; 67 68 */ 69 70class Solution { 71 72public: 73 74 TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { 75 76 int siz = preorder.size(); 77 if (siz==0) return NULL; 78 int rt = preorder[0]; 79 int pos; 80 for ( int i = 0 ; i < siz ; i++) 81 { 82 if (inorder[i]==rt) 83 { 84 pos = i; 85 break; 86 } 87 } 88 vector<int>preL,inL; 89 TreeNode *head = new TreeNode(rt); 90 for ( int i = 0 ; i < pos ; i++) 91 { 92 preL.push_back(preorder[i+1]); 93 inL.push_back(inorder[i]); 94 } 95 head->left = buildTree(preL,inL); 96 97 preL.clear(); 98 inL.clear(); 99 for ( int i = pos + 1 ; i < siz; i++) 100 { 101 preL.push_back(preorder[i]); 102 inL.push_back(inorder[i]); 103 } 104 head->right = buildTree(preL,inL); 105 return head; 106 107 } 108 109};