Большинство камней удалено в одном ряду или столбце

Я не могу понять, в чем логический недостаток моего кода

Я пытаюсь решить эту проблему:

947. Большинство камней удалено из одной и той же строки или столбца.

На двумерной плоскости мы размещаем n камней в некоторых целочисленных точках координат. В каждой координатной точке может быть не более одного камня.

Камень можно удалить, если он находится в той же строке или в том же столбце, что и другой камень, который не был удален.

Учитывая массив камней длины n, где камни[i] = [xi, yi] представляют местоположение i-го камня, верните максимально возможное количество камней, которые можно удалить.

/**

 * @param {number[][]} stones
 * @return {number}
 */
var removeStones = function (stones) {
    const rowMap = {}
    const colMap = {}
    for (let i = 0; i < stones.length; i++) {
        const [row, col] = stones[i]
        if (!rowMap[row]) rowMap[row] = 0
        if (!colMap[col]) colMap[col] = 0
        rowMap[row] += 1
        colMap[col] += 1
    }
    return findMaxMove(stones, 0, rowMap, colMap)
};

const findMaxMove = (stones, index, rowMap, colMap) => {
    if (index == stones.length) return 0
    const [row, col] = stones[index]
    let isInCol = colMap[col] > 1
    let isInRow = rowMap[row] > 1
    let removedMove = 0
    if (isInCol || isInRow) {
        const colMapCopy = { ...colMap, [col]: colMap[col] - 1 }
        const rowMapCopy = { ...rowMap, [row]: rowMap[row] - 1 }
        removedMove = 1 + findMaxMove(stones, index + 1, rowMapCopy, colMapCopy);
    }
    return Math.max(removedMove, findMaxMove(stones, index + 1, rowMap, colMap))
}

В каком-то случае он проходит, а в каком-то случае не проходит:

случай, когда он не работает:

stones = [[0,1],[1,2],[1,3],[3,3],[2,3],[0,2]]
Expected: 5
Output: 4

Из Интернета я узнал, что распространенную проблему можно решить с помощью набора Disjoint, но я хотел решить ее с помощью грубой силы, прежде чем погрузиться в набор Disjoint.

Любая помощь, пожалуйста

Это потому, что вам нужно выбрать правильные элементы для удаления, чтобы в итоге осталось наименьшее количество элементов. Если вы удалите элемент, потому что он следующий по порядку и его можно удалить по закону, вы можете упустить шанс сделать оптимальный выбор.

James 25.08.2024 01:54

Рассмотрите возможность сохранения элемента с максимальной суммой rowMap + colMap.

James 25.08.2024 02:02

@code_monk, диагональная линия?

trincot 25.08.2024 20:46
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
Улучшение производительности загрузки с помощью Google Tag Manager и атрибута Defer
В настоящее время производительность загрузки веб-сайта имеет решающее значение не только для удобства пользователей, но и для ранжирования в...
Безумие обратных вызовов в javascript [JS]
Безумие обратных вызовов в javascript [JS]
Здравствуйте! Юный падаван 🚀. Присоединяйся ко мне, чтобы разобраться в одной из самых запутанных концепций, когда вы начинаете изучать мир...
Система управления парковками с использованием HTML, CSS и JavaScript
Система управления парковками с использованием HTML, CSS и JavaScript
Веб-сайт по управлению парковками был создан с использованием HTML, CSS и JavaScript. Это простой сайт, ничего вычурного. Основная цель -...
JavaScript Вопросы с множественным выбором и ответы
JavaScript Вопросы с множественным выбором и ответы
Если вы ищете платформу, которая предоставляет вам бесплатный тест JavaScript MCQ (Multiple Choice Questions With Answers) для оценки ваших знаний,...
0
3
55
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

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

Неудачный тестовый пример представляет эту плоскость:

. 0 5 .
. . 1 2
. . . 4
. . . 3

Поскольку ваш код удаляет камни в порядке их индекса, вы сначала удалите камни 0 и 1, оставив камень 5 осиротевшим:

. . 5 .
. . . 2
. . . 4
. . . 3

Это не оптимальное решение, так как вы можете сначала удалить 0 (как вы это сделали), но затем сначала удалить 5, а затем удалить 1. И тогда все камни можно будет удалить.

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

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

Pravin Poudel 27.08.2024 02:13

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