Python：每日一题 365
本帖最后由 zltzlt 于 2020-3-31 17:53 编辑今天的题目：
给定一个字符串 s，判断是否能重新排列其中的字母，使得任意两相邻的字符都不同。
若可行，输出任意可行的结果；若不可行，返回空字符串。
示例 1：
输入：s = "aab"
输出："aba"
示例 2：
输入：s = "aaab"
输出：""
{:10_298:}欢迎大家一起答题！{:10_298:} 好像有两个每日一题 364 一个账号 发表于 2020-3-31 17:55
好像有两个每日一题 364
？ 没有思路！想到是否用set来处理。 本帖最后由 BngThea 于 2020-4-2 13:43 编辑
from collections import Counter
def fun365(s):
length = len(s)
c= Counter(s)
lst = sorted(c.items(),key=lambda item: item,reverse=True)
lenc = lst
if (length<2) or (length==2 and len(c.keys())==2) or (length==3 and len(c.keys())==3):
return s
elif length==3 and len(c.keys()) > 1:
return lst+lst+lst
eliflenc < length-1:
tmp = list(s)
res = lst
tmp.remove(res)
for i in range(length-1):
for j in range(length-i-1):
if res[-1] != tmp:
break
res += tmp.pop(j)
return res
else:
return ""
占楼 本帖最后由 March2615 于 2020-3-31 21:28 编辑
我就说怎么就少了两天的题，原来是没有363
def daily364(S: str) -> str:
# 几种情况
# 1. 最多的字符超过len(S)//2(偶)、len(S)//2+1(奇) -> return ''
# 2. 不满足1，对s进行排序，使相同字符相邻
# 3. 分成前后两段，交叉重排；如果是奇数->中间的放在最后
if len(S) < 2:
return S
sort_list = sorted(sorted(S), key=lambda x: S.count(x))
n = len(sort_list) // 2
if sort_list == sort_list[-1]:# 条件1
return ''
result = sort_list[:]# 创建一个一样长的列表保存答案
left, right = sort_list[:n], sort_list# len(left) <= len(right)
for i in range(len(left)):
result = left
for i in range(len(right)):
result = right
return ''.join(result)
吐了，调试了好久发现是个小错误，偏偏还看不出来{:10_284:}
今天就这样了，感觉还能改进，等明天写完了再发 本帖最后由 TJBEST 于 2020-3-31 22:55 编辑
不是最快的应该，但是最好想。非常朴素
def fun365(s):
#复杂度O(n)
M = len(s)
dic = {}
for each in s:
try:
dic += 1
except Exception:
dic = 1
itemArr = list(dic.items())
itemArr.sort(key = lambda each:each,reverse = True)
if itemArr > (M+1)//2:
return ''
N = len(itemArr)
firstGate = (M+1)//2
tempList = *M
firstHas = 0
for first in range(0,N):
charcter = itemArr
count = itemArr
newEnd = firstHas + count
if newEnd > firstGate:
tempList[(2*firstHas):(2*firstGate):2] = charcter*(firstGate-firstHas)
secondHas = newEnd - firstGate
tempList = charcter*secondHas
start = first + 1
break
else:
tempList[(2*firstHas):(2*newEnd):2] = charcter*(newEnd-firstHas)
firstHas = newEnd
for second in range(start,N):
charcter = itemArr
count = itemArr
newEnd = secondHas + count
tempList[(2*secondHas+1):(2*newEnd+1):2] = charcter*(newEnd-secondHas)
secondHas = newEnd
result = ''
for each in tempList:
result += each
return result 本帖最后由 ouyunfu 于 2020-3-31 21:26 编辑
def f365(s:str)->str:
s0=list(s)
s1=set(s)
s2=
m=
L=]
s0.remove(m)
Flag=1
while Flag:
for i in s0:
if i!=L[-1]:
L.append(i)
s0.remove(i)
break
else:Flag=0
if len(L)==len(s):
return ''.join(L)
else:
return '' 本帖最后由 l0stparadise 于 2020-4-1 11:39 编辑
def f365(s):
s_list=*len(s)
num_count={}
for i in s:
num_count=num_count.get(i,0)+1
s_temp_list=[]
num_count_sorted=sorted(num_count.items(),key=lambda x:x,reverse=True)
for key_values in num_count_sorted:
if key_values > (len(s)+1)/2:
return ""
else:
for j in range(key_values):
s_temp_list.append(key_values)
n=0
for i in range(0,len(s),2):
s_list=s_temp_list
n+=1
for i in range(1,len(s),2):
s_list=s_temp_list
n+=1
str1 = ""
for _ in s_list:
str1 += _
return str1 本帖最后由 archlzy 于 2020-3-31 22:38 编辑
def fun365(string):
string_list = ]
res = ]
bool_while = True
while bool_while:
m = len(string_list)
temp = []
for i in string_list:
for j in range(len(res)):
try:
if i != res and i!= res:
res.insert(j+1,i)
break
except IndexError:
if i != res:
res.insert(j+1,i)
break
else:
if i != res:
res.insert(0,i)
else:
temp.append(i)
string_list = temp
if len(string_list) == m:
bool_while = False
if len(string_list):
return ''
else:
return ''.join(res) def f365(string):
new_st = ''
dict_string = dict(zip(list(string),*(len(string))))
for each in string:
dict_string += 1
#若字符串中一个元素出现的最大次数超过一半（奇数加一的一半，偶数的一半）则返回空字符串
if max(dict_string.values()) > ((len(string)+1)//2):
return new_st
#剩余的情况返回字符串
else:
values = list(dict_string.values()).sort() #对每个元素出现的频次进行排序
#对字符串重新排序，依照元素频次高低对元素排列
i = 0
for each in dict_string:
j = dict_string
if j >= i:
while dict_string:
new_st = each + new_st
dict_string -= 1
else:
while dict_string:
new_st = new_st + each
dict_string -= 1
i = j
#将新排列的字符串平分为两部门[前半部分:后半部分]，并将后半部分间隔插入前半部分字符串中
if len(string)%2 == 0:#偶数情况直接平分
st1 = new_st[:((len(string)+1)//2)]
st2 = new_st[((len(string)+1)//2):]
else:#考虑到map函数在此情况下两段字符串数量不一致（前半部分多一个元素）会少输出一组，人为引入一个元素
st1 = new_st[:((len(string)+1)//2)]
st2 = new_st[((len(string)+1)//2):] + 'X'
st_l = list(map(lambda i,j: i+j, st1, st2))
if len(string)%2 == 0:
return ''.join(st_l)#偶数情况直接得到真值
else:
return ''.join(st_l)[:-1]#将引入的元素去除，返回真值
本帖最后由 sjtuszy 于 2020-4-1 14:06 编辑
def fun365(s):
list_sort = sorted(sorted(s), key = lambda x : s.count(x), reverse = True) #按字母的数量从多到少重排
if list_sort.count(list_sort) - 1 > len(s) - list_sort.count(list_sort):#最多的字母中间的“空”若不够其他所有字母来插空，则返回''
return ''
else:
list_1 = list_sort[:list_sort.count(list_sort)] #最多的字母成list_1列，其余所有字母成list_2列
list_2 = list_sort):]
i = 0
for each in list_2:
list_1 += each #list_2中的字母依次从左开始插在list_1的字母后边，插到list_1最后则再一次从左开始
i += 1
return ''.join(list_1) 这个题目对小白好像很不友好{:10_266:} 本帖最后由 hhb1988 于 2020-4-1 14:32 编辑
def fun365(s):
length = len(s)
if length%2:
max_num = length/2 + 1
else:
max_num = length/2
letter = {}
most_num = 0
for i in s:
if i in letter.keys():
letter += 1
else:
letter = 1
if letter > most_num:
most_num = letter
most_letter = i
if most_num > max_num:
return ''
index = 0
new_list = []
for i in range(length):
new_list.append('*')
for i in range(most_num):
new_list = most_letter
index += 2
letter = 0
for i in letter:
while letter>0:
if index > length:
index = 1
new_list = i
index +=2
letter -= 1
new_s = ''
for i in range(len(new_list)):
new_s = new_s + new_list
return str(new_s)
s = str(input("请输入一个字符串:"))
string = fun365(s)
print(string)
from collections import Counter
def f365(s):
num = Counter(s)
if max(num.values()) > (len(s)+1)//2:
return ''
num = sorted(num.items(),key=lambda x:x,reverse=True)
num =
rec = []
l, r = 0, len(num)-1
while l < r:
if num == 0:
l += 1
rec += num
num -= 1
if num == 0:
r -= 1
rec += num
num -= 1
rec = rec[:len(s)]
l, r = 0, len(rec)-1
while rec == rec:
rec, rec = rec, rec
l += 3
r -= 1
return ''.join(rec) def solve(s:str):
su = 0
d = { }
mx = 0
l=[]
string = list(set(s))
string.sort()
for i in string:
count = s.count(i)
if mx < count:
mx = count
word=i
su += count
d = count
# print(mx,su)
if mx > su-mx+1:
return ""
string.remove(word)
for i in string:
l += *d
l += *mx
string=''
for i in range(len(l)//2):
string += l
string+=l
if su%2!=0:
string+=l[-1]
return string import itertools
def func(string):
length = (len(string))
string_list = []
new_string = ''
count = 0
if length > 1:
str_list = itertools.permutations(string, length)
for i in str_list:
for num in range(len(i) - 1):
if i == i:
count = 1
new_string = ''
break
else:
new_string += i
if count != 1:
new_string += i[-1]
if new_string not in string_list:
string_list.append(new_string)
print(new_string)
count = 0
new_string = ''
if string_list == []:
print('""')
elif length == 1:
print(string)
else:
print('""')
str1 = input('请输入一个字符串:')
func(str1) def f(s):
dict1 = {}
for each in s:
if each in dict1.keys():
dict1 += 1
else:
dict1.setdefault(each,1)
max1 = max(dict1.values())
if max1*2-1 > len(s):
return ''
else:
a = 1
while a <len(s):
if s == s:
b = s
s = s[:a]+s
if b != s:
s = b+s
else:
for each in range(2,len(s)):
if b != s and b != s:
s = s[:each]+b+s
if each < a:
a+1
else:
a = a
else:
a += 1
return s
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 = 0
letter_dict += 1
sorted_letter = sorted(letter_dict.items(), key=operator.itemgetter(1), reverse=True)
most_letter_nums = sorted_letter
if most_letter_nums <= ceil(length/2):
transform_list =
i = 0
j = 0
while i < length:
nums = sorted_letter
transform_list = 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 += most_letter_nums
return resorted_str
else:
return ""
页:
[1]
2