题目描述

官方描述(中文)
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.