推倒吧骨牌
推倒吧骨牌
http://www.nowcoder.com/questionTerminal/fae1307a24ae4e9ea852a646a4f812bf
题目难度：三星
考察点：模拟、双指针
方法：模拟、双指针
1.分析：
这个题我们可以完全采用双指针的做法来解决，因为双指针可以将问题给分隔开，其实这个字符串一共就分为四种情况：
(1). L...L ，在这种情况下，将里面‘.’全部换成'L'；
(2). R...L，在这种情况下，将里面左半部分替换为'L'，右半部分替换为'R'，需要注意的是区间长度的奇偶问题
(3). R...R，在这种情况下，将里面‘.’全部换成'R'；
(4). L...R，在这种情况下，我们不做任何处理；
(2). R...L，在这种情况下，将里面左半部分替换为'L'，右半部分替换为'R'，需要注意的是区间长度的奇偶问题
(3). R...R，在这种情况下，将里面‘.’全部换成'R'；
(4). L...R，在这种情况下，我们不做任何处理；
那么我们可以采用双指着的做法，首先建立两个指针l和r，使用指针r寻找字符串s中的'L'，使其将原问题进行分割开，找到'L'后，在从后往前进行遍历，即遍历[l,r]区间找是否存在'R'，只不过是逆向遍历，如果没有任何'R'字符，那么[l,r]区间显然都要变成L，否则就是在[l,r]区间中存在上述的第二种情况即R...L型，我们就按照上述方法进行处理即可，处理完之后，我们就要从l开始找到第一个R，然后将第一个R和最后一个R间的字符全部都变成R。然后更新l和r指针即可。即r++； l=r。
算法实现：
(1). 输入一个字符串s。 (2). 初始化两个指针l=r=0。
(3). 按照上述的贪心做法进行处理，得到更新之后的s，输出即可。
2.复杂度分析：
时间复杂度：O(n)空间复杂度：O(n)
3.代码：
#include <bits/stdc++.h>
using namespace std;
int main(){
string s; cin>>s;
int len = s.size();
int l = 0, r = 0;
while(r < len) {
if(s[r] != 'L') {
r++;
continue;
}
int tmp = -1;
for(int i=r; i>=l; i--) if(s[i] == 'R') { tmp = i; break; }
if(tmp == -1) for(int i=l; i<r; i++) s[i] = 'L';
else {
int l_inx = tmp + 1;
int r_inx = r - 1;
while(l_inx < r_inx) { s[l_inx++] = 'R'; s[r_inx--] = 'L'; }
for(int i=l; i<tmp; i++) {
if(s[i] == 'R') {
for(int j=i+1; j<tmp; j++) s[j] = 'R';
break;
}
}
}
l = ++r;
}
if(l != len) {
for(int i=l; i<r; i++) {
if(s[i] == 'R') {
for(int j=i+1; j<r; j++) s[j] = 'R';
break;
}
}
}
cout<<s<<endl;
return 0;
}
投递深圳同为数码等公司10个岗位
