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

谁借莪１个温暖的怀抱￠ 2022-09-17 11:28 165阅读 0赞

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

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

![SouthEast][]

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

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

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修改）：

![SouthEast 1][]

另外，非常感谢[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题：

![SouthEast 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为例子进行分析：

原始序列：

![SouthEast 3][]

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

![SouthEast 4][]

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

![SouthEast 5][]

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

![SouthEast 6][]（其实这里不用排序，因为原来就是有序的，只不过是从左到右是从大到小排序，我们只需要翻转一下就行了。我也会给你出相应的修改后的程序，下面用蓝字提示的地方。突然感觉自己原来的思路真是弱爆了，大家不要笑话）2014.3.24 更改。

到此，我们就得到了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][http_blog.csdn.net_hguisu_article_details_7880288]和[https://github.com/crazykeyboard/Bit-Map][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、微软、小米等都用过该题：

![SouthEast 7][]

这是一个被多家公司使用过的题目，也有不少人给出比较好的解释，我在此就不罗嗦了，读者可以参考：[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/][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][http_blog.csdn.net_doufei_ccst_article_details_12779831]

[SouthEast]: /images/20220828/cc6a206f977d41c59288fce64021a513.png
[SouthEast 1]: /images/20220828/67eaa83f4bbc4552a31ce643b40b8604.png
[tadonis]: http://blog.csdn.net/tadonis
[SouthEast 2]: /images/20220828/def2d7cce43e4cc0a7a997da2505e914.png
[SouthEast 3]: /images/20220828/ada971dca74e41aebff5694bce3f902f.png
[SouthEast 4]: /images/20220828/fc8d4d8b4c7442e9a01631f90df02f96.png
[SouthEast 5]: /images/20220828/9da06992470c41d8a2992efb1ee36001.png
[SouthEast 6]: /images/20220828/7c0cf46aec6e475bbcb0bcc7c4897473.png
[http_blog.csdn.net_hguisu_article_details_7880288]: http://blog.csdn.net/hguisu/article/details/7880288
[https_github.com_crazykeyboard_Bit-Map]: https://github.com/crazykeyboard/Bit-Map
[SouthEast 7]: /images/20220828/1190c0d5c766494e9c021f025788ace2.png
[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]: 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/
[http_blog.csdn.net_doufei_ccst_article_details_12779831]: http://blog.csdn.net/doufei_ccst/article/details/12779831