Сумма диагональных элементов в спиральной матрице в Javascript

Итак, мне дан массив = [ 1 2 3 8 9 4 7 6 5 ], который представляет собой спиральный обход квадратной матрицы размера n x n. Что мне нужно было сделать, так это вычислить сумму первичных и вторичных диагоналей и распечатать ее. Мне удалось преобразовать этот одномерный массив в двумерный массив размером n*n и вычислить сумму обеих диагоналей следующим образом:

p.s.: массив примерно такой [[1, 2, 3], [6, 5, 8], [7, 4, 9]]

function spDiag(n,arr){
    let mat = [];
    let primary = 0, secondary = 0;
    while(arr.length) mat.push(arr.splice(0, n));
    
    for(let i = 0; i < n; i++){
        for(let j = 0; j < n; j++){
            if(i === j) primary += mat[i][j];
            
            if((i + j) === (n-1)) secondary += mat[i][j];
        }
        
    }
    console.log(primary + secondary)
    console.log(JSON.stringify(mat));
    
}

spDiag(3, [1,2,3,8,9,4,7,6,5])
But the task was to form a spiral matrix and then compute the sum of diagonals and not just a 2D matrix and because of this my output is coming wrong. How can I convert this 1D array to a spiral matrix?

Вам не нужна матрица для вычисления суммы. Сумма arr[0] + arr[2] + arr[4] + arr[6] + 2 * arr[8]. То есть arr[0 * (n - 1)] + arr[1 * (n - 1)] + arr[2 * (n - 1)] + arr[3 * (n - 1)] + 2 * arr[arr.length - 1].

jabaa 09.04.2022 20:56

@jabaa Это обобщенная формула? Я так не думаю, потому что для спиральной матрицы размера 4 x 4 это не выдерживает критики. Рассмотрим этот массив: [ 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10 ]

heartbeat 09.04.2022 22:25

Сначала вы добавляете 4 раза n-1. Затем вы добавляете 4 раза n-2. Потом... Да можно просто обобщить.

jabaa 09.04.2022 22:28

Не могли бы вы уточнить немного больше? я не понял

heartbeat 09.04.2022 22:33

Возьмите лист бумаги и начертите квадрат размером 3х3, обведите его по спирали и подсчитайте шаги. Вы пройдете 4 раза по 2 шага и один раз по 1 шагу. Попробуйте это с квадратом размером 4x4. Вы пройдете 4 раза по 3 шага, затем 4 раза по 2 шага и один раз по 1 шагу. Создайте квадрат размером 5x5. Вы пройдете 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 1 шаги. Это общая закономерность. Это математическая головоломка. Вы должны сделать некоторые головоломки в первую очередь.

jabaa 09.04.2022 22:36

Возможно, в моем алгоритме есть ошибка, но вы должны быть в состоянии исправить.

jabaa 09.04.2022 22:39

Да, точно есть ошибка. Я постараюсь понять это. Кроме того, не могли бы вы подсказать, где я могу решить такие головоломки или что-то подобное?

heartbeat 09.04.2022 22:46
adventofcode.com имеет похожие головоломки. В одной головоломке вам также нужно пройти матрицу по спирали, но это намного сложнее. Насколько я помню, вам нужно пройти по 2D-массиву вместо 1D-массива, уже содержащего спиральный путь. Но не исключено, что я что-то путаю и эта загадка была где-то в другом месте.
jabaa 09.04.2022 22:47
Формы c голосовым вводом в React с помощью Speechly
Формы c голосовым вводом в React с помощью Speechly
Пытались ли вы когда-нибудь заполнить веб-форму в области электронной коммерции, которая требует много кликов и выбора? Вас попросят заполнить дату,...
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Стилизация и валидация html-формы без использования JavaScript (только HTML/CSS)
Будучи разработчиком веб-приложений, легко впасть в заблуждение, считая, что приложение без JavaScript не имеет права на жизнь. Нам становится удобно...
Flatpickr: простой модуль календаря для вашего приложения на React
Flatpickr: простой модуль календаря для вашего приложения на React
Если вы ищете пакет для быстрой интеграции календаря с выбором даты в ваше приложения, то библиотека Flatpickr отлично справится с этой задачей....
В чем разница между Promise и Observable?
В чем разница между Promise и Observable?
Разберитесь в этом вопросе, и вы значительно повысите уровень своей компетенции.
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Что такое cURL в PHP? Встроенные функции и пример GET запроса
Клиент для URL-адресов, cURL, позволяет взаимодействовать с множеством различных серверов по множеству различных протоколов с синтаксисом URL.
Четыре эффективных способа центрирования блочных элементов в CSS
Четыре эффективных способа центрирования блочных элементов в CSS
У каждого из нас бывали случаи, когда нам нужно отцентрировать блочный элемент, но мы не знаем, как это сделать. Даже если мы реализуем какой-то...
0
8
39
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Вам действительно не нужно превращать 1D-массив в 2D-массив, а также вам не нужно посещать значение каждый в массиве. Диагонали следуют простому шаблону, так как индексное расстояние между двумя последовательными элементами по диагонали следует шаблону.

См., например, матрицу 7x7, индексы спиральной последовательности которой находятся на диагонали:

 0  .  .  .  .  .  6
 . 24  .  .  . 28  .
 .  . 40  . 42  .  .
 .  .  . 48  .  .  .
 .  . 46  . 44  .  .
 . 36  .  .  . 32  .
18  .  .  .  .  . 12

Пробелы между двумя последовательными индексами, которые находятся на диагонали (в порядке индекса): 6, 6, 6, 6, 4, 4, 4, 4, 2, 2, 2, 2. Общий шаблон для этих промежутков : 𝑛-1, 𝑛-1, 𝑛-1, 𝑛-1, 𝑛-3, 𝑛-3, 𝑛-3, 𝑛-3,... и т.д.

Реализация

Поскольку размер данного массива равен квадрату 𝑛, я не понимаю, зачем вам нужно передавать 𝑛 в качестве аргумента. Это избыточная информация.

Так:

function sumDiagonals(arr) {
    let n = Math.sqrt(arr.length);
    if (n % 1) throw "Array size should be perfect square";
    let sum = 0;
    let len = n*2 - n%2; // The number of values on diagonals
    for (let i = 0, j = 0; j < len; i += n - 1 - (j++ >> 2)*2) {
        sum += arr[i];
    }
    return sum;
}

let arr =  [1, 2, 3, 8, 9, 4, 7, 6, 5];
console.log(sumDiagonals(arr));

Посмотрите, какой будет ответ для примера массива, который я привел? Будет 30 не так ли? И код, который вы написали в соответствии с вашей логикой, дает результат как 25.

heartbeat 10.04.2022 09:48

Если вы говорите, что это 30, это означает, что центральный элемент считается дважды. Это то, что вы хотите? Я понял, что значение должно считаться только один раз (когда оно находится по диагоналям). Вероятно, это другая интерпретация. Вы можете уточнить?

trincot 10.04.2022 09:49

Извините, я просто проверял тестовые случаи, и на самом деле мой плохой ответ может быть принят, так что это не проблема. И я понимаю, что если мы не посчитаем средний элемент дважды, то ответом будет 25. Прохладно. Еще одна вещь, которую я не понимаю, это... Промежутки между двумя последовательными индексами, которые находятся на диагонали (в порядке индекса): 6, 6, 6, 6, 4, 4, 4, 4, 2, 2 , 2, 2. Общий шаблон для этих пробелов:

heartbeat 10.04.2022 10:02

Первый индекс в спиральной последовательности матрицы 7x7 с числом, расположенным по диагонали, равен 0 (верхний левый угол матрицы). Следующий индекс в спиральной последовательности, имеющий число на диагонали, равен 6 (вверху справа от матрицы). Таким образом, от 0 до 6 — это расстояние (промежуток) 6, что равно n-1 (здесь n равно 7). Следующий индекс в спирали с числом по диагонали равен 12 (нижний правый угол матрицы), поэтому снова тот же пробел и т. д.

trincot 10.04.2022 10:05

Ох! Теперь понял. И последнее, я много искал этот вопрос, хотя я не нашел никаких решений, но каждое обсуждение, которое я нашел, включает циклическое выполнение, например, взятие четырех переменных сверху, вниз, снизу и влево, а также четырех циклов for и т. д. и т. д. Но этот подход уникален. Вы узнали это сами или где-то прочитали, если можете мне сказать?

heartbeat 10.04.2022 10:15

Я только что проанализировал это сам, и вот что я придумал. Я понимаю, что есть много способов приблизиться к этому. Если бы я посмотрел на это снова через два года, забыв об этом вопросе, я мог бы придумать еще один подход. Никто на самом деле не понимает, как наш мозг придумывает идеи ;-)

trincot 10.04.2022 10:17

Другие вопросы по теме