|
4 / 4 / 0
Регистрация: 26.06.2016
Сообщений: 115
|
|
Сравнить буквы одного слова с другом слове08.05.2018, 23:01. Показов 8055. Ответов 29
Метки нет (Все метки)
Здравствуйте,есть такая задача. Надо сравнить буквы одного слова в другом слове и вывести true если они равны. Т.е. например есть слово
- опт и слово - пот По сути они разные слова,но буквами они совпадают, т.е. выведется true. Но проблема в том что решение в лоб не подходит, сделать 2 цикла и перебирать просто все символы, т.к. сложность такого метода будет O(n2) а надо или O(n) или O(logn*n). Тема на которой мне задали этот вопрос была по коллекция, пот я бьюсь и все никак не могу решить. Прошу кто может то помогите,заранее спасибо.
1
|
|
| 08.05.2018, 23:01 | |
|
Ответы с готовыми решениями:
29
Вычеркните из одного слова все буквы, встречающиеся в другом слове.
|
|
4 / 4 / 0
Регистрация: 26.06.2016
Сообщений: 115
|
||||||
| 09.05.2018, 21:54 [ТС] | ||||||
|
Как подсказали в этом чате ,я сделал код удовлетворяющий моим требованиям. Спасибо всем большое, не знаю примут ли его, т.к. он не основан на коллекциях но сложности требуемой он удовлетворяет.
0
|
||||||
|
3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
|
|
| 09.05.2018, 21:59 | |
|
Очевидно твой код может давать ложные срабатывания, например для аг и бв.
0
|
|
|
4 / 4 / 0
Регистрация: 26.06.2016
Сообщений: 115
|
||||||||||||||||
| 09.05.2018, 22:32 [ТС] | ||||||||||||||||
|
Понял ошибку ,спасибо.
Пытался делать через hashMap но застрял и не знаю каким образом не попасть на сложность опять n2, потому что опять придется перебирать с циклом в цикле
0
|
||||||||||||||||
|
3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
|
|
| 09.05.2018, 23:13 | |
|
letterCounter содержит счётчики для каждой буквы алфавита, так ячейка с индексом 0 соответствует букве а, 1 - b, 2 - c и т.д.
Таким образом берем из строки букву, индекс счётчика в массиве равен буква -'а', просто увеличиваем значение по этому индексу, переходим к следующей букве в слове. Если хочешь с хэшмэпом делать, то ключами будут буквы, а значениями количество этой буквы в слове. Но с массивом мне кажется проще.
0
|
|
|
4 / 4 / 0
Регистрация: 26.06.2016
Сообщений: 115
|
||||||
| 10.05.2018, 10:40 [ТС] | ||||||
|
xoraxax, я немного не понял каким образом мне потом без еще одного цикла пройтись по массиву конечному и сравнить значения что в нем лежат.
Я реализовал таким образом Но я не уверен что сложность подойдет т.к. у меня 2 цикла но не вложенных, в таком случfе будет ли сложность равнятся O(n)?
0
|
||||||
|
3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
|
||
| 10.05.2018, 10:52 | ||
|
т.е. O(100500n) == O(n) Добавлено через 4 минуты по коду, можно всю хрень засунуть в один цикл вроде, кроме того посмотри всякие computeIfAbsent Ну и опять же, я бы не стал городить мапу в этом случае, т.к. не приносит никакого выигрыша, кроме большего расхода памяти (что по большому счету тоже не существенно) Перед тем, как обрабатывать строки, надо из н их убрать все лишние символы и привести в lowerCase, иначе получишь странный результат.
0
|
||
|
502 / 348 / 134
Регистрация: 14.06.2016
Сообщений: 669
|
|
| 10.05.2018, 11:43 | |
|
А будет ли больший расход? Для общего варианта, где, например, есть и кириллица, массив придется делать пошире.
0
|
|
|
3639 / 2971 / 918
Регистрация: 05.07.2013
Сообщений: 14,220
|
||
| 10.05.2018, 12:11 | ||
|
Судя по всему пустая мапа будет занимать порядка 500 байт. Массив из 100 интов будет занимать где-то около 500-600 байт, учитывая оверхед, Добавлено через 38 секунд но опять же, не существенно абсолютно
0
|
||
|
4 / 4 / 0
Регистрация: 26.06.2016
Сообщений: 115
|
|
| 10.05.2018, 21:44 [ТС] | |
|
Спасибо всем большое за помощь, даже не смотря на то что иногда по вашему мнению я задавал глупые вопросы. Очень помогли.
0
|
|
|
2753 / 2060 / 509
Регистрация: 17.02.2014
Сообщений: 9,487
|
|
| 11.05.2018, 08:52 | |
|
АнатолийШ, главное, Бро, ты понял, что нужно близко познакомиться с коллекциями и читать спецификацию языка)).
0
|
|
| 11.05.2018, 08:52 | |
|
Помогаю со студенческими работами здесь
30
Как прочитать текст из одного файла и сравнить с текстом в другом файле
Для заданного достаточно длинного слова найти в имеющемся тексте все слова, в которых использованы только буквы, имеющиеся в заданном слове
Вычеркнуть из слова Х те буквы, которые встречаются в слове Z Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
делаю науч статью по влиянию грибов на сукцессию
anaschu 13.03.2026
прикрепляю статью
|
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога
Финальные проекты на Си и на C++:
hello-sdl3-c. zip
hello-sdl3-cpp. zip
Результат:
|
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога
MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
|
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд.
Даже если у вас. . .
|
|
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает
монорепозиторий в котором находятся все исходники.
При создании нового решения, мы просто добавляем нужные проекты
и имеем. . .
|
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение:
В этой книге («Подход, основанный на вариантах использования») Ивар утверждает,
что архитектура программного обеспечения — это
структуры,. . .
|
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога
Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
|
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога
Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip
На первой гифке отладочные линии отключены, а на второй включены:. . .
|