[已解决]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

def daily369(start: str, end: str) -> bool:
    # 解题思路
    # L和R必不可能交换位置 -> judge the order of L and R
    # L的右边和R的左边的X数量只会减少 -> L的index只能减小，R的index只能增大
    # -> the index of L and R in start and end
    if len(start) != len(end):
        return False
    if start.replace('X', '') != end.replace('X', ''):
        return False
    start_index, end_index = [[], []], [[], []]
    for i in range(len(start)):
        if start[i] == 'L':
            start_index[0].append(i)
        elif  start[i] == 'R':
            start_index[1].append(i)
        if end[i] == 'L':
            end_index[0].append(i)
        elif end[i] == 'R':
            end_index[1].append(i)
    for i in range(len(start_index[0])):
        if start_index[0][i] < end_index[0][i]:
            return False
    for i in range(len(start_index[1])):
        if start_index[1][i] > end_index[1][i]:
            return False
    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可以借用不

可以呀

塔利班

def f369(start,end):
    s,e=len(start),len(end)
    if start==end:
        return True
    elif s!=e:
        return False
    else:
        for i in range(s):
            if start[i]==end[i]:
                continue
            elif i<s-1:
                t=start[i:i+2] 
                if t=='XL':
                    return f369('LX'+start[i+2:],end[i:])
                elif t=='RX':
                    return f369('XR'+start[i+2:],end[i:])
                else:
                    return False
            else:
                return False

多点测试用例就好了

TJBEST

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

def fun369(start,end):
    def inner(string,position):
        if string == end:
            return True
        elif len(start)!=len(end):
            return False
        for index in range(position,M-1):
            if string[index] == 'X' and string[index+1]=='L':        
                if inner(string,index+1):
                    return True
                else:
                    temp = string[:index] + 'LX' + string[(index+2):]
                    if inner(temp,0):
                        return True
            elif string[index] == 'R' and string[index+1]=='X':
                if inner(string,index+1):
                    return True
                else:
                    temp = string[:index] + 'XR' + string[(index+2):]
                    if inner(temp,0):
                        return True
            else:
                pass
        return False
    M = len(start)
    return inner(start,0)

March2615

def daily369(start: str, end: str) -> bool:
    # 解题思路
    # L和R必不可能交换位置 -> judge the order of L and R
    # L的右边和R的左边的X数量只会减少 -> L的index只能减小，R的index只能增大
    # -> the index of L and R in start and end
    if len(start) != len(end):
        return False
    if start.replace('X', '') != end.replace('X', ''):
        return False
    start_index, end_index = [[], []], [[], []]
    for i in range(len(start)):
        if start[i] == 'L':
            start_index[0].append(i)
        elif  start[i] == 'R':
            start_index[1].append(i)
        if end[i] == 'L':
            end_index[0].append(i)
        elif end[i] == 'R':
            end_index[1].append(i)
    for i in range(len(start_index[0])):
        if start_index[0][i] < end_index[0][i]:
            return False
    for i in range(len(start_index[1])):
        if start_index[1][i] > end_index[1][i]:
            return False
    return True

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

kinkon

def f369(start, end):#双针法

    if start.count('X') != end.count('X'):
        return False
    m, n = len(start)-1, len(end)-1
    x = y = 0
    while x <= m and y <= n:
        while x < m and start[x] == 'X':
            x += 1
        while y < n and end[y] == 'X':
            y += 1
        #L和R不能相互穿过
        #print(start[x], end[y])
        if start[x] != end[y]:
            return False
        #L只能往左移动
        elif start[x] == 'L' and end[y] == 'L':
            if x < y:
                return False
        #R只能往右移动
        elif start[x] == 'R' and end[y] == 'R':
            if x > y:
                return False
            
        x += 1
        y += 1
    return True  

ouyunfu

import re
def f369(start,end):
    if start.replace('X','')!=end.replace('X',''):
        return False
    elif len(start)!=len(end):
        return False
    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)]:
        return True
    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

import re    
def fun369(start,end):
    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

风魔孤行者

def f(start,end):
    s = start.replace('X','')
    e = end.replace('X','')
    if len(start)==len(end) and s==e:
        return True
    else:
        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

def L_R_move(start_str, end_str):
    # 检查长度
    if len(start_str) != len(end_str):
        return False
    key_str1 = ""
    key_str2 = ""
    # 检查LR框架
    for i in range(len(start_str)):
        if start_str[i] != "X":
            key_str1 += start_str[i]
        if end_str[i] != "X":
            key_str2 += end_str[i]
    if key_str1 != key_str2:
        return False
    i = 0
    j = 0
    # 判断移位操作是否可行
    for each in key_str1:
        point_s = start_str.find(each, i)
        point_e = end_str.find(each, j)
        if point_s <= point_e and each == "R" or point_s >= point_e and each == "L":
            i = point_s + 1
            j = point_e + 1
        else:
            return False
    else:
        return True

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

chen971130

def func(start, end, a, b, c):
    start,end = list(start),list(end)
    for i in range(len(start)-1):
        if start[i] == a and start[i+1] == b:
            if end[i] == a and end[i+1] == b:
                continue
            elif end[i] == b and end[i+1] == b:
                if start[i+c] == b and end[i+c] == a:
                    continue
                else:
                    return False
            else:
                return False
    else:
        return True

def a369(start,end):
    if len(start) != len(end):
        print('False')
    else:
        start1,end1 = start.replace('X', ''),end.replace('X', '')
        if start1 != end1:
            print('False')
        else:
            if func(start, end, 'X', 'R', -1) and func(start, end, 'L', 'X', 2):
                print('True')
            else:
                print('False')

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
这种顺序相同但是也不能转换,因为只能按题目替换但是不能反过来替换吧

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

阴阳神万物主

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

def solve(start:str,end:str)->bool:
    l = len(start)
    if l != len(end):#排除长度不等的错误选项
        return False
    elif start.replace('X','')!=end.replace('X',''):#排除顺序不对的错误选项
        return False
    sr,sl,er,el = 0,0,0,0
    for i in range(l):
        if start[i] == 'R':
            sr += 1
        elif start[i] == 'L':
            sl += 1
        if end[i] == 'R':
            er += 1
        elif end[i] == 'L':
            el += 1
        if er>sr or sl>el:#排除移动方向不对的错误选项
            return False
    return True
if __name__ == '__main__':
    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不能多。
将复杂的排序问题转化成了简单的遍历计数问题。