[LeetCode]Candy Crush

这道题思路是分两部分，首先我们遍历所有的行和列，标记所有应该消去的点；第二部就是对于每一行，我们把每个元素尽量向下shift。这道题的难点在于如何做到in place，也就是不用额外的空间。
首先在我们标记要删除节点的时候不能简单地标记为0，因为可能会出现题目例子当中行和列联系的三个块share同一个块的情况。这里因为所有的tile种类都是大于0的，我们标记成负的即可，这样在我们之后再扫的时候取绝对值也不会漏掉。
第二点就是如何in place向下shift，这里我们用双指针即可，一个指针指向下一个应该填上的位置，另一个指向下一个不为0或者负数的tile。当然，由于第一次消除之后可能会产生新的可以消除的连续块，我们继续重复知道无法消去。时间复杂度 worst case O(m * n * m * n)，代码如下:

	class Solution {
	public:
	vector<vector<int>> candyCrush(vector<vector<int>>& board) {
	while (true)
	{
	bool hasChange = false;
	int m = board.size(), n = m ? board[0].size() : 0;
	//each row
	for (int i = 0; i < m; ++i)
	{
	int j = 0;
	while (j < n)
	{
	int k = j + 1;
	while (k < n && board[i][j] == board[i][k])++k;
	if (board[i][j] && k - j >= 3)
	{
	hasChange = true;
	for (int x = j; x < k; ++x)
	board[i][x] = -board[i][x];//just set it to be minus since it can be part of the col
	}
	j = k;
	}
	}
	//each col
	for (int j = 0; j < n; ++j)
	{
	int i = 0;
	while (i < m)
	{
	int k = i + 1;
	while (k < m && abs(board[i][j]) == abs(board[k][j]))++k;
	if (board[i][j] && k - i >= 3)
	{
	hasChange = true;
	for (int x = i; x < k; ++x)
	board[x][j] = board[x][j] < 0 ? board[x][j] : -board[x][j];
	}
	i = k;
	}
	}
	if (!hasChange)break;
	//rearrange each col
	for (int j = 0; j < n; ++j)
	{
	int i = m - 1, k = m - 1;
	while (k >= 0)
	{
	while (k >= 0 && board[k][j] <= 0)--k;
	if (k < 0)break;
	board[i--][j] = board[k--][j];
	}
	while (i >= 0)board[i--][j] = 0;
	}
	}
	return board;
	}
	};

view raw Candy Crush.cpp hosted with ❤ by GitHub