【华为2019年校园招聘】2019-4-17 软件题-最大时间问题

输入描述

输入为一个整数数组，数组内有六个整数。
输入整数数组长度为6， 不需要考虑其他长度，元素值为0或者正整数，6个数字每个数字只能使用一次。

输出描述

输出为一个24进制格式的时间，或者字符串“invalid”

示例：

输入
[0,2,3,0,5,6]
输出
23:56:00

输入
[9,9,9,9,9,9]
输出
invalid

解题思路：
这道题要求C/C++运行时间小于3秒，感觉是可以用暴搜的。因为考之前没刷过题，图简单就直接上暴搜了。
基本思路是对于输入的6个数字，遍历所有的排列情况，因为24进制时间本身对时、分、秒数字有大小约束，所以加上剪枝实际上不需要遍历所有的情况。对于每一种合法的时间相互之间比较大小（换算成秒）

代码

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

using namespace std;

// 根据输入的6位时间表示计算其秒数（以秒为单位的数字）
double absolute_time(const vector<int>& nums)
{
	int hour = nums[0] * 10 + nums[1];
	int minu = nums[2] * 10 + nums[3];
	int sec = nums[4] * 10 + nums[5];

	if (hour >= 24 || minu >= 60 || sec >= 60)
	{
		return -1;
	}
	else
	{
		return hour * 3600 + minu * 60 + sec;
	}
}



int main(void)
{
	string array;
	while (getline(cin, array))
	{
		if (array.empty())
		{
			break;
		}
		
		// 解析输入的字符串，转为包含6个数字的向量
		vector<int> nums;
		for (int i = 1; i < 12; i = i + 2)
		{
			int num = array[i] - '0';
			nums.push_back(num);
		}
	
		//遍历这6个数字可以组成的所有的合法的时间
		double max_time = -1;
		vector<int> final;
		for (int i0 = 0; i0 < 6; ++i0)
		{
			if (nums[i0] > 2)  //hour的十位不能超过2
			{
				continue;
			}
			for (int i1 = 0; i1 < 6; ++i1)
			{
				if (i1 == i0)
				{
					continue;
				}
				if (nums[i0] * 10 + nums[i1] >= 24)  //hour不超过24
				{
					continue;
				}

				for (int i2 = 0; i2 < 6; ++i2)
				{
					if ((i2 == i1) || (i2 == i0))
					{
						continue;
					}
					if (nums[i2] >= 6)  //minute十位不超过6
					{
						continue;
					}
					for (int i3 = 0; i3 < 6; ++i3)
					{
						if ((i3 == i2) || (i3 == i1) || (i3 == i0))
						{
							continue;
						}

						if (nums[i2] * 10 + nums[i3] >= 60)
						{
							continue;
						}
						for (int i4 = 0; i4 < 6; ++i4)
						{
							if ((i4 == i3) || (i4 == i2) || (i4 == i1) || (i4 == i0))
							{
								continue;
							}

							if (nums[i4] >= 6)   //second十位不超过6
							{
								continue;
							}
							for (int i5 = 0; i5 < 6; ++i5)
							{
								if ((i5 == i4) || (i5 == i3) || (i5 == i2) || (i5 == i1) || (i5 == i0))
								{
									continue;
								}

								if (nums[i4] * 10 + nums[i5] >= 60)
								{
									continue;
								}

								int sum = i0 + i1 + i2 + i3 + i4 + i5;
								if (sum != 15)  
								{
									continue;
								}

								vector<int> cur_num;
								cur_num.push_back(nums[i0]);
								cur_num.push_back(nums[i1]);
								cur_num.push_back(nums[i2]);
								cur_num.push_back(nums[i3]);
								cur_num.push_back(nums[i4]);
								cur_num.push_back(nums[i5]);
								double cur = absolute_time(cur_num);
								if (cur > max_time)
								{
									max_time = cur;
									final.assign(cur_num.begin(), cur_num.end());
								}
							}
						}
					}
				}
			}
		}
		
		if (max_time > -1)
		{
			cout << final[0] << final[1] << ":" << final[2] << final[3] << ":";
			cout << final[4] << final[5] << endl;
		}
		else
		{
			cout << "invalid" << endl;
		}

	}
	return 0;
}