Здравствуйте. Я выполняю следующее упражнение по программированию: Возвращаем строку как отсортированные блоки . Заявление:
Задача
Вы получите строку, состоящую из строчных букв, заглавных букв и цифр в качестве ввода. Ваша задача - вернуть эту строку в виде блоков, разделенных тире ("-"). Элементы блока должны быть отсортированы по иерархии, указанной ниже, и каждый блок не может содержать несколько экземпляров одного и того же символа.
Иерархия:
lowercase letters (a - z), in alphabetic order
uppercase letters (A - Z), in alphabetic order
digits (0 - 9), in ascending order
Примеры
"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
Удачи!
Я написал следующий код:
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 l oop предложение: initialIterationLength = len(sorted) и внутри l oop, в условии if:
if initialIterationLength == len(sorted):
sorted = []
Это действительно работает для теста обсуждается, однако для больших вводов это не сработает.
Например, когда input:
ZrXx2VpVJMgPs54SwwxSophZEWvwKUxzqNxaxlgY0T
Наш результат:
aghlopqrsvwxzEJKMNPSTUVWXYZ0245-gpwxSVZ-wx
Ожидается:
aghlopqrsvwxzEJKMNPSTUVWXYZ0245-gpwxSVZ-wx-x-x
Я думаю, что должен быть лучший алгоритм.
I прочитал:
Как можно отсортировать неповторяющиеся и затем повторяющиеся символы characters