Problem: 838. Push Dominoes 推多米诺
解题过程
首先要正序遍历一次，拿到每个’.‘左侧的字符LR和索引，然后倒序遍历一次，拿到每个’.‘右侧的字符LR和索引。最后对每个’.'，判断左右两侧字符，以及距离的，决定赋值L还是R或者不变的
Code
class Solution { public: string pushDominoes(string dominoes) { int n = dominoes.size(); // vector<bool> status(n, false); dominoes = "L" + dominoes + "R"; string ret = dominoes; pair<char, int> pre; vector<pair<char, int>> left(n+2); for(int i = 0; i <= n + 1; i++) { if(dominoes[i]!='.') { pre = {dominoes[i], i}; } else { left[i] = pre; } } char cl, cr; int disL, disR; for(int i = n+1; i >= 0; i--) { if(dominoes[i]!='.') { pre = {dominoes[i], i}; } else { // right[i] = pre; cl = left[i].first; cr = pre.first; disL = i - left[i].second; disR = pre.second - i; if(cl=='R' && cr=='L') { if( disR > disL ) { ret[i] = 'R'; } else if( disR < disL ) { ret[i] = 'L'; } } else if(cl=='R' && cr=='R') { ret[i] = 'R'; } else if(cl=='L' && cr=='L') { ret[i] = 'L'; } } } ret = ret.substr(1, n); return ret; // dominoes = "." + dominoes + "."; // unordered_map<int, char> ump; // for(int i = 1; i <= n; i++) { // if(dominoes[i]!='.') { // status[i] = true; // } else { // if( dominoes[i-1]=='R' && dominoes[i+1]=='L' ) { // status[i] = true; // } else if( dominoes[i-1]=='L' && dominoes[i+1]=='R' ) { // status[i] = true; // } else if(dominoes[i-1]=='R') { // status[i] = true; // ump[i] = 'R'; // } else if(dominoes[i+1]=='L') { // status[i] = true; // ump[i] = 'L'; // } // } // } // for(auto &&[i, c] : ump) { // dominoes[i] = c; // } // while(true) { // unordered_map<int, char> ump; // for(int i = 1; i <= n; i++) { // if(status[i] == false && dominoes[i] == '.') { // if( dominoes[i-1]=='R' && dominoes[i+1]=='L' ) { // status[i] = true; // } else if( dominoes[i-1]=='L' && dominoes[i+1]=='R' ) { // status[i] = true; // } else if(dominoes[i-1]=='R') { // status[i] = true; // ump[i] = 'R'; // } else if(dominoes[i+1]=='L') { // status[i] = true; // ump[i] = 'L'; // } // } // } // if(ump.size() == 0) break; // for(auto &&[i, c] : ump) { // dominoes[i] = c; // } // } // dominoes = dominoes.substr(1, n); // return dominoes; } };
