알고리즘/leetcode
Push Dominoes
유이얼
2021. 7. 22. 00:59
// mine
// 40ms, 16.6MB
class Solution {
public:
string pushDominoes(string dominoes) {
int size = dominoes.size();
vector<int> counter(size);
char prev = dominoes[0];
int count = 0;
for (int i = 1; i < size; ++i) {
char cur = dominoes[i];
if (cur == '.' && prev == 'R')
counter[i] = ++count;
if (cur == 'L' || cur == 'R') {
count = 0;
prev = cur;
}
}
prev = dominoes[size - 1];
count = 0;
for (int i = size - 2; i >= 0; --i) {
char& cur = dominoes[i];
if (cur == '.' && prev == 'L') {
++count;
if (counter[i] == 0 || counter[i] > count) cur = 'L';
else if (counter[i] < count) cur = 'R';
else cur = 'C';
continue;
}
if (cur == 'L' || cur == 'R') {
count = 0;
prev = cur;
}
}
for (int i = 0; i < size; ++i) {
char& cur = dominoes[i];
if (counter[i] && cur == '.') cur = 'R';
if (cur == 'C') cur = '.';
}
return dominoes;
}
};// 4ms
class Solution {
public:
string pushDominoes(string dominoes) {
char prev = 'L';
int l = -1;
int curr = 0;
int n = dominoes.length();
while (curr < n) {
if (dominoes[curr] == '.') {
curr++;
} else {
if (dominoes[curr] == 'R') {
if (prev == 'R') {
for (int i=l+1; i<curr; i++) dominoes[i] = 'R';
}
prev = 'R';
l = curr;
} else {
if (prev == 'L') {
for (int i=l+1; i<curr; ++i) dominoes[i] = 'L';
} else {
int f = l+1, s = curr-1;
while (f < s) {
dominoes[f++] = 'R';
dominoes[s--] = 'L';
}
}
prev = 'L';
l = curr;
}
curr++;
}
}
if (prev == 'R') {
for (int i=l+1; i<n; i++) dominoes[i] = 'R';
}
return dominoes;
}
};// 9000 KB
class Solution {
public:
string pushDominoes(string d) {
int n=d.length();
if(n==1)
return d;
int l=0,r=0;
int i=0;
while(i<n){
if(d[i] == 'L' || d[i] == 'R'){
i++;
continue;
}
if(i<n){
l=i;
r=l;
while(d[r] == '.' && (r<n)){
r++;
}
r--;
i=l+1;
if(l==r){
if(l==0 && d[l+1]=='L'){
d[l]=d[l+1];
}
else if(l==n-1 && d[l-1]=='R')
d[l]=d[l-1];
else if(l>0 && l<n-1 && (d[l-1] == d[l+1])){
d[l]=d[l+1];
}
}
else{
if(l <= r){
if(l==0 && r==n-1)
return d;
if(l==0 && d[r+1] == 'L'){
while(l!=r+1)
d[l++]=d[r+1];
}
if(r==n-1 && d[l-1] == 'R'){
while(l!=r+1){
d[l++]='R';
}
}
else if(l>0 && r<n-1){
if(d[l-1] == 'R'){
d[l] = 'R';
}
if(d[r+1] == 'L'){
d[r] = 'L';
i=l;
}
}
}
}
}
}
// cout<<d;
return d;
}
};