Size: a a a

JavaScript — русскоговорящее сообщество

2020 September 16

mm

mhmd mlh in JavaScript — русскоговорящее сообщество
Как из этого алгоритма сделать О(n)?

for (let i = 0; i < s.length(); i++) {
   current = s.indexOf(s.charAt(i));
   for (let j = i; j < s.length(); j++) {
       if (s.charAt(current) == s.charAt(j)) {
           count++;
       }
   }
}
источник

E

Evgen in JavaScript — русскоговорящее сообщество
mhmd mlh
Как из этого алгоритма сделать О(n)?

for (let i = 0; i < s.length(); i++) {
   current = s.indexOf(s.charAt(i));
   for (let j = i; j < s.length(); j++) {
       if (s.charAt(current) == s.charAt(j)) {
           count++;
       }
   }
}
Описание задачи хреновое, а ответ - убрать один цикл
источник

mm

mhmd mlh in JavaScript — русскоговорящее сообщество
Evgen
Описание задачи хреновое, а ответ - убрать один цикл
Надо посчитать все подстроки у которых первая и последняя буква одинаковые например у строки "ababca"  их количество 10.

a
b
a
b
c
a
aba
ababca
bab
abca
источник

AP

Anton Permyakov in JavaScript — русскоговорящее сообщество
mhmd mlh
Надо посчитать все подстроки у которых первая и последняя буква одинаковые например у строки "ababca"  их количество 10.

a
b
a
b
c
a
aba
ababca
bab
abca
ты уверен, что это за линию решается?
источник

mm

mhmd mlh in JavaScript — русскоговорящее сообщество
Anton Permyakov
ты уверен, что это за линию решается?
Да, уверен
источник

AP

Anton Permyakov in JavaScript — русскоговорящее сообщество
мб через 2 указателя можно
источник

AP

Anton Permyakov in JavaScript — русскоговорящее сообщество
т.е. хранишь 2 индекса: один начало подстроки, второй конец
источник

AP

Anton Permyakov in JavaScript — русскоговорящее сообщество
изначально расставляешь их по краям и считаешь, пока они в середине не встретятся
источник

mm

mhmd mlh in JavaScript — русскоговорящее сообщество
Пробовал и так не получилось, может быть я не правильно делал
источник

A

Aleksandr in JavaScript — русскоговорящее сообщество
mhmd mlh
Пробовал и так не получилось, может быть я не правильно делал
а ты в конце длинну строки добавлял?
источник

mm

mhmd mlh in JavaScript — русскоговорящее сообщество
Aleksandr
а ты в конце длинну строки добавлял?
Если поставить индексы по краям цыкл же не пройдёт по всем буквам разве нет?
источник

A

AntiPlayer in JavaScript — русскоговорящее сообщество
Да зчем циклом по буквам ходить не пойму?
источник

A

AntiPlayer in JavaScript — русскоговорящее сообщество
у тебя есть str[0] и str[str.length-1] — первая и последняя буквы
источник

mm

mhmd mlh in JavaScript — русскоговорящее сообщество
AntiPlayer
Да зчем циклом по буквам ходить не пойму?
Функция получает строку и надо посчитать сколько подстрок у которых первая и последняя буква
источник

EY

Eugene Yemelin in JavaScript — русскоговорящее сообщество
по памяти есть ограничения?
источник

A

Aleksandr in JavaScript — русскоговорящее сообщество
я чет сомневаюсь, что в O(n) это возможно вообще
источник

mm

mhmd mlh in JavaScript — русскоговорящее сообщество
Eugene Yemelin
по памяти есть ограничения?
Есть, самая длинная строка  10^5
источник

A

Aleksandr in JavaScript — русскоговорящее сообщество
mhmd mlh
Есть, самая длинная строка  10^5
источник

A

Aleksandr in JavaScript — русскоговорящее сообщество
вот тут варианты расписаны
источник

mm

mhmd mlh in JavaScript — русскоговорящее сообщество
Хорошо, спасибо прочитаю
источник