void Q2(){
string s;
cin >> s;
int L = -1, R = -1;
//从左到右找R
for (int i = 0; i < s.size(); ++i){
if (s[i] == 'R'){
R = i;
break;
}
}
if (R == -1){
cout << s.size() << endl;
return;
}
//从右到左找L
for (int i = s.size() - 1; i >= 0; --i){
if (s[i] == 'L'){
L = i;
break;
}
}
if (L == -1){
cout << s.size() << endl;
return;
}
if (L < R){
cout << s.size() << endl;
return;
}
int sumL = 0;
int sumR = 0;
for (int i = R; i < s.size(); ++i){
if (s[i] == 'L')
sumL++;
}
for (int i = L; i >= 0; --i){
if (s[i] == 'R')
sumR++;
}
//int sum = sumR>sumL ? sumR : sumL;
int sum = sumR + sumL;
cout << s.size() - sum + 1 << endl;
return;
}
我的思路：利用编码，如果L右边没有R，那么要把L算进去。如果R后面有L，肯定是保留一个R。
O(n)的复杂度。
AC代码如下：
#include <iostream>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100008;
char line[maxn];
struct Seq {
char op;
int l;
};
struct Seq seq[maxn];
int seq_idx;
int main() {
// freopen("in.txt", "r", stdin);
while (scanf("%s", line) != EOF) {
char pre_op = 'X';
int length = strlen(line);
seq_idx = 0;
for (int i = 0; i < length; i++) {
if (line[i] != pre_op) {
seq_idx++;
seq[seq_idx].l = 1;
seq[seq_idx].op = line[i];
pre_op = line[i];
}
else {
seq[seq_idx].l += 1;
}
}
int has_right = 0;
int ans = 0;
for (int i = 1; i <= seq_idx; i++) {
if (seq[i].op == 'L' && has_right == 0) {
ans += seq[i].l;
}
else if (seq[i].op == 'L' && has_right == 1) {
continue;
}
else if (seq[i].op == 'R') {
if (i < seq_idx) {
has_right = 1;
continue;
}
else {
ans += seq[i].l;
}
}
}
if (has_right) {
ans += 1;
}
cout << ans << endl;
}
return 0;
}
#include<iostream>
#include<string>
using namespace std;
int main()
{
string str;
while (cin >> str)
{
while (str.find("RL") != string::npos)
{
int index = str.find("RL");
if (index != 0)
{
if (str[index - 1] == 'R')
str.erase(index, 1);
else
str.erase(index + 1, 1);
}
else
str.erase(index + 1, 1);
}
cout << str.length()<<endl;
}
return 0;
}
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main() {
string in;
cin >> in;
int n = in.size();
int remain1;
for (remain1= 0; remain1 < n&&in[remain1] == 'L'; ++remain1) {}
int remain2;
for(remain2=0;remain2<n&& in[n-1-remain2] == 'R'; ++remain2){}
int remain = remain1 + remain2;
if (remain == n) {
cout << remain << endl;
return 0;
}
else
cout << remain + 1 << endl;
return 0;
}
第一个R和最后一个L之间的串全部可以“踢出去”，所以只需找到第一个R和最后一个Ｌ的下标；
若indexR > index L , 查找失败，输出字符串长度length；
否则输出
length - (lastL - firstR)
代码如下：
import java.util.Scanner;
/**
* Created by oukohou on 2017/9/16.
*
* If this runs wrong, don't ask me, I don't know why;
* If this runs right, thank god, and I don't know why.
* Maybe the answer, my friend, is blowing in the wind.
*/
public class Quarrel {
public static int getLeftPeople(char[] chars) {
if (chars.length == 1) {
return 1;
}
int length = chars.length;
int sum = length;
int firstR = 0, lastL = length - 1;
boolean foundR = false, foundL = false;
for (int i = 0; i < length; i++) {
if (chars[i] == 'R' && !foundR) { // 查找第一个R
foundR = true;
firstR = i;
}
if (chars[length - 1 - i] == 'L' && !foundL) { // 查找第一个L
foundL = true;
lastL = length - 1 - i;
}
if (foundL && foundR) {
break;
}
}
if (foundL && foundR && firstR < lastL) { // 找到，并且R在L左边，则更新sum
sum = length - (lastL - firstR);
}
return sum;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String string = scanner.next();
char[] chars = string.toCharArray();
int sum = getLeftPeople(chars);
System.out.println(sum);
}
}代码已同步到oukohou的github，欢迎 star and fork.
public static void sort(StringBuffer s){
int len = s.length();
int count =0;
int left = s.indexOf("L");
int right = s.indexOf("R");
if(left==-1||right==-1){
System.out.println(len);
}
if(s.charAt(0)=='R'){
if(s.charAt(len-1)=='R'){
left = s.lastIndexOf("L");
System.out.println(len-left+1);
}
if(s.charAt(len-1)=='L'){
System.out.println(1);
}
}
if(s.charAt(0)=='L'){
left = s.indexOf("R");
count = left;
s.delete(0,left);
len =s.length();
if(s.charAt(len-1)=='R'){
left = s.lastIndexOf("L");
if(left!=-1){
System.out.println(len-left+1+count);
}else{
System.out.println(count+len);
}
}
if(s.charAt(len-1)=='L'){
System.out.println(1+count);
}
}想法很简单，从左看，连续的L肯定留下，同理右边也一样。
中间如果还有剩余，最后只会剩一个。
public static int solution(String s){
int count=0;
for(int i=0;i<s.length();i++){
if(s.charAt(i)=='L'){
count++;
}else{
break;
}
}
for(int i=s.length()-1;i>=0;i--){
if(s.charAt(i)=='R'){
count++;
}else{
break;
}
}
if(count==s.length()){
return count;
}else
return count+1;
}#include <stdio.h>
#include <string.h>
int main()
{
char str[10];
int i = 1;
int n,j,Num_Remain;
printf("Please Enter: \n");
gets(str);
//printf("%s\n",str);
Num_Remain = strlen(str);
for(n = 0;str[n] != '\0';n++)
{
if((str[n] == 'R') && (str[n++] == 'L'))
{
if( i%2 )
{
i++;
for(j = n;str[j] != '\0';j++)
str[j] = str[j++];
Num_Remain--;
printf("%d",Num_Remain);
n--;
}
else
{
i++;
for(j = n + 1;str[j] != '\0';j++)
str[j] = str[j++];
Num_Remain--;
n--;
}
}
}
printf("%d",Num_Remain);
return 0;
}求问大神，为什么这个运行结果不对，正确率为10%是个什么鬼。。。
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
char arr[] = "LRRLRLL";
int arrLen = strlen(arr);
if (arrLen<1 || arrLen>100000)
{
return -1;
}
for (int i=0;i<arrLen-1;i++)
{
if(arr[i] != arr[i+1])
arr[i]= NULL;
else
continue;
}
int num=0;
for (int i=0;i<arrLen;i++)
{
if(arr[i] != NULL)
num++;
}
cout<<num<<endl;
return 0;
}
#include <iostream>
#include <string>
using namespace std;
int maxDelet(string str) {
int max = 0;
if(str.empty() || str.length() == 1)
return max;
for(int i = 0; i < str.length() - 1; i++) {
if(str[i] == str[i+1] ||(str[i] == 'L' && str[i+1] == 'R'))
continue;
else {
string stmp1 = str;
string stmp2 = str;
int max1 = maxDelet(stmp1.erase(i,1));
int max2 = maxDelet(stmp2.erase(i+1,1));
if(max1 >= max2) {
str.erase(i,1);
max = max1+1;
}
else {
str.erase(i+1,1);
max = max2+1;
}
break;
}
}
return max;
}
int main(int argc, const char * argv[]) {
string str;
while (cin >> str) {
size_t len = str.length();
int maxd = maxDelet(str);
cout << len - maxd << endl;
}
return 0;
}
isaimawang
@ 赛码网
533869549