【广度优先】【模拟】838推多米诺

本周推荐阅读

C++二分算法：得到子序列的最少操作次数

LeetCode推多米诺

n 张多米诺骨牌排成一行，将每张多米诺骨牌垂直竖立。在开始时，同时把一些多米诺骨牌向左或向右推。
每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。
如果一张垂直竖立的多米诺骨牌的两侧同时有多米诺骨牌倒下时，由于受力平衡， 该骨牌仍然保持不变。
就这个问题而言，我们会认为一张正在倒下的多米诺骨牌不会对其它正在倒下或已经倒下的多米诺骨牌施加额外的力。
给你一个字符串 dominoes 表示这一行多米诺骨牌的初始状态，其中：
dominoes[i] = ‘L’，表示第 i 张多米诺骨牌被推向左侧，
dominoes[i] = ‘R’，表示第 i 张多米诺骨牌被推向右侧，
dominoes[i] = ‘.’，表示没有推动第 i 张多米诺骨牌。
返回表示最终状态的字符串。
示例 1：
输入：dominoes = “RR.L”
输出：“RR.L”
解释：第一张多米诺骨牌没有给第二张施加额外的力。
示例 2：
输入：dominoes = “.L.R…LR…L…”
输出：“LL.RR.LLRRLL…”
提示：
n == dominoes.length
1 <= n <= 105
dominoes[i] 为 ‘L’、‘R’ 或 ‘.’
![(https://img-blog.csdnimg.cn/7ddeab69c86f43ee9c3a704d603a85f4.png#pic_center)
在这里插入图片描述

初始想法

将LR放到栈中。

如果遇到两个L则两个L之间的全部L ，出栈入栈
栈顶L，新遇到R不处理，新元素入栈
如果遇到两个R两个R之间全部R，出栈入栈
栈顶R 新遇到LRL之间离R近的R，离L近的L，相等的不边，出栈入栈

结束时，栈有如下几种情况

LR
L
R

分情况讨论过于复杂，放弃。

可行的方案

时间复杂度： O(n) ，两轮循环时间复杂度都是O(n)。

分析

向左倒右边必须有牌向左倒，且不被向右倒的牌挡住
向右倒左边必须有牌向右倒，且不被向左倒的牌挡住
左右倒距离左倒的近，左倒；距离右倒的近，右倒；距离相等，直立

变量解释

vRight距离最近的向右倒的牌的索引
iLeft距离最近向左倒的牌的索引

核心代码

class Solution {
public:
	string pushDominoes(string dominoes) {
		m_c = dominoes.length();
		vector<int> vRight(m_c, -1);
		{
			int iRight = -1;
			for (int i = 0; i < m_c; i++)
			{
				if ('R' == dominoes[i])
				{
					iRight = i;
				}
				if ('L' == dominoes[i])
				{
					iRight = -1;
				}
				vRight[i] = iRight;
			}
		}
		int iLeft = -1;
		string s(m_c, '.');
		for (int i = m_c - 1; i >= 0; i--)
		{
			if ('L' == dominoes[i])
			{
				iLeft = i;
			}
			if ('R' == dominoes[i])
			{
				iLeft = -1;
			}			
			if (iLeft >= 0)
			{
				if (vRight[i] >= 0)
				{
					int tmp = (iLeft - i) - (i - vRight[i]);
					if (tmp > 0)
					{
						s[i] = 'R';
					}
					else if (tmp < 0)
					{
						s[i] = 'L';
					}
				}
				else
				{
					s[i] = 'L';
				}
			}
			else if(vRight[i] >= 0)
			{
				s[i] = 'R';
			}
		}
		return s;
	}
	int m_c;
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60

测试用例

template <class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

template <class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}
}


int main()
{
	string dominoes;
	string res;
	{
		Solution slu;
		dominoes = "...";
		res = slu.pushDominoes(dominoes);
		Assert(res, string("..."));
	}
	{
		Solution slu;
		dominoes = ".L.";
		res = slu.pushDominoes(dominoes);
		Assert(res, string("LL."));
	}
	{
		Solution slu;
		dominoes = ".R.";
		res = slu.pushDominoes(dominoes);
		Assert(res, string(".RR"));
	}
	{
		Solution slu;
		dominoes = "R";
		res = slu.pushDominoes(dominoes);
		Assert(res, string("R"));
	}
	{
		Solution slu;
		dominoes = "L";
		res = slu.pushDominoes(dominoes);
		Assert(res, string("L"));
	}
	{
		Solution slu;
		dominoes = ".";
		res = slu.pushDominoes(dominoes);
		Assert(res, string("."));
	}
	{
		Solution slu;		
		dominoes = "RR.L";
		res = slu.pushDominoes(dominoes);
		Assert(res, string("RR.L"));
	}
	{
		Solution slu;
		dominoes = ".L.R...LR..L..";
		res = slu.pushDominoes(dominoes);
		Assert(res, string("LL.RR.LLRRLL.."));
	}
	
	//CConsole::Out(res);
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76

深度优先搜索

分析

时间复杂度： O(n) ，每个元素最多出队入队一次。

变量解释

que记录当前回合左到或右倒的元素索引
mIndexValue键：当前回合受到力的牌，值：当前回合受到力。1，向左的力;0,没受到力或同时受到左右的力。-1,受到向右的力。

注意： 力值能让没倒的牌倒下，无法让倒下的牌转变方向。

if ('.' != dominoes[it.first])
			{
				continue;
			}
  • 1
  • 2
  • 3
  • 4

代码

class Solution {
public:
	string pushDominoes(string dominoes) {
		m_c = dominoes.length();
		std::queue<int> que;
		for (int i = 0; i < m_c; i++)
		{
			if ('.' != dominoes[i])
			{
				que.emplace(i);
			}
		}
		while (que.size())
		{
			unordered_map<int, int> mIndexValue;
			while (que.size())
			{
				const int inx = que.front();
				que.pop();
				if ('L' == dominoes[inx])
				{
					if (inx > 0)
					{
						mIndexValue[inx - 1]++;
					}
				}
				else 
				{
					if (inx + 1 < m_c)
					{
						mIndexValue[inx + 1]--;
					}
				}
			}
			for (const auto& it : mIndexValue)
			{
				if ('.' != dominoes[it.first])
				{
					continue;
				}
				if (1 == it.second)
				{
					dominoes[it.first] = 'L';
					que.emplace(it.first);
				}
				if (-1 == it.second)
				{
					dominoes[it.first] = 'R';
					que.emplace(it.first);
				}
			}
		}
		return dominoes;
	}
	int m_c;
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56

模拟

分析

时间复杂度?(n)。
枚举所有连续的直立牌，根据两边的受力方向分情况讨论。为了简化问题：可以想象在最左边增加L，最右边增加R。

LL全部左倒
LR全部不边
RL左边右倒，右边左倒
RR全部右倒

代码

class Solution {
public:
	string pushDominoes(string dominoes) {
		m_c = dominoes.length();
		int iPre = -1;
		for (int i = 0; i < m_c; i++)
		{
			if ('.' != dominoes[i])
			{
				Do(dominoes,iPre, i);
				iPre = i;
			}
		}	
		Do(dominoes, iPre, m_c);
		return dominoes;
	}
	void Do(string& s, int left, int right)
	{
		const char chL = (left < 0) ? 'L' : s[left];
		const char chR = (right < m_c) ? s[right] : 'R';
		if ('L' == chL)
		{
			if ('L' == chR)
			{
				for (int i = left + 1; i < right; i++)
				{
					s[i] = 'L';
				}
			}
			else
			{
				//什么都不干
			}
		}
		else
		{
			if ('L' == chR)
			{
				for (int i = 1; i <= (right - left - 1) / 2; i++)
				{
					s[left + i] = 'R';
					s[right - i] = 'L';
				}
			}
			else
			{
				for (int i = left + 1; i < right; i++)
				{
					s[i] = 'R';
				}
			}
		}
	}
	int m_c;
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55

2022年12月旧版

class Solution {
public:
string pushDominoes(string dominoes) {
c = dominoes.length();
std::unordered_map mPreIndexValue;
for (int i = 0; i < c; i++)
{
const char& ch = dominoes[i];
Test(mPreIndexValue,ch, i);
}
while (mPreIndexValue.size())
{
std::unordered_map dp;
for (auto& it : mPreIndexValue)
{
if (0 == it.second)
{
continue;
}
if (‘.’ != dominoes[it.first])
{
continue;
}
dominoes[it.first] = (1 == it.second) ? ‘L’ : ‘R’;
Test(dp,dominoes[it.first], it.first);
}
dp.swap(mPreIndexValue);
}
return dominoes;
}
void Test(std::unordered_map& m,const char& ch, int i)
{
if (‘L’ == ch)
{
if (i > 0 )
{
m[i - 1]++;
}
}
else if (‘R’ == ch)
{
if (i + 1 < c)
{
m[i + 1]–;
}
}
}
int c;

};

2023年11月旧版

class Solution {
public:
string pushDominoes(string dominoes) {
int n = dominoes.size();
vector vRight(n, -1);
{
int iR = -1;
for (int i = 0; i < n; i++)
{
if (‘R’ == dominoes[i])
{
iR = i;
}
else if (‘L’ == dominoes[i])
{
iR = -1;
}
vRight[i] = iR;
}
}
int iLeft = -1;
string s(n, ‘.’);
for (int i = n - 1; i >= 0; i–)
{
if (‘L’ == dominoes[i])
{
iLeft = i;
}
else if (‘R’ == dominoes[i])
{
iLeft = -1;
}
if ((iLeft >= 0)&&(vRight[i] >= 0 ))
{
const int tmp = (iLeft - i) - (i - vRight[i]);
if (tmp > 0)
{
s[i] = ‘R’;
}
if (tmp < 0)
{
s[i] = ‘L’;
}
}
else if (iLeft >= 0)
{
s[i] = ‘L’;
}
else if (vRight[i] >= 0)
{
s[i] = ‘R’;
}
}
return s;
}
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：

VS2022 C++17

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览60496 人正在系统学习中
群中有博文配套源码
QQ群名片
注：本文转载自blog.csdn.net的闻缺陷则喜何志丹的文章"https://blog.csdn.net/he_zhidan/article/details/134611565"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！