邻居们不控制蒲公英，怎么办？# Living
a*y
1 楼
/*
You are given a String number containing the digits of a
phone number (the number of digits, n, can be any positive integer) . To
help you memorize
the number, you want to divide it into groups of contiguous digits. Each
group must contain
exactly 2 or 3 digits. There are three kinds of groups:
• Excellent: A group that contains only the same digits. For example,
000 or 77.
• Good: A group of 3 digits, 2 of which are the same. For example, 030
, 229 or 166.
• Usual: A group in which all the digits are distinct. For example,
123 or 90.
The quality of a group assignment is defined as
2 × (number of excellent groups) + (number of good groups)
Divide the number into groups such that the quality is maximized. Design an
efficient
algorithm to return the solution that maximizes the quality.
*/
int GetScore(std::string s)
{
if (s.size() == 3)
{
if (s[0] == s[1] == s[2])
return 1;
else if (s[0] == s[1] || s[0]==s[2] || s[1] == s[2])
return 2;
}
else
if (s[0] == s[1])
return 1;
}
int GetScore(vector s)
{
int score = 0;
int noExcellent = 0;
int nogood = 0;
for (vector::iterator it = s.begin(); it != s.end(); it++)
{
cout << *it << '\t';
if (GetScore(*it) == 1)
noExcellent += 1;
else if (GetScore(*it) == 2)
nogood += 1;
}
cout << endl;
return 2*noExcellent + nogood;
}
int GroupPhoneNumber(string s, vector prefix, vector& result
,int& max)
{
if (s.size() == 1)
return -1;
if (s.size() == 0)
{
return GetScore(prefix);
}
if (s.size() == 2 || s.size() == 3)
{
prefix.push_back(s);
if (GetScore(prefix) > max)
{
result = prefix;
max = GetScore(prefix);
}
return GetScore(prefix);
}
string sub = s.substr(0, 2);
prefix.push_back(sub);
int two = GroupPhoneNumber(s.substr(2,s.size() - 2), prefix, result,max);
prefix.pop_back();
prefix.push_back(s.substr(0,3));
int three = GroupPhoneNumber(s.substr(3,s.size() - 3),prefix,result,max);
return two > three ? two : three;
}
You are given a String number containing the digits of a
phone number (the number of digits, n, can be any positive integer) . To
help you memorize
the number, you want to divide it into groups of contiguous digits. Each
group must contain
exactly 2 or 3 digits. There are three kinds of groups:
• Excellent: A group that contains only the same digits. For example,
000 or 77.
• Good: A group of 3 digits, 2 of which are the same. For example, 030
, 229 or 166.
• Usual: A group in which all the digits are distinct. For example,
123 or 90.
The quality of a group assignment is defined as
2 × (number of excellent groups) + (number of good groups)
Divide the number into groups such that the quality is maximized. Design an
efficient
algorithm to return the solution that maximizes the quality.
*/
int GetScore(std::string s)
{
if (s.size() == 3)
{
if (s[0] == s[1] == s[2])
return 1;
else if (s[0] == s[1] || s[0]==s[2] || s[1] == s[2])
return 2;
}
else
if (s[0] == s[1])
return 1;
}
int GetScore(vector
{
int score = 0;
int noExcellent = 0;
int nogood = 0;
for (vector
{
cout << *it << '\t';
if (GetScore(*it) == 1)
noExcellent += 1;
else if (GetScore(*it) == 2)
nogood += 1;
}
cout << endl;
return 2*noExcellent + nogood;
}
int GroupPhoneNumber(string s, vector
,int& max)
{
if (s.size() == 1)
return -1;
if (s.size() == 0)
{
return GetScore(prefix);
}
if (s.size() == 2 || s.size() == 3)
{
prefix.push_back(s);
if (GetScore(prefix) > max)
{
result = prefix;
max = GetScore(prefix);
}
return GetScore(prefix);
}
string sub = s.substr(0, 2);
prefix.push_back(sub);
int two = GroupPhoneNumber(s.substr(2,s.size() - 2), prefix, result,max);
prefix.pop_back();
prefix.push_back(s.substr(0,3));
int three = GroupPhoneNumber(s.substr(3,s.size() - 3),prefix,result,max);
return two > three ? two : three;
}
