Подсчитайте посещенные точки на числовой прямой

Опубликовано: 14 Января, 2022

Учитывая человека, который находится в позиции current_pos, и путь двоичной строки, который представляет собой ходы, которые сделал человек, если path [i] = '0', тогда человек переместился на один шаг влево, а если path [i] = '1', то человек переместился один шаг вправо. Задача состоит в том, чтобы найти количество различных позиций, которые посетил человек.
Примеры:

Input: current_pos = 5, path = “011101” 
Output:
Given moves are left, right, right, right, left and right 
i.e. 5 -> 4 -> 5 -> 6 -> 7 -> 6 -> 7 
The number of distinct positions are 4 (4, 5, 6 and 7).
Input: current_pos = 3, path = “110100” 
Output:
3 -> 4 -> 5 -> 4 -> 5 -> 4 -> 3 
 

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход:

  • Объявите массив points [] для хранения всех точек, через которые проходит человек.
  • Инициализируйте первую позицию этого массива текущей позицией current_pos .
  • Пройдите по строковому пути и сделайте следующее:
    • Если текущий символ «0» , то человек ушел. Уменьшите текущую позицию на 1 и сохраните ее в points [] .
    • Если текущий символ - «1» , то человек двигался вправо. Увеличьте текущую позицию на 1 и сохраните ее в points [] .
  • Подсчитайте общее количество различных элементов в точках [] . Обратитесь к разделу Подсчет различных элементов в массиве для получения информации о различных методах подсчета количества отдельных элементов в массиве.

Ниже представлена реализация описанного выше подхода:

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.