题目描述
官方描述(中文)
2021/09/09每日一题
思路
该题的解题思路没有什么比较高深的算法,主要是对数据的处理。思路梳理比较复杂。
代码
class Solution
{
private:
std::string __GetFullString(const std::vector<string>& fullVec, const string& fullString, const int maxWidth)
{
if (fullVec.size() == 1)
{
return fullString + string(maxWidth - fullString.length(), ' ');
}
int numOfSpace = maxWidth - fullString.length();
auto aveSpace = numOfSpace / ((int)(fullVec.size()-1));
auto moreSpace = numOfSpace % ((int)(fullVec.size()-1));
string res;
for (int i = 0; i < fullVec.size(); ++i)
{
res = res + fullVec[i];
if (i == fullVec.size() - 1)break;
res = res + string(aveSpace, ' ') + (moreSpace-- > 0 ? " " : "");
}
return res;
}
std::string __GetLastLine(const std::vector<std::string>& fullVec, const int maxWidth)
{
string lastLine;
for (auto iter : fullVec)
{
lastLine = lastLine + iter + " ";
}
lastLine = lastLine.substr(0, lastLine.length() - 1);
return lastLine + string(maxWidth - lastLine.length(), ' ');
}
public:
vector<string> fullJustify(vector<string>& words, int maxWidth)
{
if (maxWidth <= 0)return{};
vector<string>res;
std::vector<string> fullVec;
int currPos{ 0 };
string fullString;
for (int i = 0; i < words.size(); ++i)
{
if (currPos + words[i].length() > maxWidth)
{
res.push_back(__GetFullString(fullVec, fullString, maxWidth));
fullVec.clear();
fullString.clear();
currPos = 0;
}
fullString += words[i];
fullVec.push_back(words[i]);
currPos += words[i].length() + 1;
}
res.push_back(__GetLastLine(fullVec, maxWidth));
return res;
}
};
Q.E.D.