Как создать наибольшее число из массива цифр, содержащего не более «k» последовательных одинаковых цифр? ⇐ Python

[Anonymous]

У меня есть массив целых чисел от 0 до 9, и мне нужно создать максимально возможное число путем объединения этих цифр. Однако есть ограничение: я не могу иметь более 𝑘 последовательных одинаковых цифр в (десятичном представлении) результирующего целого числа. В идеале эта проблема должна быть решена с временной сложностью O(n).
Ограничения и требования:

• Без использования дополнительных библиотек
• Входной массив состоит только из значений в {0,1,2,3,4,5,6,7,8,9
• Выходные данные должны представлять собой максимально возможное целое число, образованное путем объединения цифр массива в десятичное представление.
• В (десятичном представлении массива) должно присутствовать не более 𝑘 последовательных одинаковых цифр. the) выход.
• Можно предположить, что существует решение для каждого заданного входа. Например, [1,1,1,1,1] k=2 никогда не будет передано в качестве входных данных.

Код: Выделить всё

test_cases = [
# Format: (k, [array_of_integers], "expected_result")
(3, [0, 1, 1, 1, 1, 2, 3, 4, 4, 4, 4, 4, 6, 6, 6, 6, 6, 9, 9, 9, 9, 9], "999699666464443431110"),
(1, [1, 2, 3, 4, 5], "54321"),
(2, [1, 1, 2, 2, 3, 3], "332211"),
(2, [9, 9, 8, 8, 7, 7], "998877"),
(3, [5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3], "555444333555444333"),
(2, [2, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0], "221100221100"),
(3, [9, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 8], "999888999888"),
(1, [9, 8, 7, 6, 5], "98765"),
(3, [1, 1, 1, 1, 1, 1], "111111"),
(2, [4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1], "443322114321"),
(2, [9, 9, 8, 8, 7, 7, 6, 6], "99887766"),
(3, [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], "222111000222111000"),
(2, [5, 5, 5, 4, 4, 4, 3, 3, 3], "554433554433"),
(1, [1, 2, 3, 4, 5, 6], "654321"),
(3, [6, 6, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4], "666555444666555444"),
(2, [9, 8, 7, 6, 5, 4], "998877665544"),
(3, [3, 3, 3, 2, 2, 2, 1, 1, 1], "333222111"),
(2, [4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2], "443322443322"),
(3, [9, 9, 9, 8, 8, 8, 7, 7, 7, 6, 6, 6, 5, 5, 5], "999888777666555"),
(2, [0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5], "554433221100"),
(2, [9, 9, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7], "998877998877"),
(1, [2, 2, 1, 1, 0, 0], "210210"),
(2, [3, 3, 3, 2, 2, 2, 1, 1, 1], "332211321"),
(2, [5, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1], "55443322154321")
]

Это моя попытка:

Код: Выделить всё

def largestNumberWithoutKConsecutive(arr: list, k: int) -> str:

# Step 1: Count frequencies
freq = {}
for num in arr:
if num in freq:
freq[num] += 1
else:
freq[num] = 1

# Step 2: Sort the digits in descending order
digits = sorted(freq.keys(), reverse=True)

result = []
last_digit = None
last_count = 0

# Step 3: Build the result
while any(freq[d] > 0 for d in digits):
placed = False
# Try to place the largest available digit first
for digit in digits:
if freq[digit] == 0:
continue  # Skip if this digit is already used up
if digit == last_digit and last_count == k:
continue  # Skip if placing this digit violates the k constraint

# Determine how many times we can place this digit
use_count = min(freq[digit], k if digit != last_digit else k - last_count)
result.extend([digit] * use_count)
freq[digit] -= use_count

# Update the last_digit and last_count
if digit == last_digit:
last_count += use_count
else:
last_digit = digit
last_count = use_count

placed = True
break  # After placing, try the largest digit again

if not placed:
# Step 4: Break the sequence with the next highest different digit
for digit in digits:
if freq[digit] > 0 and digit != last_digit:
result.append(digit)
freq[digit] -= 1
last_digit = digit
last_count = 1
placed = True
break
# If no placement is possible, break out
if not placed:
break

# Convert result list to a string
result_str = ''.join(map(str, result))
return result_str

Это результат, который он генерирует для данных тестовых случаев:

Код: Выделить всё

>>> Test Case 1: **Fail**
Input: k: 3, n: [0, 1, 1, 1, 1, 2, 3, 4, 4, 4, 4, 4, 6, 6, 6, 6, 6, 9, 9, 9, 9, 9]
Output: 9996669966444344211101
Expected: 999699666464443431110

>>> Test Case 2: **Pass**
Input: k: 1, n: [1, 2, 3, 4, 5]
Output: 54321
Expected: 54321

>>>  Test Case 3: **Pass**
Input: k: 2, n: [1, 1, 2, 2, 3, 3]
Output: 332211
Expected: 332211

>>> Test Case 4: **Pass**
Input: k: 2, n: [9, 9, 8, 8, 7, 7]
Output: 998877
Expected: 998877

>>> Test Case 5: **Fail**
Input: k: 3, n: [5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3]
Output: 55544454333
Expected: 555444333555444333

>>> Test Case 6: **Fail**
Input: k: 2, n: [2, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0]
Output: 2211221100
Expected: 221100221100

>>> Test Case 7: **Pass**
Input: k: 3, n: [9, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 8]
Output: 999888999888
Expected: 999888999888

>>> Test Case 8: **Pass**
Input: k: 1, n: [9, 8, 7, 6, 5]
Output: 98765
Expected: 98765

>>> Test Case 9: **Fail**
Input: k: 3, n: [1, 1, 1, 1, 1, 1]
Output: 111
Expected: 111111

>>> Test Case 10: **Fail**
Input: k: 2, n: [4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1]
Output: 443343221121
Expected: 443322114321

Как видите, есть несколько тестовых примеров, для которых моя программа выдает неверный результат. Как это можно решить?


Подробнее здесь: https://stackoverflow.com/questions/789 ... e-than-k-c