友塔游戏客户端笔试题

 输入:
    5 2 2 4 8 9 5 3 5
    3 2 2 5 7 5 2 1 2
    1 2 2 2 1 1 3 2 1
    2 2 5 1 2 5 8 1 8
    6 1 2 3 7 9 5 6 5
    4 3 2 1 5 8 4 5 4
    8 4 5 5 4 4 5 8 7
    2 1 3 2 1 5 8 7 9
    9 2 4 9 8 7 5 3 1

    输出:81-8=73

#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;

string crStr(int row, int col)
{
	return to_string(row) + '-' + to_string(col);
}

bool isValid(unordered_set<string>& hashset, pair<int, int>&p)
{
	int curRow = p.first, curCol = p.second;
	//竖
	int topRow = curRow, downRow = curRow;
	while (hashset.find(crStr(topRow - 1, curCol)) != hashset.end() && downRow - topRow + 1 <= 2)--topRow;
	while (hashset.find(crStr(downRow + 1, curCol)) != hashset.end() && downRow - topRow + 1 <= 2)++downRow;
	if (downRow - topRow + 1 > 2)
		return true;

	//横
	int leftCol = curCol, rightCol = curCol;
	while (hashset.find(crStr(curRow, leftCol - 1)) != hashset.end() && rightCol - leftCol + 1 <= 2)--leftCol;
	while (hashset.find(crStr(curRow, rightCol + 1)) != hashset.end() && rightCol - leftCol + 1 <= 2)++rightCol;
	if (rightCol - leftCol + 1 > 2)
		return true;

	return false;
}

void myAdd(vector<vector<int>>& input, queue<pair<int, int>>& equalque, unordered_set<string> &hashset, int row, int col)
{
	string tmp = crStr(row, col);
	if (hashset.find(tmp) == hashset.end())
	{
		hashset.insert(tmp);
		equalque.push(pair<int, int>(row, col));
	}
}

int getNum(vector<vector<int>>& input)
{
	if (input.empty())return 0;
	int rows = input.size();
	int cols = input[0].size();
	int res = rows * cols;
	for (int i = 0; i < rows; i++)
	{
		for (int j = 0; j < cols; j++)
		{
			int anchor = input[i][j];
			if (anchor == -1)continue;
			//找出所有值相同的块,暂且标志为0,并加入哈希表与数组中为剔除工作做准备
			queue<pair<int, int>> equalque;
			vector<pair<int, int>>equalVec;
			unordered_set<string> hashset;
			myAdd(input, equalque, hashset, i, j);
			while (!equalque.empty())
			{
				int curRow = equalque.front().first, curCol = equalque.front().second;
				input[curRow][curCol] = 0;
				equalVec.push_back(equalque.front());
				equalque.pop();
				if (curRow + 1 < rows && input[curRow + 1][curCol] == anchor)myAdd(input, equalque, hashset, curRow + 1, curCol);
				if (curRow - 1 >= 0 && input[curRow - 1][curCol] == anchor)myAdd(input, equalque, hashset, curRow - 1, curCol);
				if (curCol + 1 < cols &&  input[curRow][curCol + 1] == anchor)myAdd(input, equalque, hashset, curRow, curCol + 1);
				if (curCol - 1 >= 0 && input[curRow][curCol - 1] == anchor)myAdd(input, equalque, hashset, curRow, curCol - 1);
			}
			res -= equalVec.size();
			//剔除横竖没有连续超过3个相同的
			for (auto p : equalVec)
				if (!isValid(hashset, p))
					res++;

			//剔除完毕,将区块值全部更新为-1
			for (auto p : equalVec)input[p.first][p.second] = -1;
		}
	}
	return res;
}

int main()
{
	/*
	9*9矩阵中均为正数,行列中值连续出现超过3个相同的就消除掉,问一次消除后剩下多少个数
	输入:
	5 2 2 4 8 9 5 3 5
	3 2 2 5 7 5 2 1 2
	1 2 2 2 1 1 3 2 1
	2 2 5 1 2 5 8 1 8
	6 1 2 3 7 9 5 6 5
	4 3 2 1 5 8 4 5 4
	8 4 5 5 4 4 5 8 7
	2 1 3 2 1 5 8 7 9
	9 2 4 9 8 7 5 3 1

	输出:81-8=73

	我的想法:和剑指offer还是哪个地方的题很相似,题目是说一个01矩阵中找出所有相连的1的区块有多少个,这个突然找不到出处了.
	此题要比原题难度高上一点,原题可以一个感染函数小小几行递归就将所有值相同的区块找出来,然后++得到所有区块;
	此题感染递归就不方便了,可以非递归深度优先或非递归广度优先将当前操作的值周围与其相同的数全部先找出来,然后遍历剔除不符合横竖都至少3个相同的数.
	当这一步骤完成后,将所有涉及访问过的数全部设为-1,表示已经访问过以后不需要关心这块区域,遇到的话直接返回即可.
	对矩阵遍历一遍,每个数只会被访问一次,假设矩阵一共n个数,则时间复杂度O(n),但因为在剔除不符合横竖至少3个数的过程也需要
	遍历,若整个矩阵全是相同数,则遍历到第一个数时回溯的代码段最终会将整个矩阵都纳入考虑,然后剔除过程复杂度O(n),总共是O(n^2)
	因此假设矩阵一共有n个数,则复杂度在O(n)到O(n^2)之间.
	*/
	int n = 9;
	vector<vector<int>> input(n);
	for (int i = 0; i < n; i++)
	{
		input[i].resize(n);
		for (int j = 0; j < n; j++)
		{
			int tmp = 0;
			scanf("%d", &tmp);
			input[i][j] = tmp;
		}
	}
	printf("%d", getNum(input));
}

#include <algorithm>
#include <string>
#include <vector>
using namespace std;

bool mintomax(pair<int, int>& p1, pair<int, int>&p2)
{
	return p1.first < p2.first;
}

int main()
{
	//比如测试用例:初始假设n帧,并且接下来有k条记录,这k条(a,b)记录分别为第a帧时情况改变,此时预测进度条结束时的帧为第b帧
	/*输入:
	10 3
	6  12
	4  8
	8  10
	输出:
	0.10
	0.20
	0.30
	0.40
	0.55
	0.70
	0.75
	0.80
	0.90
	1.00
	*/
	int n,k = 0;
	scanf("%d", &n); scanf("%d", &k);

	vector<pair<int,int>> vec(k);
	for (int i = 0; i < k; i++)
	{
		pair<int, int> tmp;
		scanf("%d", &tmp.first); scanf("%d", &tmp.second);
		vec[i] = tmp;
	}
	sort(vec.begin(),vec.end(), mintomax);

	float progress = 0;
	float speed = 1.0f / n;
	int curFrame = 0,vecInd=0;

	while (progress < 1)
	{
		if (vecInd<k&&vec[vecInd].first == curFrame)
			speed = (1 - progress) / (vec[vecInd++].second - curFrame);
		progress += speed;
		++curFrame;

		float outputProgress = progress;
		outputProgress = round(outputProgress * 100) / 100;
		printf("%.2f\n", outputProgress);
	}
}

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool getEqual(vector<int>&vec, int index, int&left, int&right)
{
	if (index < 0 || index >= vec.size()||vec.size()==1)return false;
	if (index == 0)
	{
		if (vec[1] == vec[0])
		{
			left = 0, right = 1;
			while (right + 1 < vec.size() && vec[right + 1] == vec[right])right++;
			return true;
		}
		return false;
	}
	if (index == vec.size() - 1)
	{
		if (vec[index] == vec[index - 1]) {
			right = index, left = index - 1;
			while (left - 1 >= 0 && vec[left] == vec[left - 1])left--;
			return true;
		}
		return false;
	}
	left = index, right = index;
	if (vec[index] != vec[index + 1] && vec[index] != vec[index - 1])return false;
	while (left - 1 >= 0 && vec[left - 1] == vec[left])left--;
	while (right + 1 < vec.size() && vec[right + 1] == vec[right])right++;
	return true;
}

int _solution(vector<int>vec, int index)
{
	if (index < 0 || index >= vec.size())return 0;
	int notTake =INT_MIN;
	int take = INT_MIN;
	int left, right;
	if (getEqual(vec, index, left, right))
	{
		vector<int> tmp;
		for (int i = 0; i < left; i++)tmp.push_back(vec[i]);
		for (int i = right + 1; i < vec.size(); i++)tmp.push_back(vec[i]);
		take=_solution(tmp, 0)+(right-left+1)*(right - left + 1);
		notTake = _solution(vec, right + 1);
	}
	else
	{
		notTake= _solution(vec, index + 1);
	}
	int max=(notTake < take ? take : notTake);
	if (max==INT_MIN)max = 0;
	return max;
}

int solution(vector<int>& vec)
{
	return _solution(vec, 0);
}

int main()
{
	/*测试用例:
	6
	1 2 2 3 3 2
	输出:13
	*/
	int n = 0;
	scanf("%d", &n);
	vector<int> input(n);
	for (int i = 0; i < n; i++)
	{
		int tmp = 0;
		scanf("%d", &tmp);
		input[i] = tmp;
	}
	cout << solution(input);
}