Ежедневный бит (е) C ++ # 189, Распространенная проблема на собеседовании: обход спирали.
Сегодня мы рассмотрим распространенную задачу интервью C++: обход спирали.
Учитывая сетку размером m*n как std::vector‹std::vector‹int››, вернуть элементы этой сетки в порядке обхода по спирали.
То есть, начиная с нулевой строки, нулевого столбца, повторяйте до тех пор, пока не будут пройдены все элементы сетки:
- продвигаться по колоннам
- продвигаться по рядам
- спускаться по колоннам
- спускаться по рядам
Обратите внимание, что элементы пронумерованы в порядке обхода только в демонстрационных целях.
Прежде чем вы продолжите читать решение, я рекомендую вам попробовать решить его самостоятельно. Вот ссылка на Compiler Explorer с парой тестов: https://compiler-explorer.com/z/rEv5bMz9v.
Решение
Эта задача довольно проста, но требует тщательной реализации.
Учтите, что как только мы завершим один раздел обхода, мы никогда не будем повторно посещать соответствующую строку или столбец.
Таким образом, мы можем добиться обхода по спирали, отслеживая нижние и верхние границы для еще не пройденных строк и столбцов. Как только мы проходим один участок спирали, мы корректируем соответствующую границу, гарантируя, что следующие участки обхода избегают этой строки или столбца.
std::vector<int> spiral_traversal(
const std::vector<std::vector<int>>& matrix) {
std::vector<int> result;
if (std::ssize(matrix) == 0 || std::ssize(matrix[0]) == 0)
return result;
int64_t left = 0;
int64_t right = std::ssize(matrix[0]) - 1;
int64_t top = 0;
int64_t bottom = std::ssize(matrix) - 1;
// While we have columns or rows to process.
while (left <= right && top <= bottom) {
if (top <= bottom) // Ensure there is a row to process
for (int64_t i = left; i <= right; ++i) // Advance over columns
result.push_back(matrix[top][i]);
// Move boundary so that this row will not be traversed again.
++top;
if (left <= right) // Ensure there is a column to process
for (int64_t i = top; i <= bottom; ++i) // Advance over rows
result.push_back(matrix[i][right]);
// Move boundary so that this column will not be traversed again.
--right;
if (top <= bottom) // Ensure there is a row to process
for (int64_t i = right; i >= left; --i) // Descend over columns
result.push_back(matrix[bottom][i]);
// Move boundary so that this row will not be traversed again.
--bottom;
if (left <= right) // Ensure there is a column to process
for (int64_t i = bottom; i >= top; --i) // Descend over rows
result.push_back(matrix[i][left]);
// Move boundary so that this column will not be traversed again.
++left;
}
return result;
}
