鱼C论坛

 找回密码
 立即注册
查看: 2923|回复: 53

[已解决]Python:每日一题 357

[复制链接]
发表于 2020-3-22 21:17:08 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
今天的题目:


给定一组没有重复元素的单词 word,找出所有不同的索引对 (c, d),使得 words[c] + words[d] 可拼接成一个回文串。

示例 1:

输入:["abcd", "dcba", "lls", "s", "sssll"]
输出:[[0, 1], [1, 0], [3, 2], [2,4]]
解释:可拼接成的回文串为 ["dcbaabcd", "abcddcba", "slls", "llssssll"]
示例 2:

输入:["bat", "tab", "cat"]
输出:[[0, 1], [1, 0]]
解释:可拼接成的回文串为 ["battab", "tabbat"]


欢迎大家一起答题!
最佳答案
2020-3-22 22:05:58
  1. def fun357(word):
  2.     result = []
  3.     dict1 = {a: i for i, a in enumerate(word)}
  4.     for i, a in enumerate(word):
  5.         ma = len(a)
  6.         for j in range(ma + 1):
  7.             sa, st = a[:j], a[j:]
  8.             ssa, sst = sa[::-1], st[::-1]
  9.             if sa == ssa and sst in dict1:
  10.                 m = dict1[sst]
  11.                 if m != i: result.append([m, i])
  12.             if j != ma and st == sst and ssa in dict1:
  13.                 result.append([i, dict1[ssa]])
  14.     return result
复制代码

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-3-22 21:31:19 | 显示全部楼层
本帖最后由 TJBEST 于 2020-3-23 18:02 编辑

不知道这个二元序列的顺序是否任意?我的第一个实例测试,序对正确,但是顺序不太一样
  1. def fun357(words):
  2.     M = len(words)
  3.     len_arr = [len(i) for i in words]
  4.     result = []#考虑c==d的情况
  5.     for index in range(0,M):
  6.         P = len_arr[index]
  7.         P_str = words[index]
  8.         for inner in range(0,M):
  9.             Q = len_arr[inner]
  10.             Q_str = words[inner]
  11.             state = True
  12.             if P > Q:
  13.                 N = (P - Q)//2
  14.                 for other in range(0,Q):
  15.                     if P_str[other] != Q_str[-(other+1)]:
  16.                         state = False
  17.                         break
  18.                 if state == False:
  19.                     continue
  20.                 for other in range(0,N):
  21.                     if P_str[Q+other] != P_str[-(other+1)]:
  22.                         state = False
  23.                         break
  24.                 if state == True:
  25.                     result.append([index,inner])
  26.             elif P < Q:
  27.                 N = (Q - P)//2
  28.                 for other in range(0,P):
  29.                     if P_str[other] != Q_str[-(other+1)]:
  30.                         state = False
  31.                         break
  32.                 if state == False:
  33.                     continue
  34.                 for other in range(0,N):
  35.                     if Q_str[other] != Q_str[Q-P-(other+1)]:
  36.                         state = False
  37.                         break
  38.                 if state == True:
  39.                     result.append([index,inner])
  40.             else:
  41.                 for other in range(0,P):
  42.                     if P_str[other] != Q_str[-(other+1)]:
  43.                         state = False
  44.                         break
  45.                 if state == True:
  46.                     result.append([index,inner])
  47.     return [each for each in result if each[0]!=each[1]]#剔除自洽
复制代码

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-22 21:32:36 | 显示全部楼层
  1. def test(word):
  2.     result = []
  3.     for i in range(len(word)):
  4.         for j in range(len(word)):
  5.             if i == j:
  6.                 continue
  7.             joint = word[i] + word[j]
  8.             if joint == joint[::-1]:
  9.                 result.append([i, j])
  10.     return result
复制代码

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-22 21:38:13 | 显示全部楼层
  1. def fun357(list1):
  2.     result=[]
  3.     for i in range(len(list1)):
  4.         for j in range(i+1,len(list1)):
  5.             if i!=j:
  6.                 temp=list1[i]+list1[j]
  7.                 if temp==temp[::-1]:
  8.                     result.append([i,j])
  9.                 temp=list1[j]+list1[i]
  10.                 if temp==temp[::-1]:
  11.                     result.append([j,i])
  12.     return result

  13. print(fun357(["abcd", "dcba", "lls", "s", "sssll"]))
  14. print(fun357(["bat", "tab", "cat"]))
复制代码

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-22 21:48:58 | 显示全部楼层
先占楼,昨天的没看到都解决了,没法回答了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-22 21:56:14 | 显示全部楼层
一个愚蠢的方法
  1. def f357(list1):
  2.     lst=[]
  3.     for i in range(len(list1)):
  4.         for j in range(len(list1)):
  5.             tmp=list(list1[i] + list1[j])
  6.             tmp.reverse()
  7.             if list(list1[i]+list1[j])==tmp:
  8.                 if i!=j:
  9.                     lst.append([i,j])
  10.     return lst
复制代码

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-22 22:05:58 | 显示全部楼层    本楼为最佳答案   
  1. def fun357(word):
  2.     result = []
  3.     dict1 = {a: i for i, a in enumerate(word)}
  4.     for i, a in enumerate(word):
  5.         ma = len(a)
  6.         for j in range(ma + 1):
  7.             sa, st = a[:j], a[j:]
  8.             ssa, sst = sa[::-1], st[::-1]
  9.             if sa == ssa and sst in dict1:
  10.                 m = dict1[sst]
  11.                 if m != i: result.append([m, i])
  12.             if j != ma and st == sst and ssa in dict1:
  13.                 result.append([i, dict1[ssa]])
  14.     return result
复制代码

评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zltzlt + 5 + 5

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-22 22:06:51 | 显示全部楼层
本帖最后由 kinkon 于 2020-3-23 11:37 编辑

先跑起来,速度有点慢,后面再想其他办法
  1. def f357(arr):
  2.     s, res = len(arr), []
  3.     tmp = tmp1 = ''
  4.     for i in range(s-1):
  5.         for j in range(i+1, s):
  6.             tmp = arr[i] + arr[j]
  7.             tmp1 = arr[j] + arr[i]  
  8.             if tmp == tmp[::-1]:
  9.                 res += [[i,j]]
  10.             if tmp1 == tmp1[::-1]:
  11.                 res += [[j,i]]
  12.                     
  13.     return res
复制代码

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-22 22:22:36 | 显示全部楼层
  1. def function(list1):
  2.     def f(s):
  3.         if len(s)%2 == 0:
  4.             s1 = s[:int(len(s)/2)] + s[:int(len(s)/2)][::-1]
  5.         else:
  6.             s1 = s[:int(len(s)/2)+1] + s[:int(len(s)/2)][::-1]
  7.         if s1 == s:
  8.             return True
  9.         else:
  10.             return False
  11.     list2 = []
  12.     for i in range(len(list1)):
  13.         for j in range(len(list1)):
  14.             if i != j:
  15.                 if f(list1[i]+list1[j]):
  16.                     list2.append([i,j])
  17.     return list2
复制代码

评分

参与人数 1荣誉 +4 鱼币 +2 收起 理由
zltzlt + 4 + 2

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-22 22:30:50 | 显示全部楼层
本帖最后由 永恒的蓝色梦想 于 2020-3-23 10:17 编辑

没想到啥好方法
  1. from itertools import permutations as perm

  2. def function(word):
  3.     result=[]

  4.     for i,j in perm(range(len(word)),2):
  5.         k=word[i]+word[j]

  6.         if k==k[::-1]:
  7.             result.append([i,j])

  8.     return result
复制代码

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-22 22:44:58 | 显示全部楼层
本帖最后由 flamezyy 于 2020-3-22 23:25 编辑
  1. def f357(arr):
  2.     result = []
  3.     for each in map(lambda i : (i[0]+i[1],i[0],i[1]), [(x , y) for x in arr for y in arr]):
  4.         if each[1] != each[2]:
  5.             if each[0] == each[0][::-1]:
  6.                 result.append([arr.index(each[1]),arr.index(each[2])])
  7.             else:
  8.                 continue
  9.         else:
  10.             continue
  11.     else:
  12.         return result
复制代码

做题可太有意思了

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-23 00:43:30 | 显示全部楼层
  1. def fun357(lst):
  2.     if not len(lst):return 0
  3.     result=[]
  4.     for i in range(len(lst)):
  5.         for j in range(len(lst)):
  6.             if i!=j and lst[j][::-1].startswith(lst[i]):
  7.                 result.append([i,j])
  8.     return result
复制代码

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-23 04:25:08 | 显示全部楼层
本帖最后由 ouyunfu 于 2020-3-23 04:35 编辑
  1. from itertools import permutations as p
  2. def f357(words:list)->list:
  3.     L=[]
  4.     for i in p(range(len(words)),2):
  5.         a=words[i[0]]+words[i[1]]
  6.         if a[::-1]==a:
  7.             L.append(list(i))
  8.     return L
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-23 04:40:39 | 显示全部楼层
本帖最后由 ouyunfu 于 2020-3-23 04:42 编辑

尝试一行代码
  1. from itertools import permutations as p
  2. def f357(w):
  3.     return [list(i) for i in p(range(len(w)),2) if (w[i[0]]+w[i[1]])[::-1]==w[i[0]]+w[i[1]]]
复制代码

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-23 07:27:45 | 显示全部楼层
先插个眼看大佬打架
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-23 12:16:06 | 显示全部楼层
  1. from itertools import permutations

  2. def fun357(words):
  3.     result = []
  4.     for i in permutations([j for j in range(len(words))],2):
  5.         combination = words[i[0]] + words[i[1]]
  6.         if combination == combination[::-1]:
  7.             result.append([i[0],i[1]])
  8.     return result
复制代码

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-23 12:48:18 | 显示全部楼层
一行式
  1. def fun357(lst):
  2.     if not len(lst):return 0
  3.     return [[i,j] for i in range(len(lst)) for j in range(len(lst)) if i!=j and lst[j][::-1].startswith(lst[i])]
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-23 13:08:08 | 显示全部楼层
def huiwen(list1):
    list2 = []
    for i in range(len(list1)):
        for j in range(len(list1)):
            if j == i:
                continue
            else:
                str1 = list1[i] + list1[j]
                if str1 == str1[::-1]:
                    list2.append((i,j))
    return list2
list1 = ["abcd", "dcba", "lls", "s", "sssll"]
print(huiwen(list1))

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-23 13:08:25 | 显示全部楼层

def is_palindromic(str1, str2):
    determine = str1 + str2
    if determine == determine[::-1]:
        return True
    else:
        return False


def joint_palindromic(words):
    words_num = len(words)
    result = []
    for i in range(words_num):
        for j in range(i+1, words_num):
            if is_palindromic(words[i], words[j]):
                result.append([i, j])
            if is_palindromic(words[j], words[i]):
                result.append([j, i])
    return result

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-3-23 13:10:27 | 显示全部楼层
  1. def hw(x):
  2.     a = list(x)
  3.     if a == list(reversed(a)):
  4.         return 1
  5.     else:
  6.         return 0
  7. def f357(x):
  8.     b = []
  9.     for i in range(len(x)):
  10.         for j in range(len(x)):
  11.             if i != j:
  12.                 c = x[i] + x[j]
  13.                 if hw(c) == 1:
  14.                     b.append([i, j])
  15.     return b
复制代码

先发一个暴力法,再看看能不能优化

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zltzlt + 3 + 3

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 23:14

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表