Как создать визуализацию для проблемы Leetcode Two Sum – проект на HTML, CSS и JavaScript.
С текущим состоянием рынка труда многие люди посвящают много времени решению задач на LeetCode [https//leetcode.com/] в качестве подготовки к техническим собеседованиям. Но иногда было бы полезно иметь визуализацию, показывающую алгоритмы, лежащие в основе этих проблем. В этом руководстве мы...
С текущим состоянием рынка труда многие люди решают задачи на LeetCode, чтобы подготовиться к техническим собеседованиям.
Но иногда хотелось бы иметь визуализацию, показывающую алгоритмы, лежащие в основе этих задач.
В этом руководстве мы создадим визуализацию, демонстрирующую несколько подходов к популярной задаче на LeetCode, называемой Two Sum. Для создания этого проекта мы будем использовать чистый HTML, CSS и JavaScript.
Содержание
- Необходимые навыки
- Настройка проекта
- Как решить задачу Two Sum на LeetCode
- Обзор визуализации задачи Two Sum
- Добавление визуализации метода полного перебора
- Как отключить кнопку bruteForceSolutionBtn, когда выполняется анимация
- Добавление визуализации решения методом карты
- Как сбросить вывод таблицы для решения методом карты
- Финальный код решения и пример работы
- Заключение
Необходимые навыки
Это руководство предполагает, что у вас есть базовые знания HTML, CSS и JavaScript. Если вы еще не прошли начинающий курс по одному из этих языков, рекомендуется начать с следующих ресурсов:
- Сертификация CodesCode по отзывчивому веб-дизайну
- Сертификация CodesCode по алгоритмам и структурам данных на JavaScript
Это руководство также предполагает, что у вас есть базовые навыки работы с редактором кода или средой разработки. Если это не так, рекомендуется ознакомиться с следующими ресурсами:
Настройка проекта
Вы можете создать этот проект в выбранном локальном редакторе кода или через онлайн-среду разработки (IDE) или редактор, такие как CodePen, CodeSandbox или Replit.
Проект будет состоять из трех файлов: index.html, index.js и styles.css. Так как проект в основном сосредоточен на JavaScript, в этом репозитории GitHub я предоставил все необходимые HTML- и CSS-файлы.
Вы можете свободно fork and clone the repository, или вы можете скопировать код найденный в файлах HTML и CSS и добавить его в свой проект.
Как только вы настроите среду проекта, тогда вы должны запустить локальный сервер и увидеть этот результат на экране:
Как решить задачу “Two Sum” на LeetCode
Прежде чем мы сможем создать визуализацию для этой задачи, нам сначала нужно понять и решить саму задачу.
Описание
В этой задаче вам будет предоставлен список чисел в любом порядке и целевое число. Цель состоит в том, чтобы найти пару чисел, которая в сумме дает целевое число, и вернуть массив индексов для этой пары чисел.
В этом примере у нас есть следующий список чисел и целевое число:
[2,7,11,15]target: 9Числа 2 и 7 в сумме дают 9, поэтому мы вернем [0,1], потому что это представляет индексы, где можно найти пару чисел в массиве.
В этой задаче вы можете предположить, что в массиве будет как минимум два числа или более, и будет только одно возможное решение.
Так, например, вы не можете получить такой вход данных, который не имеет решения, потому что в списке нет двух чисел, которые в сумме дают целевое число.
[1,2,3,4,5]target: 55Вы также не получите входные данные с несколькими решениями. Следующий вход имеет два ответа [0,1] и [1,2], что противоречит правилам этой задачи.
[3,3,3]target: 6Подход “перебор всех возможных вариантов”
Наиболее интуитивным подходом будет начать с начала списка чисел и сравнить каждую возможную пару чисел до тех пор, пока не найдем пару, дающую в сумме целевое число.
Давайте рассмотрим пример:
[11, 15, 2, 7]target:9Мы начинаем с первого числа в списке (11) и проверяем каждую возможную пару, чтобы увидеть, дает ли она в сумме целевое число (9).
11 + 15 = 9? НЕТ11 + 2 = 9? НЕТ11 + 7 = 9? НЕТПоскольку ни одна из этих пар не равна целевому числу (9), мы переходим ко второму числу в списке (15) и проверяем все возможные пары. Нет необходимости проверять 11+15, потому что мы уже это проверили ранее.
15 + 2 = 9? НЕТ15 + 7 = 9? НЕТПоскольку ни одна из этих пар не равна целевому числу (9), мы переходим к третьему числу в списке (2) и проверяем все возможные пары.
2 + 7 = 9? ДА!!!Теперь мы нашли пару, дающую в сумме целевое число, и мы возвращаем [2,3], потому что это представляет индексы, где можно найти пару чисел в массиве.
Решение на JavaScript с помощью подхода “перебор всех возможных вариантов” и оценка временной сложности
Это решение использует вложенный цикл for, что даёт временную сложность O(n²). Внешний цикл используется для получения текущего числа в списке, а внутренний цикл используется для проверки, равна ли сумма текущего числа и других чисел в списке целевому числу.
/** * @param {number[]} nums * @param {number} target * @return {number[]} */var twoSum = function (nums, target) { if (nums.length === 2) return [0, 1]; for (let i = 0; i < nums.length; i++) { const currentNum = nums[i]; for (let j = i + 1; j < nums.length; j++) { if (currentNum + nums[j] === target) return [i, j]; } }};Примечание: Я добавил дополнительную проверку в моем решении, чтобы проверить, содержит ли входной массив только два числа. В этом случае мы сразу же возвращаем [0,1], потому что это единственные возможные индексы для этого тестового случая.
if (nums.length === 2) return [0, 1];До сих пор наши входные массивы были очень маленькими. Но если бы у нас был входной массив из 100, 500 или 1000+ чисел, то поиск пары, дающей в сумме цель, мог занять некоторое время.
В следующем разделе мы рассмотрим решение, которое использует объект Map JavaScript и выполняется за линейное время O(n).
Решение с использованием Map
В подходе «грубой силы» мы начинали с начала массива и сравнивали все возможные пары чисел, пока не находили пару, дающую в сумме цель. Но в этом подходе мы можем использовать объект Map JavaScript и один цикл for, чтобы найти эту пару.
Объект Map JavaScript – это коллекция пар ключ-значение, которая позволяет быстро выполнять поиск и имеет встроенные методы, такие как set(), get() и has().
Давайте поработаем с тем же примером, что и раньше:
[11, 15, 2, 7]target:9Мы можем начать проходить по массиву и смотреть на текущее число в списке, которое будет nums[i]. Мы также хотим создать новый объект map, который изначально будет пустым.
const map = new Map();for(let i=0; i<nums.length; i++){ }Внутри нашего цикла нам нужно вычислить разность, которая равна цели минус текущее число.
const map = new Map(); for(let i=0; i<nums.length; i++){ const difference = target - nums[i] }Поскольку мы знаем, что могут быть только два числа, дающих в сумме цель, мы можем проверить, содержится ли разность в map. Если да, мы нашли пару и можем вернуть индексы. В противном случае, мы можем добавить текущее число в map вместе с его индексом.
const map = new Map(); for(let i=0; i < nums.length; i++) { const difference = target - nums[i] if(map.has(difference)) { return [map.get(difference), i] } else { map.set(nums[i], i) } }В следующем коде метод has() используется для проверки, содержится ли следующий key в объекте map. Этот метод вернет значение true или false.
map.has(difference)Метод get() используется для возврата соответствующего элемента из map.
if(map.has(difference)) { return [map.get(difference), i] } Метод set() добавляет или обновляет запись в map с ключом и значением.
else { map.set(nums[i], i)}Вот полный код для этого подхода:
/** * @param {number[]} nums * @param {number} target * @return {number[]} */var twoSum = function(nums, target) { if(nums.length === 2) return [0,1] const map = new Map(); for (let i = 0; i < nums.length; i++) { const difference = target - nums[i] if (map.has(difference)) { return [map.get(difference), i] } else { map.set(nums[i], i) } } };Временная сложность для решения с использованием Map
Это решение имеет линейную временную сложность O(n). Так как мы используем только один цикл вместо двух, мы улучшили временную сложность и больше не работаем в квадратичном времени O(n²), как раньше.
В следующих нескольких разделах мы начнем создавать визуализации для каждого из этих подходов.
Обзор для визуализации Two Sum
Цель проекта – создать визуализации как для решений на основе карты, так и для решений на основе полного перебора.
Для решения на основе полного перебора покажем, как мы проходим через каждую пару чисел, пока не найдем пару, дающую в сумме целевое число.
Для решения на основе карты покажем, как построить карту и проверить, какая пара дает в сумме целевое число.
Добавление визуализации метода полного перебора
Создание переменных const и let
Сначала нам нужно создать переменные const и присвоить им результат доступа к элементам HTML, отвечающим за отображение кнопки решения методом полного перебора и вывода.
const bruteForceSolutionBtn = document.getElementById("brute-force-visual-btn");const bruteForceNumbersOutput = document.querySelector( "#brute-force-output > .numbers-array");const bruteForceTextOutput = document.querySelector( "#brute-force-output > .result-text");Следующий шаг – создать переменные const для массива тестового случая и целевого числа, которые будут использоваться для обоих визуализаций.
const testCaseArray = [11, 15, 2, 7];const target = 9;Затем нам нужно создать переменные let, которые будут представлять текущее число, которое мы рассматриваем во внешнем цикле, и дополняющее число, которое мы рассматриваем во внутреннем цикле.
let currentNum;let currentCompliment;Создание функции getClassName
В своей визуализации мы хотим показать пользователю текущую пару чисел, которую мы проверяем, добавляя разные цветные границы вокруг них. Текущее число будет иметь зеленую границу, а дополняющее число – синюю границу.
Для динамического обновления этих стилей со временем нам нужно создать функцию, которая будет отвечать за добавление соответствующих классов текущему числу и его дополнению.
Сначала создайте новую функцию getClassName, которая принимает параметр num.
const getClassName = (num) => { };Внутри этой функции создайте оператор switch, внутри которого num будет использоваться в качестве выражения для проверки.
const getClassName = (num) => { switch (num) { }};Первый case должен проверять currentNum и возвращать строку для класса current-num.
const getClassName = (num) => { switch (num) { case currentNum: return "class='current-num'"; }};Второй case должен проверять currentCompliment и возвращать строку для класса compliment-num.
const getClassName = (num) => { switch (num) { case currentNum: return "class='current-num'"; case currentCompliment: return "class='compliment-num'"; }};Для default случая должна возвращаться пустая строка, потому что мы не собираемся применять какие-либо классы к этому элементу.
const getClassName = (num) => { switch (num) { case currentNum: return "class='current-num'"; case currentCompliment: return "class='compliment-num'"; default: return ""; }};Создание функции bruteForceApproach
Эта функция будет отвечать за выполнение решения методом перебора и отображение визуализации на странице.
Сначала нам нужно создать функцию bruteForceApproach, которая будет асинхронной.
const bruteForceApproach = async () => {};Затем добавим внешний цикл для нашего массива тестовых случаев.
const bruteForceApproach = async () => { for (let i = 0; i < testCaseArray.length; ++i) { }};Внутри цикла for обновите currentNum, чтобы присвоить ему значение текущего числа, которое мы рассматриваем в массиве с тестовыми случаями.
const bruteForceApproach = async () => { for (let i = 0; i < testCaseArray.length; ++i) { currentNum = testCaseArray[i]; }};Затем создайте внутренний цикл for.
const bruteForceApproach = async () => { for (let i = 0; i < testCaseArray.length; ++i) { currentNum = testCaseArray[i]; for (let j = i + 1; j < testCaseArray.length; ++j) { } }};Внутри внутреннего цикла for обновите число currentCompliment и присвойте ему значение testCaseArray[j]. Это представляет каждое число справа от текущего числа.
const bruteForceApproach = async () => { for (let i = 0; i < testCaseArray.length; ++i) { currentNum = testCaseArray[i]; for (let j = i + 1; j < testCaseArray.length; ++j) { currentCompliment = testCaseArray[j]; } }};Затем нам нужно добавить setTimeout, который будет задерживать изменения разметки на одну секунду. Это поможет создать анимационный эффект показа различных пар чисел.
const bruteForceApproach = async () => { for (let i = 0; i < testCaseArray.length; ++i) { currentNum = testCaseArray[i]; for (let j = i + 1; j < testCaseArray.length; ++j) { currentCompliment = testCaseArray[j]; await new Promise((resolve) => setTimeout(resolve, 1000)); } }};Затем нам нужно обновить HTML для вывода. Начните с присвоения массива с тестовыми случаями переменной bruteForceNumbersOutput.innerHTML.
const bruteForceApproach = async () => { for (let i = 0; i < testCaseArray.length; ++i) { currentNum = testCaseArray[i]; for (let j = i + 1; j < testCaseArray.length; ++j) { currentCompliment = testCaseArray[j]; await new Promise((resolve) => setTimeout(resolve, 1000)); bruteForceNumbersOutput.innerHTML = testCaseArray; } }};Затем мы хотим использовать метод map на массиве, чтобы создать новый массив элементов span, который представляет каждое число в массиве вместе с его стилями. Нам также нужно использовать метод join, чтобы удалить запятые, которые метод map добавляет при создании нового массива.
const bruteForceApproach = async () => { for (let i = 0; i < testCaseArray.length; ++i) { currentNum = testCaseArray[i]; for (let j = i + 1; j < testCaseArray.length; ++j) { currentCompliment = testCaseArray[j]; await new Promise((resolve) => setTimeout(resolve, 1000)); bruteForceNumbersOutput.innerHTML = testCaseArray .map( (num, index) => ` <span ${getClassName(num)}> ${testCaseArray[index]} </span> ` ) .join(""); } }};Если мы не находим пару чисел, дающих нужную сумму, то мы хотим показать пользователю сообщение. Обновите текстовое содержимое для bruteForceTextOutput и присвойте ему следующее сообщение:
const bruteForceApproach = async () => { for (let i = 0; i < testCaseArray.length; ++i) { currentNum = testCaseArray[i]; for (let j = i + 1; j < testCaseArray.length; ++j) { currentCompliment = testCaseArray[j]; await new Promise((resolve) => setTimeout(resolve, 1000)); bruteForceNumbersOutput.innerHTML = testCaseArray .map( (num, index) => ` <span ${getClassName(num)}> ${testCaseArray[index]} </span> ` ) .join(""); bruteForceTextOutput.textContent = `Does the sum of ${currentNum} + ${currentCompliment} equal ${target}? НЕТ!`; } }};Последнее условие – это проверка, была ли найдена пара чисел, дающих нужную сумму. Если да, то мы можем отобразить этот конечный массив индексов и return из функции.
if (currentNum + currentCompliment === target) { bruteForceTextOutput.textContent = `Final indices: [${i}, ${j}]`; return; }Чтобы протестировать визуализацию насильственного подхода, мы должны добавить прослушиватель событий к bruteForceSolutionBtn. Прослушиватель событий должен реагировать на событие "click" и должен ссылаться на функцию bruteForceApproach.
bruteForceSolutionBtn.addEventListener("click", bruteForceApproach);Это должен быть ваш полный код на данный момент:
const bruteForceSolutionBtn = document.getElementById("brute-force-visual-btn");const bruteForceNumbersOutput = document.querySelector( "#brute-force-output > .numbers-array");const bruteForceTextOutput = document.querySelector( "#brute-force-output > .result-text");const testCaseArray = [11, 15, 2, 7];const target = 9;let currentNum;let currentCompliment;const getClassName = (num) => { switch (num) { case currentNum: return "class='current-num'"; case currentCompliment: return "class='compliment-num'"; default: return ""; }};const bruteForceApproach = async () => { for (let i = 0; i < testCaseArray.length; ++i) { currentNum = testCaseArray[i]; for (let j = i + 1; j < testCaseArray.length; ++j) { currentCompliment = testCaseArray[j]; await new Promise((resolve) => setTimeout(resolve, 1000)); bruteForceNumbersOutput.innerHTML = testCaseArray .map( (num, index) => ` <span ${getClassName(num)}> ${testCaseArray[index]} </span> ` ) .join(""); bruteForceTextOutput.textContent = `Does the sum of ${currentNum} + ${currentCompliment} equal ${target}? НЕТ!`; if (currentNum + currentCompliment === target) { bruteForceTextOutput.textContent = `Final indices: [${i}, ${j}]`; return; } } }};bruteForceSolutionBtn.addEventListener("click", bruteForceApproach);Попробуйте визуализацию, нажав кнопку “Показать визуализацию” для насильственного подхода.
Как отключить кнопку bruteForceSolutionBtn во время выполнения анимации
Если вы попытаетесь несколько раз нажать на кнопку bruteForceSolutionBtn подряд, вы увидите сбои в анимации. Чтобы исправить это, мы должны отключить кнопку, когда анимация выполняется, и затем включить ее, когда анимация завершена.
Внутри функции bruteForceApproach установите атрибут disabled для bruteForceSolutionBtn.
const bruteForceApproach = async () => { bruteForceSolutionBtn.setAttribute("disabled", "");Внутри оператора if удалите атрибут disabled для bruteForceSolutionBtn.
if (currentNum + currentCompliment === target) { bruteForceTextOutput.textContent = `Final indices: [${i}, ${j}]`; bruteForceSolutionBtn.removeAttribute("disabled"); return; }Вот полный код с исправлением:
const bruteForceSolutionBtn = document.getElementById("brute-force-visual-btn");const bruteForceNumbersOutput = document.querySelector( "#brute-force-output > .numbers-array");const bruteForceTextOutput = document.querySelector( "#brute-force-output > .result-text");const testCaseArray = [11, 15, 2, 7];const target = 9;let currentNum;let currentCompliment;const getClassName = (num) => { switch (num) { case currentNum: return "class='current-num'"; case currentCompliment: return "class='compliment-num'"; default: return ""; }};const bruteForceApproach = async () => { bruteForceSolutionBtn.setAttribute("disabled", ""); for (let i = 0; i < testCaseArray.length; ++i) { currentNum = testCaseArray[i]; for (let j = i + 1; j < testCaseArray.length; ++j) { currentCompliment = testCaseArray[j]; await new Promise((resolve) => setTimeout(resolve, 1000)); bruteForceNumbersOutput.innerHTML = testCaseArray .map( (num, index) => ` <span ${getClassName(num)}> ${testCaseArray[index]} </span> ` ) .join(""); bruteForceTextOutput.textContent = `Does the sum of ${currentNum} + ${currentCompliment} equal ${target}? NO!`; if (currentNum + currentCompliment === target) { bruteForceTextOutput.textContent = `Final indices: [${i}, ${j}]`; bruteForceSolutionBtn.removeAttribute("disabled"); return; } } }};bruteForceSolutionBtn.addEventListener("click", bruteForceApproach);Попробуйте визуализацию еще раз, и теперь вы должны увидеть, что кнопка отключена при выполнении анимации.
Добавление визуализации решения с помощью Map
Создание переменных const
Мы создадим несколько новых переменных const, которые представляют элемент кнопки оптимального решения, вывод и таблицу для анимации.
const optimalSolutionBtn = document.getElementById("optimal-visual-btn");const currentValueOutput = document.getElementById("current-value-output");const finalOptimalSolutionResult = document.getElementById( "final-optimal-result");const table = document.getElementById("table-output");const tableBodyOutput = document.getElementById("map-table-body");Вот полный список объявлений переменных для обеих визуализаций:
const bruteForceSolutionBtn = document.getElementById("brute-force-visual-btn");const bruteForceNumbersOutput = document.querySelector( "#brute-force-output > .numbers-array");const bruteForceTextOutput = document.querySelector( "#brute-force-output > .result-text");const optimalSolutionBtn = document.getElementById("optimal-visual-btn");const currentValueOutput = document.getElementById("current-value-output");const finalOptimalSolutionResult = document.getElementById( "final-optimal-result");const table = document.getElementById("table-output");const tableBodyOutput = document.getElementById("map-table-body");const testCaseArray = [11, 15, 2, 7];const target = 9;let currentNum;let currentCompliment;Создание асинхронной функции optimalApproach
Первым шагом является создание новой функции optimalApproach, которая будет async функцией. Вы можете добавить это ниже вашей функции bruteForceApproach.
const optimalApproach = async () => { };Как и функция bruteForceApproach, мы хотим отключить кнопку, когда анимация начинается, чтобы предотвратить многократное нажатие пользователем и нарушение анимации.
const optimalApproach = async () => { optimalSolutionBtn.setAttribute("disabled", "");};При первой загрузке страницы таблица по умолчанию скрыта. Мы хотим показать элемент таблицы, когда начинается анимация.
const optimalApproach = async () => { optimalSolutionBtn.setAttribute("disabled", ""); table.style.display = "block";};Каждый раз, когда мы запускаем эту анимацию, мы хотим выводить сообщения пользователю о том, нашли ли мы правильную пару или нет. В начале анимации мы хотим очистить предыдущий вывод.
const optimalApproach = async () => { optimalSolutionBtn.setAttribute("disabled", ""); table.style.display = "block"; currentValueOutput.innerHTML = "";};Затем нам нужно создать пустой объект map, который в конечном итоге будет обновляться со временем в цикле for.
const optimalApproach = async () => { optimalSolutionBtn.setAttribute("disabled", ""); table.style.display = "block"; currentValueOutput.innerHTML = ""; const map = new Map();};Далее нам нужно создать цикл for, который будет отвечать за перебор каждого числа в массиве и обновление анимации со временем.
const optimalApproach = async () => { optimalSolutionBtn.setAttribute("disabled", ""); table.style.display = "block"; currentValueOutput.innerHTML = ""; const map = new Map(); for (let i = 0; i < testCaseArray.length; ++i) { }};Внутри цикла нам нужно добавить выражение для вычисления разности.
const optimalApproach = async () => { optimalSolutionBtn.setAttribute("disabled", ""); table.style.display = "block"; currentValueOutput.innerHTML = ""; const map = new Map(); for (let i = 0; i < testCaseArray.length; ++i) { const difference = target - testCaseArray[i]; }};Затем нам нужно добавить setTimeout, который задержит изменения на 2 секунды в HTML разметке и поможет с эффектом анимации.
const optimalApproach = async () => { optimalSolutionBtn.setAttribute("disabled", ""); table.style.display = "block"; currentValueOutput.innerHTML = ""; const map = new Map(); for (let i = 0; i < testCaseArray.length; ++i) { const difference = target - testCaseArray[i]; await new Promise((resolve) => setTimeout(resolve, 2000)); }};Затем нам нужно добавить оператор if, чтобы проверить, содержит ли карта значения разности.
const optimalApproach = async () => { optimalSolutionBtn.setAttribute("disabled", ""); table.style.display = "block"; currentValueOutput.innerHTML = ""; const map = new Map(); for (let i = 0; i < testCaseArray.length; ++i) { const difference = target - testCaseArray[i]; await new Promise((resolve) => setTimeout(resolve, 2000)); if (map.has(difference)) { } }};Внутри оператора if нам нужно обновить содержимое текста, чтобы показать окончательный результат массива индексов на экране. Мы будем использовать метод get, чтобы получить значение индекса из map.
if (map.has(difference)) { finalOptimalSolutionResult.textContent = `Final indices: [${map.get( difference )}, ${i}]`; }Нам также нужно обновить вывод, чтобы показать сообщение о том, что мы нашли пару чисел, дающих в сумме целевую величину.
if (map.has(difference)) { finalOptimalSolutionResult.textContent = `Final indices: [${map.get( difference )}, ${i}]`; currentValueOutput.innerHTML = ` <p>Difference(${difference}) = target(${target}) - current number(${testCaseArray[i]})</p> <p>Is the difference(${difference}) in our map? YES, we found that pair of numbers that add up to the target.</p> `; }Также нам нужно удалить атрибут disabled из optimalSolutionBtn и вернуться из функции.
if (map.has(difference)) { finalOptimalSolutionResult.textContent = `Окончательные индексы: [${map.get( difference )}, ${i}]`; currentValueOutput.innerHTML = ` <p>Разница(${difference}) = цель(${target}) - текущее число(${testCaseArray[i]})</p> <p>Разница(${difference}) есть в нашей карте? ДА, мы нашли пару чисел, которые в сумме дают цель.</p> `; optimalSolutionBtn.removeAttribute("disabled"); return; }Если пара не найдена, то нам нужно добавить ветку else.
if (map.has(difference)) { finalOptimalSolutionResult.textContent = `Окончательные индексы: [${map.get( difference )}, ${i}]`; currentValueOutput.innerHTML = ` <p>Разница(${difference}) = цель(${target}) - текущее число(${testCaseArray[i]})</p> <p>Разница(${difference}) есть в нашей карте? ДА, мы нашли пару чисел, которые в сумме дают цель.</p> `; optimalSolutionBtn.removeAttribute("disabled"); return; } else { }Внутри ветки else нужно обновить сообщение, чтобы показать, что мы не нашли пару и текущее число testCaseArray[i] будет добавлено в map вместе с его индексом.
else { currentValueOutput.innerHTML = ` <p>Разница(${difference}) = цель(${target}) - текущее число(${testCaseArray[i]})</p> <p>Разница(${difference}) есть в нашей карте? Нет.</p> <p>Добавьте текущее число ${testCaseArray[i]} к нашей карте.</p> `;}Затем нужно обновить вывод таблицы с текущим числом и его индексом.
else { currentValueOutput.innerHTML = ` <p>Разница(${difference}) = цель(${target}) - текущее число(${testCaseArray[i]})</p> <p>Разница(${difference}) есть в нашей карте? Нет.</p> <p>Добавьте текущее число ${testCaseArray[i]} к нашей карте.</p> `; tableBodyOutput.innerHTML += ` <tr> <td>${testCaseArray[i]}</td> <td>${i}</td> </tr> `;}Наконец, используйте метод set, чтобы установить текущее число и его индексное значение в map.
else { currentValueOutput.innerHTML = ` <p>Разница(${difference}) = цель(${target}) - текущее число(${testCaseArray[i]})</p> <p>Разница(${difference}) есть в нашей карте? Нет.</p> <p>Добавьте текущее число ${testCaseArray[i]} к нашей карте.</p> `; tableBodyOutput.innerHTML += ` <tr> <td>${testCaseArray[i]}</td> <td>${i}</td> </tr> `; map.set(testCaseArray[i], i);}Вот полный код для вашей функции optimalApproach.
const optimalApproach = async () => { optimalSolutionBtn.setAttribute("disabled", ""); table.style.display = "block"; currentValueOutput.innerHTML = ""; const map = new Map(); for (let i = 0; i < testCaseArray.length; ++i) { const difference = target - testCaseArray[i]; await new Promise((resolve) => setTimeout(resolve, 2000)); if (map.has(difference)) { finalOptimalSolutionResult.textContent = `Окончательные индексы: [${map.get( difference )}, ${i}]`; currentValueOutput.innerHTML = ` <p>Разница(${difference}) = цель(${target}) - текущее число(${testCaseArray[i]})</p> <p>Разница(${difference}) есть в нашей карте? ДА, мы нашли пару чисел, которые в сумме дают цель.</p> `; optimalSolutionBtn.removeAttribute("disabled"); return; } else { currentValueOutput.innerHTML = ` <p>Разница(${difference}) = цель(${target}) - текущее число(${testCaseArray[i]})</p> <p>Разница(${difference}) есть в нашей карте? Нет.</p> <p>Добавьте текущее число ${testCaseArray[i]} к нашей карте.</p> `; tableBodyOutput.innerHTML += ` <tr> <td>${testCaseArray[i]}</td> <td>${i}</td> </tr> `; map.set(testCaseArray[i], i); } }};Чтобы протестировать эту визуализацию, добавьте прослушиватель событий к optimalSolutionBtn и передайте событие "click" и ссылку на функцию optimalApproach.
optimalSolutionBtn.addEventListener("click", optimalApproach);При нажатии на кнопку “Показать визуализацию” для решения карты вы должны увидеть анимацию, как показано ниже:
Как сбросить вывод таблицы для решения карты
Если вы попытаетесь запустить анимацию несколько раз, то увидите, что таблица показывает результаты предыдущего запуска.
Чтобы исправить это, мы можем сбросить таблицу перед каждым запуском анимации. Начните с создания функции resetTable перед вашей функцией optimalApproach.
const resetTable = () => { };const optimalApproach = async () => { .........Внутри этой функции очистите таблицу и окончательные текстовые результаты.
const resetTable = () => { tableBodyOutput.innerHTML = ""; finalOptimalSolutionResult.textContent = "";};Вызовите функцию resetTable внутри вашей функции optimalApproach, чтобы увидеть результаты сброса таблицы.
const optimalApproach = async () => { resetTable(); optimalSolutionBtn.setAttribute("disabled", ""); ...........Попробуйте анимацию снова, и теперь вы должны увидеть, что результаты таблицы сбрасываются перед каждым новым запуском анимации.
Финальный код решения и живой пример
Вот полный код решения на JavaScript для обеих визуализаций:
const bruteForceSolutionBtn = document.getElementById("brute-force-visual-btn");const bruteForceNumbersOutput = document.querySelector( "#brute-force-output > .numbers-array");const bruteForceTextOutput = document.querySelector( "#brute-force-output > .result-text");const optimalSolutionBtn = document.getElementById("optimal-visual-btn");const currentValueOutput = document.getElementById("current-value-output");const finalOptimalSolutionResult = document.getElementById( "final-optimal-result");const table = document.getElementById("table-output");const tableBodyOutput = document.getElementById("map-table-body");const testCaseArray = [11, 15, 2, 7];const target = 9;let currentNum;let currentCompliment;const getClassName = (num) => { switch (num) { case currentNum: return "class='current-num'"; case currentCompliment: return "class='compliment-num'"; default: return ""; }};const bruteForceApproach = async () => { bruteForceSolutionBtn.setAttribute("disabled", ""); for (let i = 0; i < testCaseArray.length; ++i) { currentNum = testCaseArray[i]; for (let j = i + 1; j < testCaseArray.length; ++j) { currentCompliment = testCaseArray[j]; await new Promise((resolve) => setTimeout(resolve, 1000)); bruteForceNumbersOutput.innerHTML = testCaseArray .map( (num, index) => ` <span ${getClassName(num)}> ${testCaseArray[index]} </span> ` ) .join(""); bruteForceTextOutput.textContent = `Does the sum of ${currentNum} + ${currentCompliment} equal ${target}? NO!`; if (currentNum + currentCompliment === target) { bruteForceTextOutput.textContent = `Final indices: [${i}, ${j}]`; bruteForceSolutionBtn.removeAttribute("disabled"); return; } } }};const resetTable = () => { tableBodyOutput.innerHTML = ""; finalOptimalSolutionResult.textContent = "";};const optimalApproach = async () => { resetTable(); optimalSolutionBtn.setAttribute("disabled", ""); table.style.display = "block"; currentValueOutput.innerHTML = ""; const map = new Map(); for (let i = 0; i < testCaseArray.length; ++i) { const difference = target - testCaseArray[i]; await new Promise((resolve) => setTimeout(resolve, 2000)); if (map.has(difference)) { finalOptimalSolutionResult.textContent = `Final indices: [${map.get( difference )}, ${i}]`; currentValueOutput.innerHTML = ` <p>Difference(${difference}) = target(${target}) - current number(${testCaseArray[i]})</p> <p>Is the difference(${difference}) in our map? YES, we found that pair of numbers that add up to the target.</p> `; optimalSolutionBtn.removeAttribute("disabled"); return; } else { currentValueOutput.innerHTML = ` <p>Difference(${difference}) = target(${target}) - current number(${testCaseArray[i]})</p> <p>Is the difference(${difference}) in our map? No.</p> <p>Add the current number ${testCaseArray[i]} to our map.</p> `; tableBodyOutput.innerHTML += ` <tr> <td>${testCaseArray[i]}</td> <td>${i}</td> </tr> `; map.set(testCaseArray[i], i); } }};bruteForceSolutionBtn.addEventListener("click", bruteForceApproach);optimalSolutionBtn.addEventListener("click", optimalApproach);Вот ссылка еще раз на финальный результат на CodePen.
Заключение
Надеюсь, вам понравился этот проект и вы узнали немного больше о том, как работает проблема Two Sum.
Я призываю вас поиграть с проектом и, возможно, добавить некоторые новые функции самостоятельно, например, попробовать разные числа или запросить ввод пользовательских данных для массива чисел и целевых значений. 👍🏾
Leave a Reply