Nano Hash - криптовалюты, майнинг, программирование

UVa 11860: как использовать кучу для решения этой проблемы

Я пытаюсь решить проблему программирования в онлайн-судье UVa:

Анализатор документов Uva 11860

Установщик этой проблемы написал учебник по heap и некоторым операциям с ним, включая вставку, удаление узла и упомянутый в конце этой статьи - эту проблему можно решить с помощью кучи. Могут быть и другие способы ее решения. Но я не могу понять, как решить эту проблему с помощью heap. Я знаю, как кодировать кучу на С++ и могу определить функции insert(), remove(), print() и некоторые другие операции, такие как поиск минимального элемента и т. д.

Как эта проблема связана с кучей?

algorithm heap
24.10.2013

Ответы:


1

Подход, который приходит на ум:

Иметь (изначально пустую) кучу объектов, содержащих слово и его позицию — упорядочить эту кучу по позиции.

smallestDistance = infinity
biggestSize = 0
for each word in the input:
   heap.insert(Pair(current position, word))
   hashMap[word] = current position

   // We saw the word after this occurrence, so remove it
   while hashMap[heap.minimum.word] != heap.minimum.position
     heap.pop()

   // We found another word!
   //   The previous smallest is invalid, since it doesn't contain this word
   if heap.size > biggestSize
     smallestDistance = currentPosition - heap.minimum
     biggestSize = heap.size
   // Is this distance better than the best so far? If so, use it instead
   else
     smallestDistance = min(smallestDistance, currentPosition - heap.minimum)
output smallestDistance
24.10.2013
Новые материалы
Кластеризация: более глубокий взгляд
Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
Как написать эффективное резюме
Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
Частный метод Python: улучшение инкапсуляции и безопасности
Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
Как я автоматизирую тестирование с помощью Jest
Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..