JuniorКодЧастоЕщё не отвечали
Кратчайшее расстояние между X и Y в строке
Дана строка из 'X', 'Y' и 'O'. Верните кратчайшее расстояние между любым 'X' и любым 'Y', где соседние позиции — расстояние 1. Верните 0, если одна из букв отсутствует.
Требования:
- O(n) время, O(1) дополнительной памяти — один проход.
int shortestXY(const std::string& s) {
// ваш код здесь
}Допишите реализацию.
Пройдите один раз, храня последний виденный индекс X и Y. На X, если Y уже встречался, обновляйте минимум через i - lastY; на Y симметрично через i - lastX. Если одна из букв не встретилась, верните 0. Один проход, O(n) время, O(1) память.
- ✗Обновлять только
lastXи неlastY(или наоборот), пропуская пары в одну сторону - ✗Возвращать устаревшее большое значение-маркер, когда одна из букв не встретилась, вместо 0
- ✗Считать расстояние только от первого вхождения, а не от ближайшего
- →Почему достаточно хранить только последний виденный индекс каждой буквы?
- →Как расширить это до кратчайшего расстояния между любыми двумя из K букв?
Оглавление
Задача
Найдите кратчайшее расстояние между X и Y в строке из X/Y/O за один проход; 0, если одной из букв нет.
Решение
#include <string>
#include <climits>
#include <algorithm>
int shortestXY(const std::string& s) {
int lastX = -1, lastY = -1, best = INT_MAX;
for (int i = 0; i < static_cast<int>(s.size()); ++i) {
if (s[i] == 'X') {
lastX = i;
if (lastY != -1) best = std::min(best, i - lastY);
} else if (s[i] == 'Y') {
lastY = i;
if (lastX != -1) best = std::min(best, i - lastX);
}
}
return best == INT_MAX ? 0 : best; // нет одной из букв
}Ключевые моменты
- На каждой букве обновляем расстояние до последней противоположной — этого достаточно для ближайшей пары.
- Храним последние индексы обеих букв, а не только одной.
- Если
bestосталсяINT_MAX, одной из букв нет — возвращаем 0.
Оглавление
