Подсчитайте посещенные точки на числовой прямой
Учитывая человека, который находится в позиции current_pos, и путь двоичной строки, который представляет собой ходы, которые сделал человек, если path [i] = '0', тогда человек переместился на один шаг влево, а если path [i] = '1', то человек переместился один шаг вправо. Задача состоит в том, чтобы найти количество различных позиций, которые посетил человек.
Примеры:
Input: current_pos = 5, path = “011101”
Output: 4
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
3 -> 4 -> 5 -> 4 -> 5 -> 4 -> 3
Подход:
- Объявите массив points [] для хранения всех точек, через которые проходит человек.
- Инициализируйте первую позицию этого массива текущей позицией current_pos .
- Пройдите по строковому пути и сделайте следующее:
- Если текущий символ «0» , то человек ушел. Уменьшите текущую позицию на 1 и сохраните ее в points [] .
- Если текущий символ - «1» , то человек двигался вправо. Увеличьте текущую позицию на 1 и сохраните ее в points [] .
- Подсчитайте общее количество различных элементов в точках [] . Обратитесь к разделу Подсчет различных элементов в массиве для получения информации о различных методах подсчета количества отдельных элементов в массиве.
Ниже представлена реализация описанного выше подхода:
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.