[LeetCode]Three Equal Parts

这道题brute force的做法就是枚举所有可能，时间复杂度O(n^3)，显然是过不了test case的。考虑这道题的数据规模，O(N^2)的解法基本上也过不了。竞赛的时候并没有想出严格意义上O(N)的解法，只是做了一些优化，最后也是将将过了test case。具体的做法是，我们用right[i]表示从i开始到末尾binary所表示的数，注意这里array的长度肯定很长所以我们用真正的数mod 1000000007的结果来表示。我们从左向右扫的时候，一直维护一个所有prefix所表示的数mod之后的值和其对应结尾的坐标，这样当我们每次只需要在prefix中找到值和right[i + 1]是否存在一样的，假设prefix结尾坐标为j，然后check[j + 1, i]表示的是否和right[i + 1]的值一样即可。这个方法虽然worst case仍然是O(n^2)，但是避免了很多不必要的计算，一定程度上优化了performance，这个方法最后也是擦着边过了test case，说明我们还是需要继续优化：

	class Solution {
	public:
	vector<int> threeEqualParts(vector<int>& A) {
	int len = A.size();
	const int MOD = 1000000007;
	//2^k % MOD
	vector<int> twos(len, 0);
	twos[0] = 1;
	for(int i = 1; i < len; ++i)
	{
	twos[i] = 2 * twos[i - 1];
	twos[i] %= MOD;
	}
	//binary value % mod when start at A[i]
	vector<int> right(len, 0);
	for(int i = 0; i < len; ++i)
	{
	if(A[len - 1 - i])
	{
	if(!i)right[len - 1] = 1;
	else
	{
	int add = twos[i];
	right[len - 1 - i] = add + right[len - i];
	right[len - 1 - i] %= MOD;
	}
	}
	else
	right[len - 1 - i] = i? right[len - i]: 0;
	}
	//presum maps to idx
	unordered_map<int, int> presums;
	presums[A[0]] = 0;
	int curr = A[0];
	for(int i = 1; i < len - 1; ++i)
	{
	int r = right[i + 1];
	if(presums.find(r) != presums.end() && convertToBinary(A, presums[r] + 1, i, twos) == r)
	return {presums[r], i + 1};
	curr = curr * 2 + A[i];
	curr %= MOD;
	presums[curr] = i;
	}
	return {-1, -1};
	}
	private:
	int convertToBinary(vector<int>& A, int i, int j, vector<int>& twos)
	{
	const int MOD = 1000000007;
	int res = 0;
	for(int k = i; k <= j; ++k)
	{
	if(A[k])res += twos[j - k];
	res %= MOD;
	}
	return res;
	}
	};

view raw Three Equal Parts.cpp hosted with ❤ by GitHub

check solution之后，一个显而易见的结论是，三个part的1的数量必须一样。所以我们统计总数k在找到每个1的数量为k / 3的区间，注意我们不允许leading和trailing zeros。之后我们比较这三个区间表示的binary是不是一样的，因为不包含leading和trailing zeros，所以我们直接比较即可。最后需要注意最后一个part的trailing zero，因为这个是无论如何在构建第三个part的时候都没法避免的，之后我们要确保第一个和第二个part之后有大于等于part3的trailing zero的话，那么part1和part2也必定可以表示成part3的样子。时间复杂度O(N)，代码如下:

	class Solution {
	public:
	vector<int> threeEqualParts(vector<int>& A) {
	int len = A.size(), cnt = 0;
	for (int i = 0; i < len; ++i)
	if (A[i] == 1)++cnt;
	if (cnt % 3)return { -1, -1 };
	if (!cnt)return{ 0, len - 1 };
	int k = cnt / 3;
	int i1 = 0, i2 = 0, i3 = 0, j1 = 0, j2 = 0, j3 = 0;
	cnt = 0;
	for (int i = 0; i < len; ++i)
	{
	if (A[i] == 1)
	{
	++cnt;
	if (cnt == 1)i1 = i;
	if (cnt == k)j1 = i;
	if (cnt == k + 1)i2 = i;
	if (cnt == 2 * k)j2 = i;
	if (cnt == 2 * k + 1)i3 = i;
	if (cnt == 3 * k)j3 = i;
	}
	}
	vector<int> v1(A.begin() + i1, A.begin() + j1 + 1);
	vector<int> v2(A.begin() + i2, A.begin() + j2 + 1);
	vector<int> v3(A.begin() + i3, A.begin() + j3 + 1);
	if (v1 != v2)return{ -1, -1 };
	if (v1 != v3)return{ -1, -1 };
	//check zeros, we don't care about leading 0s, we only care about trailing 0s
	int z1 = i2 - 1 - j1, z2 = i3 - 1 - j2, z3 = len - 1 - j3;
	if (z1 < z3 || z2 < z3)return{ -1, -1 };
	return{j1 + z3, j2 + z3 + 1};
	}
	};

view raw Three Equal Parts_2.cpp hosted with ❤ by GitHub