python - 对不重复的字符进行排序，然后对重复的字符进行排序？

Question

我正在做以下编程练习:Return String As Sorted Blocks 。声明如下:

Task

You will receive a string consisting of lowercase letters, uppercaseletters and digits as input. Your task is to return this string asblocks separated by dashes ("-"). The elements of a block should besorted with respect to the hierarchy listed below, and each blockcannot contain multiple instances of the same character.

The hierarchy is:

lowercase letters (a - z), in alphabetic order
uppercase letters (A - Z), in alphabetic order
digits (0 - 9), in ascending order

Examples

"21AxBz" -> "xzAB12" - since input does not contain repeating characters, you only need 1 block
"abacad" -> "abcd-a-a" - character "a" repeats 3 times, thus 3 blocks are needed
"" -> "" - an empty input should result in an empty output

Good luck!

我编写了以下代码:

def blocks(s):
    print("s: "+s)
    lowers = []
    uppers = []
    digits = []
    for c in s:
        if c.islower():
            lowers.append(c)
        if c.isupper():
            uppers.append(c)
        if c.isdigit():
            digits.append(c)
    lowers.sort()
    uppers.sort()
    digits.sort()
    print("lowers: ")
    print(lowers)
    print("uppers: ")
    print(uppers)
    print("digits: ")
    print(digits)
    result = ""
    sorted = lowers+uppers+digits
    removedLetters = 0
    needsNextBlock = False
    nextBlock = "-"
    while len(sorted) > 0:
        for i, c in enumerate(sorted):
            print(i, c)
            print("result: ")
            print(result)
            if c not in result:
                result += c
                print("we want to delete: ")
                print(c)
                sorted = sorted[0:i-removedLetters] + sorted[i+1-removedLetters:]
                removedLetters += 1
                print("new sorted: ")
                print(sorted)
            else:
                if c not in nextBlock:
                    needsNextBlock = True
                    nextBlock += c
                    sorted = sorted[0:i-removedLetters] + sorted[i+1-removedLetters:]
                    removedLetters += 1

                    print("new sorted: ")
                    print(sorted)

        if needsNextBlock:
            result += nextBlock
        needsNextBlock = False
        nextBlock = "-"
    return result

并且存在一个错误，因为我们进行以下测试时:

Test.assert_equals(blocks("abacad"), "abcd-a-a")

跟踪是:

s: abacad
lowers: 
['a', 'a', 'a', 'b', 'c', 'd']
uppers: 
[]
digits: 
[]
0 a
result: 

we want to delete: 
a
new sorted: 
['a', 'a', 'b', 'c', 'd']
1 a
result: 
a
new sorted: 
['a', 'b', 'c', 'd']
2 a
result: 
a
3 b
result: 
a
we want to delete: 
b
new sorted: 
['a', 'c', 'd']
4 c
result: 
ab
we want to delete: 
c
new sorted: 
['a', 'd']
5 d
result: 
abc
we want to delete: 
d
new sorted: 
['a']
0 a
result: 
abcd-a
new sorted: 
['a']
0 a
result: 
abcd-a-a
new sorted: 
['a']
0 a
result: 
abcd-a-a-a
new sorted: 
['a']
0 a
result: 
abcd-a-a-a-a
new sorted: 
['a']
0 a
(infinite loop)

正如我们所见，执行时会产生困难:

sorted = sorted[0:i-removedLetters] + sorted[i+1-removedLetters:]
removedLetters += 1

因为我们之前已经传递了重复的字母，在本例中是“a”，但我们没有计算它，所以新排序的子字符串的演算保持不变。

我尝试了一种幼稚的方法:

def blocks(s):
    print("\n\n\ns: "+s)
    lowers = []
    uppers = []
    digits = []
    for c in s:
        if c.islower():
            lowers.append(c)
        if c.isupper():
            uppers.append(c)
        if c.isdigit():
            digits.append(c)
    lowers.sort()
    uppers.sort()
    digits.sort()
    print("lowers: ")
    print(lowers)
    print("uppers: ")
    print(uppers)
    print("digits: ")
    print(digits)
    result = ""
    sorted = lowers+uppers+digits
    removedLetters = 0
    needsNextBlock = False
    nextBlock = "-"
    while len(sorted) > 0:
        initialIterationLength = len(sorted)
        for i, c in enumerate(sorted):
            print(i, c)
            print("result: ")
            print(result)
            if c not in result:
                result += c
                print("we want to delete: ")
                print(c)
                sorted = sorted[0:i-removedLetters] + sorted[i+1-removedLetters:]
                removedLetters += 1
                print("new sorted: ")
                print(sorted)
            else:
                if c not in nextBlock:
                    needsNextBlock = True
                    nextBlock += c
                    sorted = sorted[0:i-removedLetters] + sorted[i+1-removedLetters:]
                    removedLetters += 1
                    if initialIterationLength == len(sorted):
                        sorted = []
                    print("new sorted: ")
                    print(sorted)

        if needsNextBlock:
            result += nextBlock
        needsNextBlock = False
        nextBlock = "-"
    return result

如您所见，当我们启动 while 循环时，我添加了这句话: initialIterationLength = len(sorted) 并在循环内部的 if 条件中添加了以下句子:

if initialIterationLength == len(sorted):
    sorted = []

它确实适用于正在讨论的测试，但对于较大的输入，它不起作用。

例如，当输入为:

ZrXx2VpVJMgPs54SwwxSophZEWvwKUxzqNxaxlgY0T

我们的结果是:

aghlopqrsvwxzEJKMNPSTUVWXYZ0245-gpwxSVZ-wx

预期是:

aghlopqrsvwxzEJKMNPSTUVWXYZ0245-gpwxSVZ-wx-x-x

我认为应该有更好的算法。

我已阅读:

• How do I get a substring of a string in Python?
• Does Python have a string 'contains' substring method?
• Accessing the index in 'for' loops?
• How do I concatenate two lists in Python?
• How can I check if a string represents an int, without using try/except?
• Check if string is upper, lower, or mixed case in Python
• Iterating each character in a string using Python
• How to detect lowercase letters in Python?

我们如何对不重复的字符进行排序，然后对重复的字符进行排序？

Answer 1

您可以使用计数器根据重复的数字来跟踪您需要的迭代。

import string
from collections import Counter

ORDER = {s:i for i, s in enumerate(string.ascii_letters + string.digits)}

def my_sorted(s):

    c = Counter(s)
    res = []
    it = 1

    to_sort = set(c)
    while len(to_sort) > 0:
        res.append(sorted(to_sort ,key=lambda x:ORDER[x]))
        to_sort = [k for k in c if c[k] > it]
        it+=1

    return "-".join(["".join(l) for l in res])

示例:

>>> s="ZrXx2VpVJMgPs54SwwxSophZEWvwKUxzqNxaxlgY0T"
>>> my_sorted(s)
aghlopqrsvwxzEJKMNPSTUVWXYZ0245-gpwxSVZ-gpwxSVZ-wx-x-x