Как прийти к предлагаемому подходу номер два в вопросе Zig Zag LeetCode номер 6

Question

Я изучаю CS и решаю вопрос LeetCode номер 6, преобразование зигзага , и я придумал решение, которое использует ту же методологию, что и подход номер один. 1004. * Для самообразования я попытался понять подход номер два, и мне трудно понять, как можно разработать эти правила. Они описаны здесь .

Моя проблема в том, что, хотя я могу использовать их правила и вывести эти числа из их формул, мне кажется, что у меня нет математических способностей, которые позволяют мне чтобы увидеть, как я мог «увидеть» это сам.

Вопрос: Если вы сами решили этот вопрос и придумали подход номер два - какие навыки вы использовали для этого? что?

Answer 1

Я сам не решил проблему, но навыки, которые я бы использовал, чтобы придумать решение, подобное второму подходу, были бы анализом и рассмотрением числовых / счетных моделей. Если проследить зигзаг, сразу станет ясно, что каждый прямой столбец имеет длину num_rows (кроме, возможно, последнего). Поразмыслив, мы понимаем, что каждая диагональ также имеет одинаковое количество символов, за исключением нижнего и верхнего, с которым она соединяется. Следовательно, мы можем посчитать каждый компонент юг-> северо-восток как num_rows + num_rows - 2 символов.

Используя logi c выше, мы можем написать формулы.

В нулевой строке у нас нет смещения:

k * (num_rows + num_rows - 2)

В последней строке (num_rows - 1) мы добавляем начальный столбец, который смещает наши вычисления:

k * (num_rows + num_rows - 2) + num_rows - 1

Середина немного сложнее, но в основном такая же. Если мы знаем верхнюю часть каждого вертикального столбца, мы добавляем i, чтобы получить i символ строки:

k * (num_rows + num_rows - 2) + i

Чтобы получить символ в той же строке, по диагонали "заг" , то есть после этого столбца мы смотрим на начало следующего столбца и вычитаем i:

(k + 1) * (num_rows + num_rows - 2) - i