ъъ
я бы посмотрел на решение этой задачи за куб )))
Size: a a a
2021 May 23
q
меня интересует теоритическая точка зрения, возможно ли такое реализовать!?
ъъ
линейное время - точно да)
ъъ
чтоб еще и с константной памятью - наверняка нет
q
https://www.geeksforgeeks.org/check-balanced-parentheses-expression-o1-space/
Ну тут я не уверен в корректности, ибо не вдавался в подробности самого решения
Ну тут я не уверен в корректности, ибо не вдавался в подробности самого решения
AT
это как раз проблема регулярок. Нельзя
AT
без стека нельзя, конечно же
q
то есть, все-таки выделение доп. памяти строго зависит от кол-во элементов? Я просто смотрю в сторону структур данных константных размеров, и пробую просто на практике чет провернуть...
q
не самый лучший подход, кнш, просто интересно))
AT
Вы хотите решить эту задачу? Или вы хотите решить эту задачу хитрым необычным способом?
q
а я пока не определился)
AT
решите сначала просто. Складывайте в стек открывающие скобки и при встрече закрывающей вытаскивайте и сравнивайте на соответствие (предварительно проверив на непустоту стека, конечно же)
q
это все классика, и понятно, что без структуры данных, которая зависит от длины строки, данная идея не сработает. Мой вопрос не был связан именно с этим подходом, возможно, существует некоторая другая идея, которая не требует структуры данных, зависящуюся от длины строки...
CD
Нельзя конст память, если не абузить модификацию входных данных
NE
на so видел за n^2
M
Можно или за O(n^2) по времени но O(1) по памяти если 2 и более типов скобок
https://www.geeksforgeeks.org/check-for-balanced-parentheses-in-an-expression-o1-space-on2-time-complexity/?ref=rp
Или за O(n) по времени и O(1) по памяти если всего один тип скобок
https://www.geeksforgeeks.org/check-if-given-parentheses-expression-is-balanced-or-not/?ref=rp
https://www.geeksforgeeks.org/check-for-balanced-parentheses-in-an-expression-o1-space-on2-time-complexity/?ref=rp
Или за O(n) по времени и O(1) по памяти если всего один тип скобок
https://www.geeksforgeeks.org/check-if-given-parentheses-expression-is-balanced-or-not/?ref=rp
NE
👍.
CD
Интересная единица памяти, в которой можно хранить число до N
NE
?