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

zltzlt

今天的题目：

给定一个字符串 s，判断是否能重新排列其中的字母，使得任意两相邻的字符都不同。

若可行，输出任意可行的结果；若不可行，返回空字符串。

示例 1：

输入：s = "aab"
输出："aba"

示例 2：

输入：s = "aaab"
输出：""

欢迎大家一起答题！

最佳答案

月排行榜 / 总排行榜

旅途Z

2020-4-1 23:54:44

import operator
from math import ceil


def dif_neighbor(string):
    length = len(string)
    letter_dict = {}
    resorted_str = ""
    for letter in string:
        if letter not in letter_dict:
            letter_dict[letter] = 0
        letter_dict[letter] += 1
    sorted_letter = sorted(letter_dict.items(), key=operator.itemgetter(1), reverse=True)
    most_letter_nums = sorted_letter[0][1]
    if most_letter_nums <= ceil(length/2):
        transform_list = [0 for j in range(length)]
        i = 0
        j = 0
        while i < length:
            nums = sorted_letter[j][1]
            transform_list[i: i+nums] = [sorted_letter[j][0] for each in range(i, i+nums)]
            i += nums
            j += 1
        for index in range(most_letter_nums):
            moved_index = index
            while moved_index < length:
                resorted_str += transform_list[moved_index]
                moved_index += most_letter_nums
        return resorted_str
    else:
        return ""

跳转到最佳答案楼层

一个账号

好像有两个每日一题 364

zltzlt

一个账号 发表于 2020-3-31 17:55
好像有两个每日一题 364

？

xiangjianshinan

没有思路！想到是否用set来处理。

BngThea

1. 
   
2. from collections import Counter
   
3. def fun365(s):
   
4.     length = len(s)
   
5.     c= Counter(s)
   
6.     lst = sorted(c.items(),key=lambda item: item[1],reverse=True)
   
7.     lenc = lst[0][1]
   
8.     if (length<2) or (length==2 and len(c.keys())==2) or (length==3 and len(c.keys())==3):
   
9.         return s
   
10.     elif length==3 and len(c.keys()) > 1:
    
11.         return lst[0][0]+lst[1][0]+lst[0][0]
    
12.     elif  lenc < length-1:
    
13.         tmp = list(s)
    
14.         res = lst[0][0]
    
15.         tmp.remove(res)
    
16.         for i in range(length-1):
    
17.             for j in range(length-i-1):
    
18.                 if res[-1] != tmp[j]:
    
19.                     break               
    
20.             res += tmp.pop(j)
    
21.         return res
    
22.     else:
    
23.         return ""
    

复制代码

永恒的蓝色梦想

占楼

March2615

我就说怎么就少了两天的题，原来是没有363

1. def daily364(S: str) -> str:
   
2.     # 几种情况
   
3.     # 1. 最多的字符超过len(S)//2(偶)、len(S)//2+1(奇) -> return ''
   
4.     # 2. 不满足1，对s进行排序，使相同字符相邻
   
5.     # 3. 分成前后两段，交叉重排；如果是奇数->中间的放在最后
   
6.     if len(S) < 2:
   
7.         return S
   
8.     sort_list = sorted(sorted(S), key=lambda x: S.count(x))
   
9.     n = len(sort_list) // 2
   
10.     if sort_list[n - 1] == sort_list[-1]:  # 条件1
    
11.         return ''
    
12.     result = sort_list[:]  # 创建一个一样长的列表保存答案
    
13.     left, right = sort_list[:n], sort_list[n:]  # len(left) <= len(right)
    
14.     for i in range(len(left)):
    
15.         result[2 * i + 1] = left[i]
    
16.     for i in range(len(right)):
    
17.         result[2 * i] = right[i]
    
18.     return ''.join(result)

复制代码

吐了，调试了好久发现是个小错误，偏偏还看不出来
今天就这样了，感觉还能改进，等明天写完了再发

TJBEST

不是最快的应该，但是最好想。非常朴素

1. def fun365(s):
   
2.     #复杂度O(n)
   
3.     M = len(s)
   
4.     dic = {}
   
5.     for each in s:
   
6.         try:
   
7.             dic[each] += 1
   
8.         except Exception:
   
9.             dic[each] = 1
   
10.     itemArr = list(dic.items())
    
11.     itemArr.sort(key = lambda each:each[1],reverse = True)
    
12.     if itemArr[0][1] > (M+1)//2:
    
13.         return ''
    
14.     N = len(itemArr)
    
15.     firstGate = (M+1)//2
    
16.     tempList = [0]*M
    
17.     firstHas = 0
    
18.     for first in range(0,N):
    
19.         charcter = itemArr[first][0]
    
20.         count = itemArr[first][1]
    
21.         newEnd = firstHas + count
    
22.         if newEnd > firstGate:
    
23.             tempList[(2*firstHas):(2*firstGate):2] = charcter*(firstGate-firstHas)
    
24.             secondHas = newEnd - firstGate
    
25.             tempList[1:(2*secondHas+1):2] = charcter*secondHas
    
26.             start = first + 1
    
27.             break
    
28.         else:
    
29.             tempList[(2*firstHas):(2*newEnd):2] = charcter*(newEnd-firstHas)
    
30.             firstHas = newEnd
    
31.     for second in range(start,N):
    
32.         charcter = itemArr[second][0]
    
33.         count = itemArr[second][1]
    
34.         newEnd = secondHas + count
    
35.         tempList[(2*secondHas+1):(2*newEnd+1):2] = charcter*(newEnd-secondHas)
    
36.         secondHas = newEnd
    
37.     result = ''
    
38.     for each in tempList:
    
39.         result += each
    
40.     return result

复制代码

ouyunfu

1. def f365(s:str)->str:
   
2.     s0=list(s)
   
3.     s1=set(s)
   
4.     s2=[s.count(i) for i in s1]
   
5.     m=[i for i in s1 if s.count(i)==max(s2)]
   
6.     L=[m[0]]
   
7.     s0.remove(m[0])
   
8.     Flag=1
   
9.     while Flag:
   
10.         for i in s0:
    
11.             if i!=L[-1]:
    
12.                 L.append(i)
    
13.                 s0.remove(i)
    
14.                 break
    
15.         else:Flag=0
    
16.     if len(L)==len(s):
    
17.         return ''.join(L)
    
18.     else:
    
19.         return ''

复制代码

l0stparadise

1. def f365(s):
   
2.     s_list=[0]*len(s)
   
3.     num_count={}
   
4.     for i in s:
   
5.         num_count[i]=num_count.get(i,0)+1
   
6.     s_temp_list=[]
   
7.     num_count_sorted=sorted(num_count.items(),key=lambda x:x[1],reverse=True)
   
8.     for key_values in num_count_sorted:
   
9.         if key_values[1] > (len(s)+1)/2:
   
10.             return ""
    
11.         else:
    
12.             for j in range(key_values[1]):
    
13.                 s_temp_list.append(key_values[0])
    
14.     n=0
    
15.     for i in range(0,len(s),2):
    
16.         s_list[i]=s_temp_list[n]
    
17.         n+=1
    
18.     for i in range(1,len(s),2):
    
19.         s_list[i]=s_temp_list[n]
    
20.         n+=1
    
21.     str1 = ""
    
22.     for _ in s_list:
    
23.         str1 += _
    
24.     return str1

复制代码

archlzy

1. def fun365(string):
   
2.     string_list = [i for i in string[1:]]
   
3.     res = [string[0]]
   
4.     bool_while = True
   
5.     while bool_while:
   
6.         m = len(string_list)
   
7.         temp = []
   
8.         for i in string_list:
   
9.             for j in range(len(res)):
   
10.                 try:
    
11.                     if i != res[j] and i!= res[j+1]:
    
12.                         res.insert(j+1,i)
    
13.                         break
    
14.                 except IndexError:
    
15.                     if i != res[j]:
    
16.                         res.insert(j+1,i)
    
17.                         break
    
18.             else:
    
19.                 if i != res[0]:
    
20.                     res.insert(0,i)
    
21.                 else:
    
22.                     temp.append(i)
    
23.         string_list = temp
    
24.         if len(string_list) == m:
    
25.             bool_while = False
    
26.     if len(string_list):
    
27.         return ''
    
28.     else:
    
29.         return ''.join(res)

复制代码

sYMMetrY

1. def f365(string):
   
2.     new_st = ''
   
3.     dict_string = dict(zip(list(string),[0]*(len(string))))
   
4.     for each in string:
   
5.         dict_string[each] += 1
   
6. 
   
7.     #若字符串中一个元素出现的最大次数超过一半（奇数加一的一半，偶数的一半）则返回空字符串
   
8.     if max(dict_string.values()) > ((len(string)+1)//2):
   
9.         return new_st
   
10.    
    
11.     #剩余的情况返回字符串
    
12.     else:
    
13.         values = list(dict_string.values()).sort() #对每个元素出现的频次进行排序
    
14. 
    
15.         #对字符串重新排序，依照元素频次高低对元素排列
    
16.         i = 0
    
17.         for each in dict_string:            
    
18.             j = dict_string[each]
    
19.             if j >= i:
    
20.                 while dict_string[each]:                        
    
21.                     new_st = each + new_st
    
22.                     dict_string[each] -= 1
    
23. 
    
24.             else:
    
25.                 while dict_string[each]:                        
    
26.                     new_st = new_st + each
    
27.                     dict_string[each] -= 1
    
28.             i = j
    
29.         #将新排列的字符串平分为两部门[前半部分:后半部分]，并将后半部分间隔插入前半部分字符串中        
    
30.         if len(string)%2 == 0:#偶数情况直接平分        
    
31.             st1 = new_st[:((len(string)+1)//2)]
    
32.             st2 = new_st[((len(string)+1)//2):]
    
33.         else:#考虑到map函数在此情况下两段字符串数量不一致（前半部分多一个元素）会少输出一组，人为引入一个元素
    
34.             st1 = new_st[:((len(string)+1)//2)]   
    
35.             st2 = new_st[((len(string)+1)//2):] + 'X'
    
36. 
    
37.         st_l = list(map(lambda i,j: i+j, st1, st2))               
    
38. 
    
39.         if len(string)%2 == 0:
    
40.             return ''.join(st_l)#偶数情况直接得到真值
    
41.         else:
    
42.             return ''.join(st_l)[:-1]#将引入的元素去除，返回真值
    

复制代码

sjtuszy

1. def fun365(s):
   
2.     list_sort = sorted(sorted(s), key = lambda x : s.count(x), reverse = True)      #按字母的数量从多到少重排
   
3.     if list_sort.count(list_sort[0]) - 1 > len(s) - list_sort.count(list_sort[0]):  #最多的字母中间的“空”若不够其他所有字母来插空，则返回''
   
4.         return ''
   
5.     else:
   
6.         list_1 = list_sort[:list_sort.count(list_sort[0])]                          #最多的字母成list_1列，其余所有字母成list_2列
   
7.         list_2 = list_sort[list_sort.count(list_sort[0]):]
   
8.         i = 0
   
9.         for each in list_2:
   
10.             list_1[i % len(list_1)] += each                                         #list_2中的字母依次从左开始插在list_1的字母后边，插到list_1最后则再一次从左开始
    
11.             i += 1
    
12.         return ''.join(list_1)

复制代码

尤思帆

这个题目对小白好像很不友好

hhb1988

1. def fun365(s):   
   
2.     length = len(s)
   
3.     if length%2:
   
4.         max_num = length/2 + 1
   
5.     else:
   
6.         max_num = length/2
   
7.     letter = {}
   
8.     most_num = 0
   
9.     for i in s:
   
10.         if i in letter.keys():
    
11.             letter[i] += 1
    
12.         else:
    
13.             letter[i] = 1
    
14.             
    
15.         if letter[i] > most_num:
    
16.             most_num = letter[i]
    
17.             most_letter = i
    
18.             if most_num > max_num:
    
19.                 return ''
    
20.    
    
21.     index = 0
    
22.     new_list = []
    
23.     for i in range(length):
    
24.         new_list.append('*')
    
25.               
    
26.     for i in range(most_num):
    
27.         new_list[index] = most_letter
    
28.         index += 2
    
29.    
    
30.     letter[most_letter] = 0   
    
31.     for i in letter:
    
32.         while letter[i]>0:
    
33.             if index > length:
    
34.                 index = 1
    
35.             
    
36.             new_list[index] = i
    
37.             index +=2
    
38.             letter[i] -= 1
    
39.    
    
40.     new_s = ''
    
41.     for i in range(len(new_list)):
    
42.         new_s = new_s + new_list[i]
    
43.         
    
44.     return str(new_s)
    
45. 
    
46. 
    
47. s = str(input("请输入一个字符串:"))
    
48. string = fun365(s)
    
49. print(string)
    

复制代码

kinkon

1. from collections import Counter
   
2. def f365(s):
   
3.     num = Counter(s)
   
4.     if max(num.values()) > (len(s)+1)//2:
   
5.         return ''            
   
6.     num = sorted(num.items(),key=lambda x:x[1],reverse=True)   
   
7.     num = [list(n) for n in num]
   
8.     rec = []
   
9.     l, r = 0, len(num)-1
   
10.     while l < r:
    
11.         if num[l][1] == 0:
    
12.             l += 1   
    
13.         rec += num[l][0]
    
14.         num[l][1] -= 1
    
15.         if num[r][1] == 0:
    
16.             r -= 1        
    
17.         rec += num[r][0]
    
18.         num[r][1] -= 1
    
19.     rec = rec[:len(s)]
    
20.     l, r = 0, len(rec)-1
    
21.     while rec[r] == rec[r-1]:        
    
22.         rec[l], rec[r-1] = rec[r-1], rec[l]
    
23.         l += 3
    
24.         r -= 1
    
25.     return ''.join(rec)

复制代码

NAMELESSONE

1. def solve(s:str):
   
2.     su = 0
   
3.     d = { }
   
4.     mx = 0
   
5.     l=[]
   
6.     string = list(set(s))
   
7.     string.sort()
   
8.     for i in string:
   
9.         count = s.count(i)
   
10.         if mx < count:
    
11.             mx = count
    
12.             word=i
    
13.         su += count
    
14.         d[i] = count
    
15.        # print(mx,su)
    
16.     if mx > su-mx+1:
    
17.         return ""
    
18.     string.remove(word)
    
19.     for i in string:
    
20.         l += [i]*d[i]
    
21.     l += [word]*mx
    
22.     string=''
    
23.     for i in range(len(l)//2):
    
24.         string += l[len(l)//2+i]
    
25.         string+=l[i]
    
26.     if su%2!=0:
    
27.         string+=l[-1]
    
28.     return string

复制代码

raimond

1. import itertools
   
2. 
   
3. def func(string):
   
4.     length = (len(string))
   
5.     string_list = []
   
6.     new_string = ''
   
7.     count = 0
   
8. 
   
9.     if length > 1:
   
10.         str_list = itertools.permutations(string, length)
    
11.         for i in str_list:
    
12.             for num in range(len(i) - 1):
    
13.                 if i[num] == i[num + 1]:
    
14.                     count = 1
    
15.                     new_string = ''
    
16.                     break
    
17.                 else:
    
18.                     new_string += i[num]
    
19.             if count != 1:
    
20.                 new_string += i[-1]
    
21.                 if new_string not in string_list:
    
22.                     string_list.append(new_string)
    
23.                     print(new_string)
    
24. 
    
25.             count = 0
    
26.             new_string = ''
    
27. 
    
28.         if string_list == []:
    
29.             print('""')
    
30. 
    
31.     elif length == 1:
    
32.         print(string)
    
33. 
    
34.     else:
    
35.         print('""')
    
36. 
    
37. str1 = input('请输入一个字符串:')
    
38. func(str1)

复制代码

风魔孤行者

1. def f(s):
   
2.     dict1 = {}
   
3.     for each in s:
   
4.         if each in dict1.keys():
   
5.             dict1[each] += 1
   
6.         else:
   
7.             dict1.setdefault(each,1)
   
8.     max1 = max(dict1.values())
   
9.     if max1*2-1 > len(s):
   
10.         return ''
    
11.     else:
    
12.         a = 1
    
13.         while a <len(s):
    
14.             if s[a] == s[a-1]:
    
15.                 b = s[a]
    
16.                 s = s[:a]+s[a+1:]
    
17.                 if b != s[0]:
    
18.                     s = b+s
    
19.                 else:
    
20.                     for each in range(2,len(s)):
    
21.                         if b != s[each] and b != s[each-1]:
    
22.                             s = s[:each]+b+s[each:]
    
23.                             if each < a:
    
24.                                 a+1
    
25.                             else:
    
26.                                 a = a
    
27.             else:
    
28.                 a += 1
    
29.         return s
    

复制代码

旅途Z

import operator
from math import ceil


def dif_neighbor(string):
    length = len(string)
    letter_dict = {}
    resorted_str = ""
    for letter in string:
        if letter not in letter_dict:
            letter_dict[letter] = 0
        letter_dict[letter] += 1
    sorted_letter = sorted(letter_dict.items(), key=operator.itemgetter(1), reverse=True)
    most_letter_nums = sorted_letter[0][1]
    if most_letter_nums <= ceil(length/2):
        transform_list = [0 for j in range(length)]
        i = 0
        j = 0
        while i < length:
            nums = sorted_letter[j][1]
            transform_list[i: i+nums] = [sorted_letter[j][0] for each in range(i, i+nums)]
            i += nums
            j += 1
        for index in range(most_letter_nums):
            moved_index = index
            while moved_index < length:
                resorted_str += transform_list[moved_index]
                moved_index += most_letter_nums
        return resorted_str
    else:
        return ""