leetcode 838

我发现我非常不擅长解决这种 ummm充满了各种逻辑判断的问题 orz！ 因为总是漏少几种情况（很绝望orz）

这道题我是这么判断的

temp为更改后的字符串，dominoes为原字符串

对于原字符串，只需要改变“.”的状态就好了

设置两个指针 low，high

扫描到当前字符“.”时，low从“.”左边往前扫，high从“.”右边往后扫

存在以前几种情况

1. dominoes[high]=='L'&&dominoes[low]!='R'

   需要将“.”变为“L”

2.dominoes[low]=='R'&&dominoes[high]!='L'

   需要将“.”变为“R”

3. dominoes[low]=='.'&&dominoes[high]=='.'

   同时移动low和high

4. dominoes[low]=='L'&&dominoes[high]=='.'

   只需要移动high指针，因为可能之后会出现L这种情况

5. dominoes[low]=='.'&&dominoes[high]=='R'

  只需要移动low指针，因为可能前面会有R这种情况

6. 其他情况，是不需要改变“.”的状态的

最后对改变后的temp字符串考虑两种情况：

1.第一个字符是“.”

2.末尾字符是“.”

给几个特殊样例：

".L.R...LR..L.."
"..R.."
".R........"
".......L.L"
"RRRRRRL..."

"L.L...L.L.LL.L..L..."

代码如下

class Solution {
public:
    string pushDominoes(string dominoes) {
        string temp = dominoes;
        if(dominoes[0]=='.')
        {
            if(dominoes[1]=='L')
                temp[0] = 'L';
        }
        for(int i =1;i<dominoes.length()-1;i++)
        {
            if(dominoes[i]=='.')
            {
                int low = i-1;
                int high = i+1;
                while(low>=0&&high<dominoes.length())
                {
                    if(dominoes[high]=='L'&&dominoes[low]!='R')
                    {
                        temp[i] = 'L';
                        break;
                    }
                    else if(dominoes[low]=='R'&&dominoes[high]!='L')
                    {
                        temp[i] = 'R';
                        break;
                    }
                    else if(dominoes[low]=='.'&&dominoes[high]=='.')
                    {
                        low--;
                        high++;
                    }
                    else if(dominoes[low]=='L'&&dominoes[high]=='.')
                    {
                        high++;
                    }
                    else if(dominoes[low]=='.'&&dominoes[high]=='R')
                    {
                        low--;
                    }
                    else
                        break;
                }
            }
        }
        if(dominoes[dominoes.length()-1]=='.')
        {
            int low = dominoes.length()-2;
            while(low>=0)
            {
                if(temp[low]=='.')
                    low--;
                else
                    break;
            }
            if(temp[low]=='R')
            {
                for(int i =low+1;i<dominoes.length();i++)
                    temp[i] ='R';
            }
        }
        if(dominoes[0]=='.')
        {
            int high = 1;
            while(high<dominoes.length())
            {
                if(temp[high]=='.')
                    high++;
                else
                    break;
            }
            if(temp[high]=='L')
            {
                for(int i =high-1;i>=0;i--)
                    temp[i] ='L';
            }
        }
        return temp;
    }
};

如果大家对我的代算法思路有什么改进，欢迎评论区留言！