[已解决]Python：每日一题 369

zltzlt

今天的题目：

在一个由 'L' , 'R' 和 'X' 三个字符组成的字符串（例如 "RXXLRXRXL"）中进行移动操作。

一次移动操作可以使用一个 "LX" 替换一个 "XL"，或者使用一个 "XR" 替换一个 "RX"。

给定起始字符串 start 和结束字符串 end，当且仅当存在一系列移动操作使得 start 可以转换成 end 时，返回 True。否则返回 False。

示例：

输入：start = "RXXLRXRXL", end = "XRLXXRRLX"
输出：True
解释：可以通过以下几步将 start 转换成end:
RXXLRXRXL -> XRXLRXRXL -> XRLXRXRXL ->
XRLXXRRXL -> XRLXXRRLX

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

March2615

2020-4-5 21:35:17

1. def daily369(start: str, end: str) -> bool:
   
2.     # 解题思路
   
3.     # L和R必不可能交换位置 -> judge the order of L and R
   
4.     # L的右边和R的左边的X数量只会减少 -> L的index只能减小，R的index只能增大
   
5.     # -> the index of L and R in start and end
   
6.     if len(start) != len(end):
   
7.         return False
   
8.     if start.replace('X', '') != end.replace('X', ''):
   
9.         return False
   
10.     start_index, end_index = [[], []], [[], []]
    
11.     for i in range(len(start)):
    
12.         if start[i] == 'L':
    
13.             start_index[0].append(i)
    
14.         elif  start[i] == 'R':
    
15.             start_index[1].append(i)
    
16.         if end[i] == 'L':
    
17.             end_index[0].append(i)
    
18.         elif end[i] == 'R':
    
19.             end_index[1].append(i)
    
20.     for i in range(len(start_index[0])):
    
21.         if start_index[0][i] < end_index[0][i]:
    
22.             return False
    
23.     for i in range(len(start_index[1])):
    
24.         if start_index[1][i] > end_index[1][i]:
    
25.             return False
    
26.     return True

复制代码

后面判断位置写的太复杂了，不知道有没有更好的方法

跳转到最佳答案楼层

fan1993423

想问一下这个遇到X必须执行动作吗？可以跳过某个X吗？另外同一个X可以反复使用吗 比如说XRR->RXR->RRX?

zltzlt

fan1993423 发表于 2020-4-5 18:10
想问一下这个遇到X必须执行动作吗？可以跳过某个X吗？另外同一个X可以反复使用吗 比如说XRR->RXR->RRX?

XRR 里面没有 RX，你是不是搞反了

fan1993423

zltzlt 发表于 2020-4-5 18:11
XRR 里面没有 RX，你是不是搞反了

好吧，搞反了，但意思就是XLL->LXL->LLX 这个X可以借用不

zltzlt

fan1993423 发表于 2020-4-5 18:16
好吧，搞反了，但意思就是XRR->RXR->RRX 这个X可以借用不

可以呀

塔利班

1. def f369(start,end):
   
2.     s,e=len(start),len(end)
   
3.     if start==end:
   
4.         return True
   
5.     elif s!=e:
   
6.         return False
   
7.     else:
   
8.         for i in range(s):
   
9.             if start[i]==end[i]:
   
10.                 continue
    
11.             elif i<s-1:
    
12.                 t=start[i:i+2]
    
13.                 if t=='XL':
    
14.                     return f369('LX'+start[i+2:],end[i:])
    
15.                 elif t=='RX':
    
16.                     return f369('XR'+start[i+2:],end[i:])
    
17.                 else:
    
18.                     return False
    
19.             else:
    
20.                 return False

复制代码

多点测试用例就好了

TJBEST

来一个无脑的算法，后面有更好的在更改。

1. def fun369(start,end):
   
2.     def inner(string,position):
   
3.         if string == end:
   
4.             return True
   
5.         elif len(start)!=len(end):
   
6.             return False
   
7.         for index in range(position,M-1):
   
8.             if string[index] == 'X' and string[index+1]=='L':        
   
9.                 if inner(string,index+1):
   
10.                     return True
    
11.                 else:
    
12.                     temp = string[:index] + 'LX' + string[(index+2):]
    
13.                     if inner(temp,0):
    
14.                         return True
    
15.             elif string[index] == 'R' and string[index+1]=='X':
    
16.                 if inner(string,index+1):
    
17.                     return True
    
18.                 else:
    
19.                     temp = string[:index] + 'XR' + string[(index+2):]
    
20.                     if inner(temp,0):
    
21.                         return True
    
22.             else:
    
23.                 pass
    
24.         return False
    
25.     M = len(start)
    
26.     return inner(start,0)

复制代码

March2615

1. def daily369(start: str, end: str) -> bool:
   
2.     # 解题思路
   
3.     # L和R必不可能交换位置 -> judge the order of L and R
   
4.     # L的右边和R的左边的X数量只会减少 -> L的index只能减小，R的index只能增大
   
5.     # -> the index of L and R in start and end
   
6.     if len(start) != len(end):
   
7.         return False
   
8.     if start.replace('X', '') != end.replace('X', ''):
   
9.         return False
   
10.     start_index, end_index = [[], []], [[], []]
    
11.     for i in range(len(start)):
    
12.         if start[i] == 'L':
    
13.             start_index[0].append(i)
    
14.         elif  start[i] == 'R':
    
15.             start_index[1].append(i)
    
16.         if end[i] == 'L':
    
17.             end_index[0].append(i)
    
18.         elif end[i] == 'R':
    
19.             end_index[1].append(i)
    
20.     for i in range(len(start_index[0])):
    
21.         if start_index[0][i] < end_index[0][i]:
    
22.             return False
    
23.     for i in range(len(start_index[1])):
    
24.         if start_index[1][i] > end_index[1][i]:
    
25.             return False
    
26.     return True

复制代码

后面判断位置写的太复杂了，不知道有没有更好的方法

kinkon

1. def f369(start, end):#双针法
   
2. 
   
3.     if start.count('X') != end.count('X'):
   
4.         return False
   
5.     m, n = len(start)-1, len(end)-1
   
6.     x = y = 0
   
7.     while x <= m and y <= n:
   
8.         while x < m and start[x] == 'X':
   
9.             x += 1
   
10.         while y < n and end[y] == 'X':
    
11.             y += 1
    
12.         #L和R不能相互穿过
    
13.         #print(start[x], end[y])
    
14.         if start[x] != end[y]:
    
15.             return False
    
16.         #L只能往左移动
    
17.         elif start[x] == 'L' and end[y] == 'L':
    
18.             if x < y:
    
19.                 return False
    
20.         #R只能往右移动
    
21.         elif start[x] == 'R' and end[y] == 'R':
    
22.             if x > y:
    
23.                 return False
    
24.             
    
25.         x += 1
    
26.         y += 1
    
27.     return True  

复制代码

ouyunfu

1. import re
   
2. def f369(start,end):
   
3.     if start.replace('X','')!=end.replace('X',''):
   
4.         return False
   
5.     elif len(start)!=len(end):
   
6.         return False
   
7.     elif [i.start() for i in re.finditer('R',start)]<=[i.start() for i in re.finditer('R',end)] and [i.start() for i in re.finditer('L',start)]>=[i.start() for i in re.finditer('L',end)]:
   
8.         return True
   
9.     else:return False

复制代码

whosyourdaddy

def func369(start,end):
    i = 0
    j = 0
    if len(start) != len(end):
        return False
    if start.count('X') != end.count('X'):
        return False
    a = len(start)
    b = len(end)
    while(i<a-1 and j<b-1):
        while(start[i]=='X'):
            i += 1
            if i == (a-1):
                break
        while(end[j]=='X'):
            j += 1
            if j==(b-1):
                break
        if start[i]!= end[j]:
            return False
        if start[i]=='L' and i<j:
            return False
        if start[i]=='R' and j<i:
            return False
        i += 1
        j += 1
    return True

ouyunfu

1. import re   
   
2. def fun369(start,end):
   
3.     return True if start.count('X')==end.count('X') and start.replace('X','')==end.replace('X','') and [i.start() for i in re.finditer('R',start)]<=[i.start() for i in re.finditer('R',end)] and [i.start() for i in re.finditer('L',start)]>=[i.start() for i in re.finditer('L',end)] else False

复制代码

风魔孤行者

1. def f(start,end):
   
2.     s = start.replace('X','')
   
3.     e = end.replace('X','')
   
4.     if len(start)==len(end) and s==e:
   
5.         return True
   
6.     else:
   
7.         return False

复制代码

chen971130

ouyunfu 发表于 2020-4-5 22:38
解题思路：
L，R不可越界，而X通过与L,R交换可以变换到任意位置，因此只需保证除去X后的‘LR框架‘一致， ...

start = LX
end = XL
这种顺序相同但是也不能转换,因为只能按题目替换但是不能反过来替换吧
或者 start = LXR  end = XLR 也不能

永恒的蓝色梦想

zhanlou

旅途Z

1. def L_R_move(start_str, end_str):
   
2.     # 检查长度
   
3.     if len(start_str) != len(end_str):
   
4.         return False
   
5.     key_str1 = ""
   
6.     key_str2 = ""
   
7.     # 检查LR框架
   
8.     for i in range(len(start_str)):
   
9.         if start_str[i] != "X":
   
10.             key_str1 += start_str[i]
    
11.         if end_str[i] != "X":
    
12.             key_str2 += end_str[i]
    
13.     if key_str1 != key_str2:
    
14.         return False
    
15.     i = 0
    
16.     j = 0
    
17.     # 判断移位操作是否可行
    
18.     for each in key_str1:
    
19.         point_s = start_str.find(each, i)
    
20.         point_e = end_str.find(each, j)
    
21.         if point_s <= point_e and each == "R" or point_s >= point_e and each == "L":
    
22.             i = point_s + 1
    
23.             j = point_e + 1
    
24.         else:
    
25.             return False
    
26.     else:
    
27.         return True
    

复制代码

思路：先检查长度及去X后LR的顺序与数量是否一致，
再根据LR在start与end字符串中的索引判断是否可以通过移位操作使得start变换到end

chen971130

1. def func(start, end, a, b, c):
   
2.     start,end = list(start),list(end)
   
3.     for i in range(len(start)-1):
   
4.         if start[i] == a and start[i+1] == b:
   
5.             if end[i] == a and end[i+1] == b:
   
6.                 continue
   
7.             elif end[i] == b and end[i+1] == b:
   
8.                 if start[i+c] == b and end[i+c] == a:
   
9.                     continue
   
10.                 else:
    
11.                     return False
    
12.             else:
    
13.                 return False
    
14.     else:
    
15.         return True
    
16. 
    
17. def a369(start,end):
    
18.     if len(start) != len(end):
    
19.         print('False')
    
20.     else:
    
21.         start1,end1 = start.replace('X', ''),end.replace('X', '')
    
22.         if start1 != end1:
    
23.             print('False')
    
24.         else:
    
25.             if func(start, end, 'X', 'R', -1) and func(start, end, 'L', 'X', 2):
    
26.                 print('True')
    
27.             else:
    
28.                 print('False')
    
29. 
    
30. a369("RXXLRXRXL", "XRLXXRRLX")  # True

复制代码

Joy187

def converse(start,end):
    for i in range(0,len(start)):
        if(start[i]=='X'):
            s = start.replace('X','')
        if(end[i]=='X'):
            e = end.replace('X','')
    if len(start)==len(end) and s==e:
        return True
    else:
        return False

ouyunfu

chen971130 发表于 2020-4-6 10:18
start = LX
end = XL
这种顺序相同但是也不能转换,因为只能按题目替换但是不能反过来替换吧

看来我理解错了，谢谢提醒

阴阳神万物主

难度评级：简单
要素分析：字符串 模拟
代码：

1. def solve(start:str,end:str)->bool:
   
2.     l = len(start)
   
3.     if l != len(end):#排除长度不等的错误选项
   
4.         return False
   
5.     elif start.replace('X','')!=end.replace('X',''):#排除顺序不对的错误选项
   
6.         return False
   
7.     sr,sl,er,el = 0,0,0,0
   
8.     for i in range(l):
   
9.         if start[i] == 'R':
   
10.             sr += 1
    
11.         elif start[i] == 'L':
    
12.             sl += 1
    
13.         if end[i] == 'R':
    
14.             er += 1
    
15.         elif end[i] == 'L':
    
16.             el += 1
    
17.         if er>sr or sl>el:#排除移动方向不对的错误选项
    
18.             return False
    
19.     return True
    
20. if __name__ == '__main__':
    
21.     print('示例 输出：',solve(start = "RXXLRXRXL", end = "XRLXXRRLX"))
    

复制代码

思路解说：
必然性：
1.长度不等的字符串不可能相等；
2.R与L的的顺序不准交换，得出顺序不同的不可能相等，且start与end中按照顺序，每一个R或L一一对应；
3.R只能右移，L只能左移，可以推出能移动成目标的条件：start中的每一个R不可以出现在end中对应R的右边，L不可以出现在左边。
巧解：
在相同长度的不等子串内start的R不能少于end中的，L不能多。
将复杂的排序问题转化成了简单的遍历计数问题。