O(n)时间快速选择

Posted on by

如何在期望线性时间选出第i小的元素？
通过该调用快速排序的random_partition可以实现在平均O(n)时间内选出第i小的元素。
根本原因：这种方法实际上是对数组进行了局部的排序，每次只排序partition后的一半，因为将快速排序的平均时间O(nlogn)降到了O(n).严谨的数学证明请参见《算法导论》。
下面先给出算法的实现，然后叙述缺点及改进。

2018秋招总结

Posted on by


秋招终于结束了，趁着还有些记忆写下这篇面经，希望对学弟学妹有所帮助。

google code jam2016资格赛题解

Posted on by

A. Counting Sheep
小数据暴力，大数据也一样
B. Revenge of the Pancakes
小数据暴力，大数据没做
C. Coin Jam
小数据暴力，大数据没做
D. Fractiles
题意：一个序列由两种字符组成:L、G.给出k，c，s。表示序列初始长度k，变换了c次。每次变换：L的地方用最初始序列代替，G的地方用k个G代替。
现序列各个位置的值是看不到的，你可以选择查看其中的s个位置的值。问：能否通过小于等于s次查看，来推断出现序列是否包含G。
这题我是这样做的。小数据大数据一个做法。
如果查看一个位置发现是G，那么我们就知道序列是含有G的了，所以问题其实是在问：有没有一种查看的策略使得在查看的值都是L的情况下，可以断定序列必定没有G。
我们可以把整个变换的过程画出来，可以发现是一棵k叉树（注意一点这里我把原始序列的k个结点最为统一的“根结点”）。叶子节点是现序列。关键一点在于当得到了位置pos的值是L之后，我们就知道了pos位置的值是L之后，就知道了pos的父节点是L，它的父节点也是L。换言之，pos到树根的路径上的结点都是L。
那么为了尽可能通过一次查看得到最多信息，我们可以查看根节点的第二个子结点的第三个子结点的…………（一直到叶子结点）的值。这样就得到了min(c,k)个连续位置的值，接下来重复这个查看过程就行。
这个还是有个图比较好解释。。下次加个图。

linux内核模块编程笔记

Posted on by

最近因为实验室项目，开始接触了一点linux内核模块编程
内核编译选项.config所在路径:/usr/src/相应内核版本/.config
内核符号表：在编写内核模块的时候，因为LKM是动态加载到内核中，也就是说这时的内核是在内存中运行的,所以正确获取内核函数和变量的地址很重要。如果我们在内核模块中直接将地址写死，那么显然不通用，在另一个内核上可能地址就变了。内核符号表就是用于解决这个问题。每个内核都有其内核符号表，里面是内核导出的符号及其地址。我们编写的内核模块通过访问这个内核符号表就可以得到当前正在运行的内核的可用函数和变量的确切地址。
那么怎样使用内核未导出的符号呢？
我们可以使用kallsyms_lookup_name(char*)这个函数，该函数参数是符号名，返回unsigned long型的函数/变量地址。这个方法有个前提，那就是kallsyms_lookup_name(char*)这个符号本身是被内核导出的，所以要用CONFIG_KALLSYMS=y来编译内核，或者修改内核源码中的kallsyms.c文件，增加EXPORT_SYMBOL(kallsyms_lookup_name);手动将该符号导出
————————————————————————————————————————————————————————————————————————————
过程中的问题和要点：
linux内核的三种内存模型
page结构中的_count和_mapcount
_mapcount：在页表中每增加一个映射项，_mapcount就加1.初始值是-1

虚拟化笔记

Posted on by

VMM进程地址空间中存储了各个虚拟机具体的硬件环境（如PC值、EAX值等等，PC值指向guestOS的代码），guestOS在运行时（其实就是VMM将真实寄存器等硬件环境改为guestOS的环境，PC改为指向guestOS的代码，这样guestOS的代码就开始运行了），其代码是真正运行在真实cpu上的，由于guestOS是在ring3，所以执行特权指令时触发异常，VMM的异常处理模块截获异常，然后再做安排。

leetcode比较重要的题(always updating)

Posted on by

对leetcode比较重要的题做下记录。
“重要”的条件：
1.没能想到解法的题
2.没能想到最优解的题
3.虽想到最优解，但是面试现场容易出错的题
关于第三点易出错是指完成时间较长，或者对代码修改多次。
注意，建议读者在做题时不要使用编译器编译，而是用肉眼和纸笔进行debug，毕竟面试时不可能让你用编译器。
10 Regular Expression Matching(hard)
这题虽然知道用递归，但是还是没想出来。。

Shortest Palindrome

Posted on by

leetcode的一道题
题意：给出一个字符串，只能在首部加上字符使其成为回文串，求所加字符数最少的方案。
这题以前搞acm的时候碰到过，如果是以前，就直接上KMP了。但是前面有道题是用manacher算法求字符串的最长回文子串。突然发现这题也可以用manacher来做，时间复杂度也是O(n)。
manacher确实是一种思路巧妙，代码简短的算法。
https://leetcode.com/problems/shortest-palindrome/

bestcoder#64 div1

Posted on by

还是做出两题。。
1001(hdu5586) Sum
题意：给出n个数，给出函数f(x)，现在可以对连续的一段区间的数使用f(x)转换，也可以不用。问最后这n个数之和最大是多少.
简单dp。可以先对这n个数都使用f(x)得到新的数组b(设原数组为a),b[]-a[]，得到数组c。对c[]求最大子串和，这个最大子串和就是对某一段数施加f(x)之后可以达到的最大增益。如果是负的，那么显然不应该进行f(x)的转换。a数组的和加上这个增益就是答案。

bestcoder#63 div1

Posted on by

第一次做div1，解出两道题，能做的也只有两道。但是第一题罚时有点厉害，一直不太相信需要高精度（因为output里写了integer。。）
1001(hdu5568) sequence2
一个整数序列有多少种长度为k的不同的递增子序列，两个子序列只要有一个元素对应位置不同就算不同。
如1 2 2有两个长度为2的不同子序列1 2和1 2（这两个2位置不同）
简单的dp题。dp[i][j]表示前i个数组成的序列中有多少个长度为j的不同子序列。
dp[i][j]=sigma(dp[t][j-1]),其中a[i]>a[t]。