В рейтинге участвует:

групп:

каналов:

Виртуальный сервер на SSD - недорого!

Аренда выделенных и виртуальных серверов (VDS/VPS), хостинг, аренда IP-адресов, администрирование, круглосуточная поддержка

qwarta.ru подробнее

Резервное копирование с проверкой на вирусы!!!

Удобный сервис создания резервных копий на любой сервер сети интернет. Отслеживайте изменения, проверяйте на вирусы. Надежно защитите свой бизнес!

go.backupland.com

Выбираете сервер? Любая конфигурация на заказ!

Аренда физических серверов любых конфигураций под любые запросы - 1С бухгалтерия, игровые сервера, нагруженные проекты, интернет-магазины!

qwarta.ru подробнее

Size: a a a

pro.algorithms

1758 membersпожаловаться на группу
2020 August 19

Н

Новичок in pro.algorithms
Dmitry Baynak
сортировки на сравнениях не работают быстрее n log n, timsort - n log n в worst case
так что в "любых случаях" не обогнать
нет, в любых, я имел ввиду сортировку не под все случаи, а в каких конкретно случаях можно обогнать и чем. Если на интах, то каунтинг сорт — норм. А если только под строки, допустим?
источник
13:58пожаловаться#1

DB

Dmitry Baynak in pro.algorithms
Новичок
нет, в любых, я имел ввиду сортировку не под все случаи, а в каких конкретно случаях можно обогнать и чем. Если на интах, то каунтинг сорт — норм. А если только под строки, допустим?
bucket sort, radix sort
источник
14:03пожаловаться#2

DB

Dmitry Baynak in pro.algorithms
https://en.wikipedia.org/wiki/Sorting_algorithm#Non-comparison_sorts
источник
14:03пожаловаться#3

Н

Новичок in pro.algorithms
спасибо
источник
14:14пожаловаться#4

N

Nikolay in pro.algorithms
Есть строка. Из нее можно удалить только 1 символ. Из любого места . Надо узнать можно ли таким удалением из нее сделать палиндром. Можно решит не квадратичной временной сложностью ?
источник
18:13пожаловаться#5

🗿

🗿🗿🗿 Ilushkins 🗿🗿🗿... in pro.algorithms
Nikolay
Есть строка. Из нее можно удалить только 1 символ. Из любого места . Надо узнать можно ли таким удалением из нее сделать палиндром. Можно решит не квадратичной временной сложностью ?
Палиндром это типа ABCCBA?
источник
18:14пожаловаться#6

C

Cotangent in pro.algorithms
🗿🗿🗿 Ilushkins 🗿🗿🗿
Палиндром это типа ABCCBA?
да
источник
18:14пожаловаться#7

C

Cotangent in pro.algorithms
ABCBA тож
источник
18:15пожаловаться#8

N

Nikolay in pro.algorithms
Cotangent
да
Как?
источник
18:16пожаловаться#9

N

Nikolay in pro.algorithms
🗿🗿🗿 Ilushkins 🗿🗿🗿
Палиндром это типа ABCCBA?
Да
источник
18:16пожаловаться#10

A

Andrey Borzenkov in pro.algorithms
у тебя центр палиндрома будет в +-1 позиции от текущего
источник
18:16пожаловаться#11

N

Nikolay in pro.algorithms
Andrey Borzenkov
у тебя центр палиндрома будет в +-1 позиции от текущего
Если пришла строка на вход , то как использовать это знание +-1?
источник
18:19пожаловаться#12

EZ

Evgenii Zheltonozhsk... in pro.algorithms
Nikolay
Если пришла строка на вход , то как использовать это знание +-1?
Начинаешь с каждого из потенциальных центров, если да символа не равны, пробуешь удалить каждый из них
источник
18:22пожаловаться#13

D

Daniil in pro.algorithms
Делаешь обычную проверку палиндрома, когда у тебя символы не равны, у тебя появляется два варианта для удаления, рассмотри их
источник
18:22пожаловаться#14

A

Andrey Borzenkov in pro.algorithms
допустим у неё длина N, проверим что она палиндром, если да, то вернём её
если нет, то после удаления её длина станет равна N - 1
тут нужно рассмотреть случай для четного и нечётного, но они идентичны почти
если (N - 1) нечётно, то нужно попытаться жадно набрать из центра палиндром для [N / 2 - 1, N / 2, N / 2 + 1]
источник
18:22пожаловаться#15

C

Cotangent in pro.algorithms
Nikolay
Есть строка. Из нее можно удалить только 1 символ. Из любого места . Надо узнать можно ли таким удалением из нее сделать палиндром. Можно решит не квадратичной временной сложностью ?
есть ссылка на задачу? типа попытатся сдать её
источник
18:40пожаловаться#16

K

Kotomord_λapki in pro.algorithms
Nikolay
Есть строка. Из нее можно удалить только 1 символ. Из любого места . Надо узнать можно ли таким удалением из нее сделать палиндром. Можно решит не квадратичной временной сложностью ?
ну очевидно, что линейная сложность.
Крайние символы не совпадают - проверить две подстроки на палиндромность, иначе перейти к подстроке без первого и последнего символа
источник
18:49пожаловаться#17

CD

Constantine Drozdov in pro.algorithms
Kotomord_λapki
ну очевидно, что линейная сложность.
Крайние символы не совпадают - проверить две подстроки на палиндромность, иначе перейти к подстроке без первого и последнего символа
осталось проверить палиндромность за 1)
источник
20:14пожаловаться#18

K

Kotomord_λapki in pro.algorithms
Constantine Drozdov
осталось проверить палиндромность за 1)
Почему? Переход на палиндромность ровно1 раз
источник
20:14пожаловаться#19

CD

Constantine Drozdov in pro.algorithms
Kotomord_λapki
Почему? Переход на палиндромность ровно1 раз
а в подстроке?
источник
20:14пожаловаться#20