网易有道笔试题（2014届，2013.10北邮站）

从网上看到网易有道2014届校园招聘的笔试题目，简单的做了一下编程和算法部分，都是一些平常遇到的题目，留一个笔记。

总共有两道编程题目和一个算法题目，编程题目要求写出可以运行的C/C++代码或者Java代码，第一个编程题如下：

（不是太清楚，但勉强能看）

对于这道题，应该是考察对于字符串的处理能力，应该是比较基础的题目。从题目的描述我们可以将要转换的字符串组合分成两大类

1，普通的字符串，不进行转换，如例子中的h1（两个尖括号中的内容）

2，以&开头并且以;（分号）结尾的的字符串，这类字符串需要按照给定的规则进行转换。该类有可以分成两类

1）&后面跟#和数字的UNICODE，需要当做一个UNICODE出来，输出的时候转换成相应的UNICODE进行输出

2）&后面试一个普通的字符串，是一个普通的转义字符，按照规则转换后输出

对于2中的2)我们可以先将转换规则存放在一个map<string, string> mapTable数据结构中，这样，每当我们遇到一个转义字符串的时候就可以通过查找这个mapTable得到

相应的转换后的字符。

具体代码如下：（没有考虑容错，如果有什么更好的代码方式，欢迎共同讨论）

这也是一个比较简单常见的题目，我的思路如下（如果您有更好的思路，欢迎和您讨论）：
对于一个给定的序列S = a0a1a2....a(n-1)，对于其中的任意一位ak，存在一个ap使得ak < ap 并且 k < p <= n-1那么交换ak与ap的位置，得到新的序列
S' = a0a1...ap...ak....a(n-1)，这这个序列中ap所在的位置为第k位，ak所在的位置为第p位。那么序列S‘一定是比S大的序列。
从这个思路出发，我们找一个比S大的最小的序列S''，也就是S的下一个序列。
要找到这样的S’‘，就需要找到一个最大的位置k使得所有的am > ak(m > k)，并交换ak与an，其中an = max(ar | k < r < n-1 并且 ar < ak) .
也就是在ak的右边找一个比ak小的最大的数，并让ak与之交换，然后把从第k+1到n-1上的数字进行从小到大排序。这是得到的整个序列就是要求的S''。
下面以23541为例子进行分析：
原始序列：

相应的k和p的位置如下：

其中4是k右边的比3大的最小的那个数字，因此交换3和4的位置，得到：

此时，序列24531还不是23541的下一个序列，要得到下一个序列需要对从第k+1 = 2位到n-1 = 4位的数字进行从小到大排序，得到新的序列：

到此，我们就得到了24531的下一个字典序：24135.
对于上面的分析，我们可以做出进一步的优化，同时也可以使用一些技巧避免对数字序列进行排序：
1. 通过分析我们可以知道，k的值就是使得a(n-1)a(n-2)...a(k+1)是递增序列的最小值
2.通过一个数组isUsed[n]，来记录从1到n的数字是否已经在0到k位出现，然后从小到大遍历isUsed数组，如果数字i没有出现，那么将它赋值给第k+1位，下一个没有出现的
赋值给第k+2位，以此类推。其实这里是应用了bit map的性质，从而避免了对数字串进行排序。关于bit map的知识参考：http://blog.csdn.net/hguisu/article/details/7880288和https://github.com/crazykeyboard/Bit-Map.
经过1和2的优化，算法的时间复杂度是O(n)
代码如下：

这是一个被多家公司使用过的题目，也有不少人给出比较好的解释，我在此就不罗嗦了，读者可以参考：http://remonstrate.wordpress.com/2013/01/17/%E7%9B%B4%E6%96%B9%E5%9B%BE%E4%B8%8B%E6%9C%80%E5%A4%A7%E9%9D%A2%E7%A7%AF%E7%9F%A9%E5%BD%A2/， 下面给出我的代码：
#include <iostream>#include <algorithm>#include <vector>using namespace std ;typedef struct node{int index ;int heighe ;node(int i = -1 , int h = 0) : index(i), heighe(h){};}Node ;int maxArea(vector<int>& histogram){int ret = 0;if (histogram.empty()) return 0 ;histogram.push_back(-1) ;Node *tmpStack = new Node[histogram.size() + 1] ;tmpStack[0] = Node(-1, 0) ;int stackIndex = 1 ;for (int i = 0; i < histogram.size();){if (tmpStack[stackIndex - 1].heighe <= histogram[i]){tmpStack[stackIndex ++] = Node(i, histogram[i]) ;++i ;}else{if (stackIndex == 1 && i == histogram.size() - 1) break ; //已经处理完所有的直方图int tmpArea = (i - tmpStack[stackIndex -2].index - 1) * tmpStack[stackIndex - 1].heighe ;ret = max(ret, tmpArea) ;stackIndex -- ; //出栈操作}}delete[] tmpStack ;return ret ;}int main(int argc, char** argv){int values[] = { 2, 1, 4, 5, 1, 3, 3, 1, 2} ;vector<int> tmp(values, values + sizeof(values) / sizeof(int))  ;cout << maxArea(tmp) << endl;return 0 ;}

欢迎转载，请注明出处：http://blog.csdn.net/doufei_ccst/article/details/12779831