Python：每日一题 369,Python交流,编程语言专区,鱼C论坛

zltzlt 发表于 2020-4-5 17:50:22

Python：每日一题 369

今天的题目：

在一个由 '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

{:10_298:}欢迎大家一起答题！{:10_298:}

fan1993423 发表于 2020-4-5 18:10:55

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

zltzlt 发表于 2020-4-5 18:11:53

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

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

fan1993423 发表于 2020-4-5 18:16:17

本帖最后由 fan1993423 于 2020-4-5 18:22 编辑

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

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

zltzlt 发表于 2020-4-5 18:17:01

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

可以呀

塔利班 发表于 2020-4-5 19:09:29

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==end:
            continue
         elif i<s-1:
            t=start
            if t=='XL':
               return f369('LX'+start,end)
            elif t=='RX':
               return f369('XR'+start,end)
            else:
               return False
         else:
            return False
多点测试用例就好了

TJBEST 发表于 2020-4-5 19:58:28

本帖最后由 TJBEST 于 2020-4-7 09:58 编辑

来一个无脑的算法，后面有更好的在更改。
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 == 'X' and string=='L':
            if inner(string,index+1):
               return True
            else:
               temp = string[:index] + 'LX' + string[(index+2):]
               if inner(temp,0):
                     return True
         elif string == 'R' and string=='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 发表于 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 == 'L':
         start_index.append(i)
   elifstart == 'R':
         start_index.append(i)
   if end == 'L':
         end_index.append(i)
   elif end == 'R':
         end_index.append(i)
for i in range(len(start_index)):
   if start_index < end_index:
         return False
for i in range(len(start_index)):
   if start_index > end_index:
         return False
return True

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

kinkon 发表于 2020-4-5 21:37:13

本帖最后由 kinkon 于 2020-4-6 15:16 编辑

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 += 1
   while y < n and end == 'X':
         y += 1
   #L和R不能相互穿过
   #print(start, end)
   if start != end:
         return False
   #L只能往左移动
   elif start == 'L' and end == 'L':
         if x < y:
            return False
   #R只能往右移动
   elif start == 'R' and end == 'R':
         if x > y:
            return False

   x += 1
   y += 1
return True

ouyunfu 发表于 2020-4-5 22:38:28

本帖最后由 ouyunfu 于 2020-4-6 15:55 编辑

import re
def f369(start,end):
if start.replace('X','')!=end.replace('X',''):
   return False
elif len(start)!=len(end):
   return False
elif <= and >=:
   return True
else:return False

whosyourdaddy 发表于 2020-4-5 22:51:33

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=='X'):
         i += 1
         if i == (a-1):
            break
   while(end=='X'):
         j += 1
         if j==(b-1):
            break
   if start!= end:
         return False
   if start=='L' and i<j:
         return False
   if start=='R' and j<i:
         return False
   i += 1
   j += 1
return True

ouyunfu 发表于 2020-4-5 23:25:44

本帖最后由 ouyunfu 于 2020-4-6 15:51 编辑

import re
def fun369(start,end):
return True if start.count('X')==end.count('X') and start.replace('X','')==end.replace('X','') and <= and >= else False

风魔孤行者 发表于 2020-4-6 10:00:46

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 发表于 2020-4-6 10:18:00

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

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

永恒的蓝色梦想 发表于 2020-4-6 10:29:07

zhanlou

旅途Z 发表于 2020-4-6 11:51:26

本帖最后由旅途Z 于 2020-4-8 22:35 编辑

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 != "X":
         key_str1 += start_str
   if end_str != "X":
         key_str2 += end_str
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 发表于 2020-4-6 12:14:33

本帖最后由 chen971130 于 2020-4-6 12:21 编辑

def func(start, end, a, b, c):
start,end = list(start),list(end)
for i in range(len(start)-1):
   if start == a and start == b:
         if end == a and end == b:
            continue
         elif end == b and end == b:
            if start == b and end == 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 发表于 2020-4-6 12:50:39

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

ouyunfu 发表于 2020-4-6 13:34:00

本帖最后由 ouyunfu 于 2020-4-6 13:39 编辑

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

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

阴阳神万物主 发表于 2020-4-6 13:59:43

难度评级：简单
要素分析：字符串模拟
代码：
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 == 'R':
         sr += 1
   elif start == 'L':
         sl += 1
   if end == 'R':
         er += 1
   elif end == '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不能多。
将复杂的排序问题转化成了简单的遍历计数问题。

页: [1] 2

鱼C论坛's Archiver

Python：每日一题 369