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

from collections import Counter
def fun365(s):
    length = len(s)
    c= Counter(s)
    lst = sorted(c.items(),key=lambda item: item[1],reverse=True)
    lenc = lst[0][1]
    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[0][0]+lst[1][0]+lst[0][0]
    elif  lenc < length-1:
        tmp = list(s)
        res = lst[0][0]
        tmp.remove(res)
        for i in range(length-1):
            for j in range(length-i-1):
                if res[-1] != tmp[j]:
                    break               
            res += tmp.pop(j)
        return res
    else:
        return ""

永恒的蓝色梦想

占楼

March2615

我就说怎么就少了两天的题，原来是没有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[n - 1] == sort_list[-1]:  # 条件1
        return ''
    result = sort_list[:]  # 创建一个一样长的列表保存答案
    left, right = sort_list[:n], sort_list[n:]  # len(left) <= len(right)
    for i in range(len(left)):
        result[2 * i + 1] = left[i]
    for i in range(len(right)):
        result[2 * i] = right[i]
    return ''.join(result)

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

TJBEST

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

def fun365(s):
    #复杂度O(n)
    M = len(s)
    dic = {}
    for each in s:
        try:
            dic[each] += 1
        except Exception:
            dic[each] = 1
    itemArr = list(dic.items())
    itemArr.sort(key = lambda each:each[1],reverse = True)
    if itemArr[0][1] > (M+1)//2:
        return ''
    N = len(itemArr)
    firstGate = (M+1)//2
    tempList = [0]*M
    firstHas = 0
    for first in range(0,N):
        charcter = itemArr[first][0]
        count = itemArr[first][1]
        newEnd = firstHas + count
        if newEnd > firstGate:
            tempList[(2*firstHas):(2*firstGate):2] = charcter*(firstGate-firstHas)
            secondHas = newEnd - firstGate
            tempList[1:(2*secondHas+1):2] = 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[second][0]
        count = itemArr[second][1]
        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

def f365(s:str)->str:
    s0=list(s)
    s1=set(s)
    s2=[s.count(i) for i in s1]
    m=[i for i in s1 if s.count(i)==max(s2)]
    L=[m[0]]
    s0.remove(m[0])
    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

def f365(s):
    s_list=[0]*len(s)
    num_count={}
    for i in s:
        num_count[i]=num_count.get(i,0)+1
    s_temp_list=[]
    num_count_sorted=sorted(num_count.items(),key=lambda x:x[1],reverse=True)
    for key_values in num_count_sorted:
        if key_values[1] > (len(s)+1)/2:
            return ""
        else:
            for j in range(key_values[1]):
                s_temp_list.append(key_values[0])
    n=0
    for i in range(0,len(s),2):
        s_list[i]=s_temp_list[n]
        n+=1
    for i in range(1,len(s),2):
        s_list[i]=s_temp_list[n]
        n+=1
    str1 = ""
    for _ in s_list:
        str1 += _
    return str1

archlzy

def fun365(string):
    string_list = [i for i in string[1:]]
    res = [string[0]]
    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[j] and i!= res[j+1]:
                        res.insert(j+1,i)
                        break
                except IndexError:
                    if i != res[j]:
                        res.insert(j+1,i)
                        break
            else:
                if i != res[0]:
                    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)

sYMMetrY

def f365(string):
    new_st = ''
    dict_string = dict(zip(list(string),[0]*(len(string))))
    for each in string:
        dict_string[each] += 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[each]
            if j >= i:
                while dict_string[each]:                        
                    new_st = each + new_st
                    dict_string[each] -= 1

            else:
                while dict_string[each]:                        
                    new_st = new_st + each
                    dict_string[each] -= 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

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

尤思帆

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

hhb1988

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[i] += 1
        else:
            letter[i] = 1
            
        if letter[i] > most_num:
            most_num = letter[i]
            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[index] = most_letter
        index += 2
    
    letter[most_letter] = 0    
    for i in letter:
        while letter[i]>0:
            if index > length:
                index = 1
            
            new_list[index] = i
            index +=2
            letter[i] -= 1
    
    new_s = ''
    for i in range(len(new_list)):
        new_s = new_s + new_list[i]
        
    return str(new_s)


s = str(input("请输入一个字符串:"))
string = fun365(s)
print(string)

kinkon

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[1],reverse=True)    
    num = [list(n) for n in num]
    rec = []
    l, r = 0, len(num)-1
    while l < r:
        if num[l][1] == 0:
            l += 1    
        rec += num[l][0]
        num[l][1] -= 1
        if num[r][1] == 0:
            r -= 1        
        rec += num[r][0]
        num[r][1] -= 1
    rec = rec[:len(s)]
    l, r = 0, len(rec)-1
    while rec[r] == rec[r-1]:        
        rec[l], rec[r-1] = rec[r-1], rec[l]
        l += 3
        r -= 1
    return ''.join(rec)

NAMELESSONE

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[i] = count
       # print(mx,su)
    if mx > su-mx+1:
        return ""
    string.remove(word)
    for i in string:
        l += [i]*d[i]
    l += [word]*mx
    string=''
    for i in range(len(l)//2):
        string += l[len(l)//2+i]
        string+=l[i]
    if su%2!=0:
        string+=l[-1]
    return string

raimond

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[num] == i[num + 1]:
                    count = 1
                    new_string = ''
                    break
                else:
                    new_string += i[num]
            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[each] += 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[a] == s[a-1]:
                b = s[a]
                s = s[:a]+s[a+1:]
                if b != s[0]:
                    s = b+s
                else:
                    for each in range(2,len(s)):
                        if b != s[each] and b != s[each-1]:
                            s = s[:each]+b+s[each:]
                            if each < a:
                                a+1
                            else:
                                a = a
            else:
                a += 1
        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 ""