今日头条2017后端工程师笔试题

「爱情、让人受尽委屈。」 2022-05-15 09:41 220阅读 0赞

**1、最大映射**

有 n 个字符串，每个字符串都是由 A-J 的大写字符构成。现在你将每个字符映射为一个 0-9 的数字，不同字符映射为不同的数字。这样每个字符串就可以看做一个整数，唯一的要求是这些整数必须是正整数且它们的字符串不能有前导零。现在问你怎样映射字符才能使得这些字符串表示的整数之和最大？

**输入描述:**

每组测试用例仅包含一组数据，每组数据第一行为一个正整数 n ， 接下来有 n 行，每行一个长度不超过 12 且仅包含大写字母 A-J 的字符串。 n 不大于 50，且至少存在一个字符不是任何字符串的首字母。

**输出描述:**

输出一个数，表示最大和是多少。

**输入例子:**

ABC

BCA

**输出例子:**

1875

**2、木棒拼图**

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

初始集合是空的，有两种操作，要么给集合添加一个长度为 L 的木棒，要么删去集合中已经有的某个木棒。每次操作结束后你都需要告知是否能用集合中的这些木棒构成一个简单多边形。

**输入描述:**

每组测试用例仅包含一组数据，每组数据第一行为一个正整数 n 表示操作的数量(1 ≤ n ≤ 50000) ， 接下来有n行，每行第一个整数为操作类型 i (i ∈ \{1,2\})，第二个整数为一个长度 L(1 ≤ L ≤ 1,000,000,000)。如果 i=1 代表在集合内插入一个长度为 L 的木棒，如果 i=2 代表删去在集合内的一根长度为 L 的木棒。输入数据保证删除时集合中必定存在长度为 L 的木棒，且任意操作后集合都是非空的。

**输出描述:**

对于每一次操作结束有一次输出，如果集合内的木棒可以构成简单多边形，输出 "Yes" ，否则输出 "No"。

**输入例子:**

1 1

2 1

1 2

**输出例子:**

Yes

**3、魔法权值**

给出 n 个字符串，对于每个 n 个排列 p，按排列给出的顺序(p\[0\] , p\[1\] … p\[n-1\])依次连接这 n 个字符串都能得到一个长度为这些字符串长度之和的字符串。所以按照这个方法一共可以生成 n! 个字符串。

一个字符串的权值等于把这个字符串循环左移 i 次后得到的字符串仍和原字符串全等的数量，i 的取值为 \[1 , 字符串长度\]。求这些字符串最后生成的 n! 个字符串中权值为 K 的有多少个。

注：定义把一个串循环左移 1 次等价于把这个串的第一个字符移动到最后一个字符的后面。

**输入描述:**

每组测试用例仅包含一组数据，每组数据第一行为两个正整数 n, K ， n 的大小不超过 8 ， K 不超过 200。接下来有 n 行，每行一个长度不超过 20 且仅包含大写字母的字符串。

**输出描述:**

输出一个整数代表权值为 K 的字符串数量。

**输入例子:**

3 2

RAAB

**输出例子:**

#include<iostream>
    #include<string>
    using namespace std;
    
    bool IsWeightK(string s, int k)
    {
    	int count = 0;
    	for (int i = 1; i <= s.length(); i++)
    	{
    		string temp = s.substr(i) + s.substr(0,i);
    		if (temp == s)
    		{
    			count++;
    			if (count > k)
    				return false;
    		}
    	}
    	if (count == k)
    		return true;
    	else
    		return false;
    }
    
    void PermutationHelp(string* str, int length, int begin, int k, int& res)
    {
    	if (begin == length)
    	{
    		string allstr = "";
    		for (int j = 0; j < length; j++)
    			allstr += str[j];
    		if (IsWeightK(allstr, k))
    			res++;
    	}
    	else
    	{
    		for (int i = begin; i < length; i++)
    		{
    			string temp1 = str[begin];
    			str[begin] = str[i];
    			str[i] = temp1;
    			PermutationHelp(str, length, begin + 1, k, res);
    			string temp2 = str[begin];
    			str[begin] = str[i];
    			str[i] = temp2;
    		}
    	}
    }
    
    int main() {
    	int n, k;
    	cin >> n >> k;
    	int res = 0;
    	string *arrstr = new string[n];
    	for (int i = 0; i < n; i++)
    		cin >> arrstr[i];
    	PermutationHelp(arrstr,n,0,k,res);
    	delete[] arrstr;
    	cout << res << endl;
    	system("pause");
    }

#include<iostream>
    #include<string>
    #include<vector>
    #include<numeric>
    #include<algorithm>
    using namespace std;
    
    bool IsWeightK(string s, int k)
    {
    	int count = 0;
    	int length = s.length();
    	string two = s + s;
    	for (int i = 1; i <= length; i++)
    	{
    		string temp = two.substr(i,length);
    		if (temp == s)
    		{
    			count++;
    			if (count > k)
    				return false;
    		}
    	}
    	if (count == k)
    		return true;
    	else
    		return false;
    }
    
    int main() 
    {
    	int n, k;
    	cin >> n >> k;
    	int res = 0;
    	vector<int> pos(n);
    	for (int i = 0; i < n; i++)
    		pos[i] = i;
    	vector<string> str(n);
    	for (int i = 0; i < n; i++)
    		cin >> str[i];
    	do
    	{
    		string temp = "";
    		for (int i : pos)
    			temp += str[i];
    		if (IsWeightK(temp, k))
    			res++;
    	} while (next_permutation(pos.begin(),pos.end()));
    	cout << res << endl;
    	system("pause");
    }

**4、或与加**

给定 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。

**输入描述:**

每组测试用例仅包含一组数据，每组数据为两个正整数 x , k。 满足 0 < x , k ≤ 2,000,000,000。

**输出描述:**

输出一个数y。

**输入例子:**

5 1

**输出例子:**