大厂笔试真题

1.复数相乘

2.K个一组翻转链表 

#include<iostream>
#include<vector>
#include<string>


using namespace std;

void Reverse(vector<string>& arr, int begin, int end)
{
	while (begin < end)
	{
		swap(arr[begin], arr[end]);
		begin++;
		end--;
	}
}

int main()
{
	string str;  //输入的数字很大
	int k = 0;
	vector<string> li;
	while (cin >> str)
	{
		if (str == "#")
			break;

		li.push_back(str);
	}

	cin >> k;


	for (int i = 0; i <= li.size(); i += k)
	{
		//cout << i << " " << i + k - 1 << endl;

		if((i + k ) <= li.size())
		Reverse(li, i, i + k - 1);
	}

	for (int i = 0; i < li.size()-1; ++i)
	{
		cout << li[i] << "->";
	}

	cout << li[li.size() - 1] << endl;

	return 0;
}

 3.递增子序列

• 此题需要找的递增序列可以不连续，所以可以记录遍历当前位置时的最小的两个值，如果当前位置的值大于第二小的值，则可以说明存在这样的递增序列。
• 这里需要注意，第二小的值必须在第一小的值的后面，如果更新了第一小的值，则也需要更新第二小的值。

#include<iostream>
#include<vector>
#include<string>


using namespace std;

int main()
{
	int n = 0;
	cin >> n;

	vector<int> arr(n);
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}

	int first = arr[0];
	int second = INT_MAX;

	for (int i = 1; i < n; ++i)
	{
		if (arr[i] < first)
		{
			first = arr[i];
			second = INT_MAX;
            //如果更新了最小值，则第二小的值需要在后面找，所以此处需要更新
		}
		else if (arr[i] > first && arr[i] < second)
		{
			second = arr[i];
		}
		else if (arr[i] > first && arr[i] > second)
		{
			cout << "true" << endl;
			return 0;
		}
	}

	cout << "false" << endl;

	return 0;
}

4.硬币划分 (难)

5.合并二叉树

6.求表达式 f(n)结果末尾0的个数(巧)

7.字符串压缩算法 

//1.

#include<iostream>
#include<string>

using namespace std;

int main()
{
	string target;
	while (getline(cin,target))
	{
		if (target.size() < 2)
		{
			cout << target << endl;
		}

		string ret;
		int count = 0;
		int prev = 0;
		int cur = 1;

		while (cur <= target.size())
		{
			if (target[prev] == target[cur])
			{
				count++;
			}
			else
			{
				if(count != 0)
				ret += to_string(count);

				ret += target[prev];
				count = 0;
			}
			prev++;
			cur++;
		}

		cout << ret << endl;

	}

	return 0;
}

//2.
#include <string> 
#include <iostream> 
using namespace std; 

int main()
{
	string str;
	getline(cin, str);

	//遍历字符串
	for (int i = 0; i < str.length(); i++)
	{
		//用来记录重复字符数量 
		int cnt = 0;

		//判断是不是字符串中的重复字符 
		while (str[i] == str[i + 1])
		{
			i++;
			cnt++;
		}

		//先输出压缩的字符个数 
		if (cnt != 0)
		{
			cout << cnt;
		}
		//再输出被压缩的字符 
		cout << str[i];
	}

	return 0;
}