从网上看到网易有道2014届校园招聘的笔试题目，简单的做了一下编程和算法部分，都是一些平常遇到的题目，留一个笔记。
总共有两道编程题目和一个算法题目，编程题目要求写出可以运行的C/C++代码或者Java代码，第一个编程题如下：
（不是太清楚，但勉强能看）
对于这道题，应该是考察对于字符串的处理能力，应该是比较基础的题目。从题目的描述我们可以将要转换的字符串组合分成两大类
1，普通的字符串，不进行转换，如例子中的h1（两个尖括号中的内容）
2，以&开头并且以;（分号）结尾的的字符串，这类字符串需要按照给定的规则进行转换。该类有可以分成两类
1）&后面跟#和数字的UNICODE，需要当做一个UNICODE出来，输出的时候转换成相应的UNICODE进行输出
2）&后面试一个普通的字符串，是一个普通的转义字符，按照规则转换后输出
对于2中的2)我们可以先将转换规则存放在一个map<string, string> mapTable数据结构中，这样，每当我们遇到一个转义字符串的时候就可以通过查找这个mapTable得到
相应的转换后的字符。
具体代码如下：（没有考虑容错，如果有什么更好的代码方式，欢迎共同讨论）
#include <iostream>
#include <string>
#include <map>
#include <cstdlib>
using namespace std;
void parse(const string& srcStr, map<string, string>& mapTable)
{
if (srcStr.empty()) return ;
wcout.imbue(locale("chs")) ; //设置编码方式，能够输出unicode
int p0 = 0, p1 = 0, p2 = 0 ;
while(p0 != string :: npos && p0 < srcStr.length())
{
p1 = srcStr.find_first_of("#&", p0) ;
if (p1 == string :: npos)
{
cout << srcStr.substr(p0, srcStr.length() - p0) ; //一个普通字符串
return ;
}
else
{
cout << srcStr.substr(p0, p1 - p0) ;//一个普通字符串
p2 = srcStr.find_first_of(";", p1) ;
if (p2 == string :: npos)
{
cout << "Bad format" << endl;
return ;
}
string inStr = srcStr.substr(p1, p2 - p1 + 1) ;
if (inStr.length() >= 2 && inStr.at(1) == '#') //是一个UNICODE
{
int uniNum = atoi(inStr.substr(2, inStr.length() - 2).c_str()) ;
wcout << wchar_t(uniNum) ;
}
else //是一个普通的转义字符
{
string tmpStr = mapTable[inStr] ;
cout << tmpStr ;
}
p0 = p2 + 1;
}
}
cout << endl;
}
int main(int argc, char** argv)
{
string src ;
cin >> src ;
map<string , string > mapTable ;
mapTable["""] = "\"" ;
mapTable["&"] = "&" ;
mapTable["<"] = "<" ;
mapTable[">"] = ">" ;
parse(src, mapTable) ;
return 0 ;
}
突然发现上面代码中，由于CSDN网站转码的问题，main函数中的一些字符串已经被自动转换了，我只好贴出图片了（2014.3.24修改）：
另外，非常感谢 tadonis的建议，将参数map作为const传入，修改如下（VS2008调试通过，XCode中map实现与VS2008不同，需要做调整）：
void parse(const string& srcStr, const map<string, string>& mapTable)
{
if (srcStr.empty()) return ;
wcout.imbue(locale("chs")) ; //设置编码方式，能够输出unicode
int p0 = 0, p1 = 0, p2 = 0 ;
while(p0 != string :: npos && p0 < srcStr.length())
{
p1 = srcStr.find_first_of("#&", p0) ;
if (p1 == string :: npos)
{
cout << srcStr.substr(p0, srcStr.length() - p0) ; //一个普通字符串
return ;
}
else
{
cout << srcStr.substr(p0, p1 - p0) ;//一个普通字符串
p2 = srcStr.find_first_of(";", p1) ;
if (p2 == string :: npos)
{
cout << "Bad format" << endl;
return ;
}
string inStr = srcStr.substr(p1, p2 - p1 + 1) ;
if (inStr.length() >= 2 && inStr.at(1) == '#') //是一个UNICODE
{
int uniNum = atoi(inStr.substr(2, inStr.length() - 2).c_str()) ;
wcout << wchar_t(uniNum) ;
}
else //是一个普通的转义字符
{
//string tmpStr = mapTable[inStr] ;
//cout << tmpStr ;
map<string, string> :: const_iterator it = mapTable.find(inStr) ;
cout << (it->second) ;
}
p0 = p2 + 1;
}
}
cout << endl;
}
下面是变成题目的第2题：
这也是一个比较简单常见的题目，我的思路如下（如果您有更好的思路，欢迎和您讨论）：
对于一个给定的序列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)
代码如下：
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <algorithm>
using namespace std ;
unsigned int nextSeq(unsigned int seq)
{
//抽取每一个数字
vector<char> digits ;
unsigned int preSeq = seq ;
while(preSeq)
{
digits.push_back(preSeq % 10) ;
preSeq /= 10 ;
}
reverse(digits.begin(), digits.end()) ;
int k = digits.size() - 1 ;
while(k > 0 && digits.at(k - 1) > digits.at(k)) --k ;
if (k > 0) -- k ;
else
return seq ; //没有下一个序列返回自身
//交换digits[k]和ddigits[q]的值
int q = digits.size() - 1 ;
while (digits.at(q) < digits.at(k)) --q ;
swap(digits.at(k), digits.at(q)) ;
//剩下的字符从小到大排序，这里使用bitmap的思想排序(并没有真正用bitmap)
int leftNum = digits.size() - k - 1 ;
bool *isUsed = new bool[digits.size()] ;
memset(isUsed, 0 , digits.size()) ;
for (int i = 0; i <= k ; ++ i)
isUsed[digits.at(i) - 1] = true ;
for(int i = 0; i < digits.size(); ++ i)
if (!isUsed[i]) digits.at(++k) = i + 1 ;
delete[] isUsed ;
//计算下一个序列的数值
int ret = 0 ;
for (int i = 0; i < digits.size(); ++ i)
{
ret *= 10 ;
ret += digits.at(i) ;
}
return ret ;
}
int main(int argc, char ** argv)
{
int inNum ;
while (cin >> inNum)
{
cout << nextSeq(inNum) << endl;
}
return 0 ;
}
2014.3.24 更改后的代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std ;
/**************************************
* str 表示原始的序列
* n 表示序列的长度
* 下一个序列存放在str中返回
**************************************/
bool nextPermutation(char *str, int n)
{
bool ret = false ;
if (!str || n <= 0) return ret;
int i = n - 2 ;
while (i >= 0 && str[i] >= str[i + 1])
--i ;
if (i < 0)
{
reverse(str, str + n) ;
ret = false;
}
else
{
int j = n - 1;
while (str[j] <= str[i]) --j ;
swap(str[i], str[j]) ;
reverse(str + i + 1, str + n) ;
ret = true ;
}
return ret ;
}
int main(int argc, char **argv)
{
char str[] = "123" ;
char str1[] = "123" ;
cout << "原始字符串：" << str << endl;
while (nextPermutation(str, (int)strlen(str)) && next_permutation(str1, str1 + strlen(str1)))
cout << "下一个序列是：" << str << " " << str1 << endl;
return 0 ;
}
输出结果：
原始字符串：123
下一个序列是：132 132
下一个序列是：213 213
下一个序列是：231 231
下一个序列是：312 312
下一个序列是：321 321
Program ended with exit code: 0
现在代码简洁了很多，为了验证其正确性，我和STL中的next_permutation的结果做了对比，暂时发现还是可以的，另外，当只有一个元素的时候STL没有处理，本程序还是会处理一下，只是得到的还是原来结果，空字符串的时候也同样是可以胜任的。各位请起初宝贵意见！共同学习进步。
最后一题是算法题，也是一个比较老的题目，google、微软、小米等都用过该题：
这是一个被多家公司使用过的题目，也有不少人给出比较好的解释，我在此就不罗嗦了，读者可以参考：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