|
1505 / 969 / 812
Регистрация: 30.04.2016
Сообщений: 3,337
|
||||||
Вывести все правильные скобочные выражения длины N, состоящие из круглых и квадратных скобок26.06.2017, 19:22. Показов 2973. Ответов 11
Метки нет (Все метки)
Здравствуйте! Решил данную задачу, но один тест не проходит по времени...Можно ли как-то оптимизировать данный код?
Мое решение:
0
|
||||||
| 26.06.2017, 19:22 | |
|
Ответы с готовыми решениями:
11
Вывести все правильные скобочные выражения длиной N, состоящие из круглых и квадратных скобок Вывести все правильные скобочные выражения (оптимизировать алгоритм, ускорить работу кода)
|
|
7804 / 6568 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
|
|
| 26.06.2017, 19:52 | |
|
str и b передавай по ссылке.
1
|
|
|
1505 / 969 / 812
Регистрация: 30.04.2016
Сообщений: 3,337
|
|
| 26.06.2017, 20:24 [ТС] | |
|
nmcf, спасибо за ваш ответ. Стало немного быстрее, но последний тест все равно валится по времени
![]() Добавлено через 10 минут Здесь либо оптимизация при выводе нужна (но вроде использую printf()), либо рекурсивную функцию перебора убирать нужно. Хотя здесь размещения с повторениями и все вроде правильно, перебирает все варианты с повторами...Лимит времени 2 секунды, а последний тест занимает три и не знаю, что делать теперь...
0
|
|
|
7804 / 6568 / 2988
Регистрация: 14.04.2014
Сообщений: 28,705
|
|
| 26.06.2017, 21:17 | |
|
0
|
|
|
1505 / 969 / 812
Регистрация: 30.04.2016
Сообщений: 3,337
|
|
| 26.06.2017, 21:26 [ТС] | |
|
Ромаха, здравствуйте! Вот как раз next_permutation() здесь не подходит, так как размещения с повторениями нужны, поэтому и использую рекурсивную функцию. А вообще, встроенные функции работают довольно быстро
Похожую задачу сдал с помощью next_permutation(), а что с этой делать - не знаю.
0
|
|
|
Диссидент
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
|
|
| 26.06.2017, 22:30 | |
|
В строках 42-45 ты перебираешь ВСЕ варианты. В итоге их у тебя выходит 4N. Но очевидно, что за "(" не может следовать "]", за "[" - ")". Если ты будешь пропускать такие комбинации, то как раз эту секунду и сбросишь
Добавлено через 8 минут Fixer_84, это не предел оптимизаций. Когда получено больше половины строки, можно подсчитать количество открытые - закрытые. И если оно больше числа оставшихся символов, то на фига строку генерить дальше? Все равно все скобки не закроются. Вообще, очень полезно вместе с каждой строкой держать счетчики скобок. Ведь если у тебя N = 40, а строка начинается с "())", дальше с этим огрызком можно не работать, все равно строка будет не сбалансирована.. Все это вместе и называется, кажется, "метод ветвей и границ"
1
|
|
| 27.06.2017, 13:09 | ||||||
2
|
||||||
|
279 / 39 / 13
Регистрация: 11.10.2015
Сообщений: 405
|
|
| 27.06.2017, 14:15 | |
|
Fixer_84, стринги по значению передавать это хардкор дичайший
1
|
|
|
Форумчанин
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
|
||
| 27.06.2017, 14:22 | ||
|
Кстати, в некоторых случая компилятор может это дело заменить мув семантикой (если увидит что дальше строка не используется). Но лучше конечно использовать lvalue ссылку на const.
1
|
||
|
Диссидент
27714 / 17332 / 3810
Регистрация: 24.12.2010
Сообщений: 38,978
|
|||
| 27.06.2017, 23:19 | |||
|
Имхо, главное - алгоритм. Но, конечно, и средства языка следует использовать грамотно. ЗЫ. А алгоритм у ТС и впрямь лобовой и ломовой.
1
|
|||
| 27.06.2017, 23:19 | |
|
Помогаю со студенческими работами здесь
12
Проверить правильность расстановки круглых и квадратных скобок в выражениях
Проверить правильность расстановки круглых и квадратных скобок в выражениях
Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
||||
|
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта
Симптом:
После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
|
Access
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
|
Новый ноутбук
volvo 07.12.2025
Всем привет.
По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне:
Ryzen 5 7533HS
64 Gb DDR5
1Tb NVMe
16" Full HD Display
Win11 Pro
|
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
|
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
|
|
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов
На странице:
https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/
нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
|
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов.
. . .
|
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
|
Мысли в слух
kumehtar 18.11.2025
Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .
|
Создание Single Page Application на фреймах
krapotkin 16.11.2025
Статья исключительно для начинающих. Подходы оригинальностью не блещут.
В век Веб все очень привыкли к дизайну Single-Page-Application .
Быстренько разберем подход "на фреймах".
Мы делаем одну. . .
|