""" LR匹配问题,记录之前方向,分4类讨论LL/RL/RR/LR
""" import math if __name__ == "__main__": s = list(input().strip()) ans = s[:] t = pl = pr = 0 flag = '0' while t < len(s): while t < len(s) and s[t] == '.': t += 1 if t >= len(s): break if s[t] == 'L': if flag == '0' or flag == 'L': for i in range(pl, t): ans[i] = 'L' else: pl = t for i in range(pr, math.ceil((pr + pl) / 2)): ans[i] = 'R' for i in range(math.floor((pr + pl) / 2) + 1, pl): ans[i] = 'L' flag = 'L' elif s[t] == 'R': if flag == 'R': for i in range(pr + 1, t): ans[i] = 'R' pr = t flag = 'R' t += 1 if pr > pl: for i in range(pr, len(s)): ans[i] = 'R' print(''.join(ans))
s = input() stat = [(i, char) for i, char in enumerate(s) if char != '.'] stat = [(-1, 'L')] + stat + [(len(s), 'R')] #print() #print(s) for (i,ci), (j, cj) in zip(stat[:-1], stat[1:]): #print(i, j, ci, cj) if ci == cj: if i < 0: s = ci * (j-i) + s[j+1:] elif j == len(s): s = s[:i] + ci * (j-i) + s[j+1:] else: s = s[:i] + ci * (j-i+1) + s[j+1:] #print(s) elif ci > cj: # R > L half = (j-i+1) // 2 rest = (j-i+1) % 2 s = s[:i] + 'R'*half + '.'*rest + 'L'*half + s[j+1:] #print(i, j, s) #print(s, i, j, s[:i], s[j+1:]) #print('LL.RR.LLRRRLLL.') print(s)参考LEETCODE838 https://leetcode.com/articles/push-dominoes/
常规做法,注意coding细节即可
1. import java.util.Scanner; 2. import static java.lang.System.in; 3. public class Main { 4. public static void main(String[] args) { 5. Scanner sc = new Scanner(in); 6. String str = sc.nextLine(); 7. char[] arr = ("L" + str + "R").toCharArray(); //首尾加一个字符方便处理 8. int begin = 0; 9. for (int i = 1; i < arr.length; i++) { 10. if (arr[i] != '.') { 11. trans(arr, begin, i); 12. begin = i; 13. } 14. } 15. StringBuilder sb = new StringBuilder(); 16. for (int i = 1; i < arr.length - 1; i++) { 17. sb.append(arr[i]); 18. } 19. System.out.println(sb.toString()); 20. } 21. public static void trans(char[] arr, int begin, int end) { 22. 23. for (int i = begin + 1, j = end - 1; i <= j; i++, j--) { 24. if (arr[begin] == 'L' && arr[end] == 'L') { 25. arr[i] = 'L'; 26. arr[j] = 'L'; 27. } else if (arr[begin] == 'R' && arr[end] == 'R') { 28. arr[i] = 'R'; 29. arr[j] = 'R'; 30. } else if (arr[begin] == 'R' && arr[end] == 'L' && i != j) { 31. arr[i] = 'R'; 32. arr[j] = 'L'; 33. } 34. } 35. } 36. }
#include <bits/stdc++.h> using namespace std; int main(){ string s; cin>>s; int l = s.length(); int L[l],R[l]; for(int i=0, x=l;i<l;i++){ if(s[i]=='R'){ x = l; R[i] = x--; }else if(s[i]=='.' && x<l) R[i] = x--; else{ R[i] = 0; x = l; } } for(int i=l-1,x=l;i>=0;i--){ if(s[i]=='L'){ x = l; L[i] = x--; }else if(s[i]=='.' && x<l) L[i] = x--; else{ L[i] = 0; x = l; } } string r; for(int i=0;i<l;i++){ if(L[i]>R[i]) r += 'L'; else if(L[i]<R[i]) r += 'R'; else r += '.'; } cout<<r<<endl; return 0; }
/*链接:https://www.nowcoder.com/questionTerminal/fae1307a24ae4e9ea852a646a4f812bf?answerType=1&f=discussion 来源:牛客网 这个字符串一共就分为四种情况: (1):L...L ,在这种情况下,将里面‘.’全部换成'L'; (2):R...L,在这种情况下,将里面左半部分替换为'L',右半部分替换为'R',需要注意的是区间长度的奇偶问题 (3):R...R,在这种情况下,将里面‘.’全部换成'R'; (4):L...R,在这种情况下,我们不做任何处理; 备注:为了考虑左右开头的影响,我们分别在字符串的最左边加上“L”,最右边加上“R”, 这样既不会影响内部的判断,又能处理端点的情况 */ import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.nextLine(); StringBuilder sb = new StringBuilder(s);//为了统一处理, sb.append("R");//在最右边加一个“R” sb.insert(0, "L");//在最左边加一个“L” List<Integer> v = new ArrayList<>();//记录含有L或R的下标位置 for(int i = 0; i < sb.length(); ++i){ if(sb.charAt(i) == 'L' || sb.charAt(i) == 'R') v.add(i);; } for(int p = 0; p < v.size() - 1; ++p){//按RL区间端点分类,共有4类 int i = v.get(p), j = v.get(p + 1);//一个区间一个区间处理(区间都是相邻的处理) char c1 = sb.charAt(i), c2 = sb.charAt(j); if(c1 == 'L' && c2 == 'L'){ for(int k = i + 1; k < j; ++k) sb.setCharAt(k, 'L'); } if(c1 == 'L' && c2 == 'R'){}//这种什么也不用做 if(c1 == 'R' && c2 == 'L'){ for(int k = i + 1; k < (double)(j + i)/2; ++k) sb.setCharAt(k, 'R'); for(int k = j - 1; k > (double)(j + i)/2; --k) sb.setCharAt(k, 'L'); } if(c1 == 'R' && c2 == 'R'){ for(int k = i + 1; k < j; ++k) sb.setCharAt(k, 'R'); } } sb.deleteCharAt(sb.length() - 1); sb.deleteCharAt(0);//把开始加的那两张去掉 System.out.println(sb); } }
using System; using System.Collections.Generic; using System.Linq; using System.Text.RegularExpressions; //总结目前牛客问题 第一,没有循环输入问题, 第二 有循环输入问题, 第三 输入有多余空格问题 ,第四 中间插入多余空行问题 .... namespace Test0001 { class Program { public static void Main(string[] args) { string line; while (!string.IsNullOrEmpty(line = Console.ReadLine())) Func(line); } public static void Func(string line) { int n = line.Length; int[] dp1 = new int[n]; int[] dp2 = new int[n]; //从左往右 dp1[0] = line[0] == 'R' ? n : 0; //初始值 for (int i = 1; i < n; i++) { if (line[i] == 'R') { dp1[i] = n; } else if (line[i] == '.') { dp1[i] = dp1[i - 1] > 0 ? dp1[i - 1] - 1 : 0;//如果左边的大于0说明是连续的,因此等于左边一位的值减1 } } //从右往左 dp2[n - 1] = line[n - 1] == 'L' ? n : 0;//初始值 for (int i = n - 2; i >= 0; i--) { if (line[i] == 'L') { dp2[i] = n; } else if (line[i] == '.') { dp2[i] = dp2[i + 1] > 0 ? dp2[i + 1] - 1 : 0;//如果右边的大于0说明是连续的,因此等于右边一位的值减1 } } for (int i = 0; i < n; i++) { int a = dp1[i] - dp2[i]; Console.Write(a > 0 ? 'R' : a < 0 ? 'L' : '.'); } } } }
#include <bits/stdc++.h> using namespace std; void get_L(vector<pair<int, int> > &p, int L, string s){ int power = 1; p[L].first = power; power++; L--; while(L >= 0 && s[L] != 'L' && s[L] != 'R'){ p[L].first = power; power++; L--; } } void get_R(vector<pair<int, int> > &p, int R, string s){ int power = 1; p[R].second = power; power++; R++; while(R < s.length() && s[R] != 'L' && s[R] != 'R'){ p[R].second = power; power++; R++; } } int main(int argc, char *argv[]){ string s; cin >> s; vector<pair<int, int> > p(s.length(), {0, 0}); for (int i = 0; i < s.length(); i++){ if(s[i] == 'L'){ get_L(p, i, s); } else if(s[i] =='R'){ get_R(p, i, s); } } for (int i = 0; i < s.length(); i++){ if(p[i].first > p[i].second){ if(p[i].second == 0){ s[i] = 'L'; } else { s[i] = 'R'; } } else if(p[i].first < p[i].second) { if(p[i].second > p[i].first){ if(p[i].first == 0){ s[i] = 'R'; } else { s[i] = 'L'; } } } else { s[i] = '.'; } } for (int i = 0; i < s.length(); i++){ printf("%c", s[i]); } printf("\n"); return 0; }
stones = list(input()) prev = [-1, ""] for i in range(len(stones)): if stones[i] == "L": if prev[1] == "L" or prev[1] == "": for j in range(prev[0] + 1, i): stones[j] = "L" elif prev[1] == "R": for j in range(prev[0] + 1, i): if j < (prev[0] + i) / 2: stones[j] = "R" elif j > (prev[0] + i) / 2: stones[j] = "L" else: continue prev = [i, stones[i]] elif stones[i] == "R": if prev[1] == "R": for j in range(prev[0] + 1, i): stones[j] = "R" prev = [i, stones[i]] if prev[1] == "R": for i in range(prev[0] + 1, len(stones)): stones[i] = "R" print("".join(stones))
#include <iostream> using namespace std; int main(void){ enum {INIT, LEFT, RIGHT}; string s; cin>>s; int boundary = s.length(); int left = 0, right = 0, stage = INIT; for(int i = 0; i < boundary; ++i){ if(s[i] == 'L'){ switch (stage) { //注意这里为了节省代码量,INIT case没有break case INIT: stage = LEFT; case LEFT: for(int j = left; j < i; ++j) s[j] = 'L'; left = i+1; break; //(LEFT RIGHT)完成向中心倒的操作,此后状态回归到INIT case RIGHT: stage = INIT; for(int j = right, k = i-1; j < k; ++j, --k) s[j] = 'R', s[k] = 'L'; left = right = i+1; } } if(s[i] == 'R'){ switch (stage) { case INIT: case LEFT: stage = RIGHT; right = i+1; break; case RIGHT: for(int j = right; j < i; ++j) s[j] = 'R'; right = i+1; } } } //注意最后退出循环时若状态为RIGHT,完成向右倒的操作 if(stage == RIGHT) for(int j = right; j < boundary; ++j) s[j] = 'R'; cout<<s<<endl; return 0; }
当前状态 | 转移状态 | 操作 |
INIT | LEFT | left至i的字符赋值为L,表示向左倾倒 |
LEFT | LEFT(不变) | 同上 |
RIGHT | INIT | right至i的字符从两端开始左右各赋值R,L,表示两边向中间倾倒 |
当前状态 | 转移状态 | 操作 |
INIT | RIGHT | right=i+1 |
LEFT | RIGHT(不变) | 同上 |
RIGHT | RIGHT | right至i的字符赋值为R,表示向右倾倒 |
public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); String str = in.nextLine(); char[] c = str.toCharArray(); int i = -1; int j = 0; while (j < c.length){ if (c[j] == '.') j++; else if (c[j] == 'L'){ for (int k=i+1;k<j;k++){ c[k] = 'L'; } i = j; j++; }else if (c[j] == 'R'){ int k; for (k=j+1;k<c.length;k++){ if (c[k] != '.') break; } j++; if (k == c.length){ while (j < c.length){ c[j] = 'R'; j++; } }else if (c[k] == 'R'){ while (j < k){ c[j] = 'R'; j++; } i = k; }else if (c[k] == 'L'){ int t = k-1; while (j < t){ c[j] = 'R'; c[t] = 'L'; j++;t--; } j = k+1; i = k; } } } for (char ch : c) System.out.print(ch); } }
import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); char[] chs = scanner.next().toCharArray(); int len = chs.length; int[] values = new int[len]; // 第一遍从左往右遍历,遇到R就赋值length,接下来如果是.则递减,直到遇到L清零 int value = 0; for (int i = 0; i < len; i++) { if (chs[i] == 'R') { value = len; } else if (chs[i] == 'L') { value = 0; } else { // 保证L之后遇到.仍旧赋值0而不是负数 value = Math.max(value - 1, 0); } // values数组加上value值 values[i] += value; } // 第二遍从右往左遍历,遇到L就赋值length,接下来如果是.则递减,直到遇到R清零 value = 0; for (int i = len - 1; i >= 0; --i) { if (chs[i] == 'L') { value = len; } else if (chs[i] == 'R') { value = 0; } else { // 保证R之后遇到.仍旧赋值0而不是负数 value = Math.max(value - 1, 0); } // values数组减去value值 values[i] -= value; } StringBuilder result = new StringBuilder(); // values值大于0则为R,小于0则为L,等于0则为. for (int i : values) { result.append(i > 0 ? 'R' : i < 0 ? 'L' : '.'); } System.out.println(result); } }
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Solution10_推倒吧骨牌 { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); String s = bf.readLine(); int n = s.length(); int[] ltor = new int[n];//模拟往右边推,每个骨牌倒下的先后顺序 int[] rtol = new int[n];//模拟往左边推,每个骨牌倒下的先后顺序 boolean isPush = false; for (int i = 0; i < n; i++) { if (s.charAt(i) == 'R') { ltor[i] = 1; isPush = true; } else if (s.charAt(i) == 'L') { isPush = false; } else if (isPush) { ltor[i] = ltor[i - 1] + 1; } } isPush = false; for (int i = n - 1; i >= 0; i--) { if (s.charAt(i) == 'L') { isPush = true; rtol[i] = 1; } else if (s.charAt(i) == 'R') { isPush = false; } else if (isPush) { rtol[i] = rtol[i + 1] + 1; } } StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; i++) { if (ltor[i] == rtol[i]){ sb.append('.'); }else if (ltor[i] == 0 && rtol[i] != 0){//ltor[i] == 0,往左边倒 sb.append('L'); }else if (ltor[i] !=0 && rtol[i] == 0) {//rtol[i] = 0 往右边的倒 sb.append('R'); }else if (ltor[i] < rtol[i]){//往右边倒的时间小于往左边推到的时间,所以先往右边先倒 sb.append('R'); }else if (ltor[i]>rtol[i]){ sb.append('L'); } } System.out.println(sb.toString()); } }
import java.util.*; public class TTTest { public static void main(String[] args) { Scanner input = new Scanner(System.in); String s = input.next(); input.close(); char[] a = s.toCharArray(); int len = s.length(); int lway = 0; int ridx= 0; int num = 0; for (int i=0;i<len;i++) { if (a[i] == 'R') { for (int j=i+1;j<len;j++) { if (a[j] == 'R') { num = 1; ridx = j; break; } if (a[j] == 'L') { num = 1; lway = j; if (((j-i)%2) != 0) { for (int k=i+1;k<j;++k) { if (k>((j-i)/2 + i)) { a[k] = 'L'; } if (k <= ((j-i)/2 + i)) { a[k] = 'R'; } } } if (((j-i)%2) == 0) { for (int k=i+1;k<j;k++) { if (k<((j+i)/2)) { a[k] = 'R'; } if (k>((j+i)/2)) { a[k] = 'L'; } if (k==((j+i)/2)) { a[k] = '.'; } } } break; } else { num = 0; } } if (num == 0) { for (int j=i+1;j<len;j++) { a[j] = 'R'; } } } if(i< ridx){ a[i] = 'R'; } if (a[i] == 'L') { for (int j=lway;j<=i;j++) { a[j] = 'L'; } } } System.out.println(a); } }
import sys from collections import deque instr = sys.stdin.readline().strip() q = deque() outstr = "" for ch in instr: if ch == '.': q.extend(ch) # `'.'`入队列 elif ch == 'R': if len(q) == 0: q.extend(ch) continue if q[0] == '.': outstr += ''.join(q) # 全部出队列 elif q[0] == 'R': outstr += 'R' * len(q) # 全部出队列,且被推倒 q.clear() q.extend(ch) # `'R'`入队列 elif ch == 'L': if len(q) == 0: outstr += 'L' continue if q[0] == '.': outstr += 'L' * len(q) # 全部出队列,且被推倒 q.clear() outstr += 'L' # 当前的`'L'`` elif q[0] == 'R': d, v = divmod(len(q) - 1, 2) if v: # 奇数个 outstr += 'R' + 'R' * d + '.' + 'L' * d + 'L' else: # 偶数个 outstr += 'R' + 'R' * d + 'L' * d + 'L' q.clear() if len(q) > 0: outstr += q[0] * len(q) print(outstr)
/* LL LR RL RR */ import java.util.Scanner; public class Main { public static void main (String[] args) { Scanner sc = new Scanner(System.in); char[] in = sc.next().toCharArray(); int len = in.length; char first = 'a'; int firsti = 0; char second = 'a'; int secondi = 0; int front = 0; int pair = 0; for (int i = 0; i < len; i++) { if (in[i] == '.') { continue; } else if (in[i] == 'L') { if (pair == 0) { first = 'L'; firsti = i; pair++; } else { second = 'L'; secondi = i; pair++; } } else { if (pair == 0) { first = 'R'; firsti = i; pair++; } else { second = 'R'; secondi = i; pair++; } } if (pair == 2) { if (first == 'L' && second == 'L') { pair = 1; for (int j = front; j < secondi; j++) { System.out.print('L'); } front = secondi; firsti = secondi; } if (first == 'L' && second == 'R') { pair = 1; for (int j = front; j <= firsti; j++) { System.out.print('L'); } for (int j = firsti+1; j < secondi; j++) { System.out.print('.'); } front = secondi; first = 'R'; firsti = secondi; } if (first == 'R' && second == 'L') { pair = 1; for (int j = front; j < firsti; j++) { System.out.print('.'); } for (int j = firsti; j < firsti+(secondi-firsti+1)/2; j++) { System.out.print('R'); } int s = firsti+(secondi-firsti+1)/2; if ((secondi-firsti+1)%2 == 1) { System.out.print('.'); s++; } for (int j = s; j < secondi; j++) { System.out.print('L'); } front = secondi; first = 'L'; firsti = secondi; } if (first == 'R' && second == 'R') { pair = 1; for (int j = front; j < firsti; j++) { System.out.print('.'); } for (int j = firsti; j < secondi; j++) { System.out.print('R'); } front = secondi; firsti = secondi; } } } if (first == 'L') { System.out.print('L'); front++; for (int j = front; j < len; j++) { System.out.print('.'); } } else { for (int j = front; j < len; j++) { System.out.print('R'); } } } }
#include<bits/stdc++.h> using namespace std; // 更新任意两个操作之间的骨牌 // 只有LR、LL、RR、RL这几种情况 void update(string& s,int l,int r,char last,char now) { if(last=='L'&&now=='R') return; else if(last=='R'&&now=='L'){ while(r-l>2) { s[++l]='R';s[--r]='L'; } } else if(last=='L'&&now=='L'){ for(int i=l;i<=r;++i) s[i]='L'; }else{ for(int i=l;i<=r;++i) s[i]='R'; } } int main() { string s; cin>>s; bool first = true; int i = 0; int last_index = 0; char pre; while(i<s.size()) { while(i<s.size()&&s[i]=='.') ++i; // 先确定第一个动作是L还是R if(s[i]=='L'){ if(first) { first = false; for(int k=0;k<i;++k) s[k]='L'; pre = 'L'; last_index = i; } // 逐段更新 else { update(s,last_index,i,pre,'L'); pre = 'L'; last_index = i; } } else if(s[i]=='R'){ if(first){ first = false; last_index = i; pre = 'R'; } else{ // 逐段更新 update(s,last_index,i,pre,'R'); pre = 'R'; last_index = i; } } ++i; } // 如果最后一个动作是R 后面几张牌改一下 if(pre=='R') for(int k=last_index;k<s.size();++k) s[k]='R'; cout<<s<<endl; return 0; }
a = [0, 0] a = a + list(input()) a = a + [0, 0] s = '' for i in range(2, len(a)-2): if a[i] == '.' and a[i-1] == 'R': c = 1 for j in range(i+1, len(a)-2): if a[j] == '.': c = c + 1 continue if a[j] == 'R': break if a[j] == 'L': for k in range(1, c+1): if k <= c//2: a[i+k-1] = -1 if c % 2 == 0 and k > c//2: a[i+k-1] = 1 if c % 2 != 0 and k > c//2 + 1: a[i+k-1] = 1 if c % 2 != 0 and k == c//2 + 1: a[i+k-1] = 0 break for i in range(2, len(a)-2): if a[i] == 'R' and a[i+1] == '.' and a[i+2] != 'L': a[i+1] = 'R' for i in range(1, len(a)-3): if a[-i] == 'L' and a[-i-1] == '.' and a[-i-2] != 'R': a[-i-1] = 'L' for i in range(2, len(a)-2): if a[i] == 0: a[i] = '.' if a[i] == -1: a[i] = 'R' if a[i] == 1: a[i] = 'L' s = s + a[i] print(s)