JavaScript | LeetCode

Задача: 1034. Coloring A Border Сложность: medium Вам дана целочисленная матричная сетка m x n и три целых числа row, col и color. Каждое значение в сетке представляет собой цвет квадрата сетки в данном месте. Два квадрата называются смежными, если они находятся рядом друг с другом в любом из 4 направлений. Два квадрата принадлежат одному связанному компоненту, если они имеют одинаковый цвет и являются смежными. Граница связанного компонента - это все квадраты в связанном компоненте, которые либо смежны (по крайней мере) с квадратом, не входящим в компонент, либо находятся на границе сетки (в первой или последней строке или столбце). Вы должны окрасить границу связанного компонента, содержащего квадрат grid[row][col], в цвет. Верните конечную сетку. Пример:

    
        Input: grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
Output: [[3,3],[3,2]]{}
    

👨‍💻 Алгоритм: 1⃣Поиск связанного компонента: Используйте поиск в глубину (DFS) или поиск в ширину (BFS), чтобы найти все клетки, принадлежащие связанному компоненту, содержащему клетку grid[row][col]. Запомните все клетки, которые принадлежат этому компоненту. 2⃣Определение границ компонента: Для каждой клетки в связанном компоненте проверьте, является ли она границей. Клетка является границей, если она находится на краю сетки или если хотя бы одна из её соседних клеток не принадлежит связанному компоненту или имеет другой цвет. 3⃣Окрашивание границы: Измените цвет всех клеток, являющихся границами, на заданный цвет. 😎 Решение:

    
        var colorBorder = function(grid, row, col, color) {
    const m = grid.length, n = grid[0].length;
    const originalColor = grid[row][col];
    const visited = new Array(m).fill(null).map(() => new Array(n).fill(false));
    const borders = [];

    const dfs = (r, c) => {
        visited[r][c] = true;
        let isBorder = false;
        for (const [dr, dc] of [[-1, 0], [1, 0], [0, -1], [0, 1]]) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                if (!visited[nr][nc]) {
                    if (grid[nr][nc] === originalColor) {
                        dfs(nr, nc);
                    } else {
                        isBorder = true;
                    }
                }
            } else {
                isBorder = true;
            }
        }
        if (isBorder || r === 0 || r === m - 1 || c === 0 || c === n - 1) {
            borders.push([r, c]);
        }
    };

    dfs(row, col);
    for (const [r, c] of borders) {
        grid[r][c] = color;
    }

    return grid;
};{}
    

Ставь 👍 и забирай 📚 Базу знаний

Задача: 191. Number of 1 Bits Сложность: easy Напишите функцию, которая принимает бинарное представление положительного целого числа и возвращает количество установленных битов (также известных как вес Хэмминга). Пример:

    
        Input: n = 11

Output: 3

Explanation:

The input binary string 1011 has a total of three set bits.{}
    

👨‍💻 Алгоритм: 1️⃣Решение простое: проверяем каждый из 32 битов числа. Если бит равен 1, увеличиваем количество 1-битов на единицу. 2️⃣Для проверки i-го бита числа используем битовую маску. Начинаем с маски m=1, так как двоичное представление 1 это 0000 0000 0000 0000 0000 0000 0000 0001. Логическое И между любым числом и маской 1 дает нам младший бит этого числа. 3️⃣Для проверки следующего бита сдвигаем маску влево на один: 0000 0000 0000 0000 0000 0000 0000 0010 и так далее. 😎 Решение:

    
        function hammingWeight(n) {
    let bits = 0;
    let mask = 1;
    for (let i = 0; i < 32; i++) {
        if ((n & mask) !== 0) {
            bits++;
        }
        mask <<= 1;
    }
    return bits;
}{}
    

Ставь 👍 и забирай 📚 Базу знаний

Как frontend-разработчику вырасти в ЗП? День сурка frontend-разработчика выглядит так Зарплата замерла, задачи — бесконечный повтор, растет только кол-во бессмысленных созвонов Откликаешься на вакансии — отвечают только ноунеймы, на собесах закидывают странными алгоритмами «на скорость». И самое бесящее — пока буксуешь, кто-то вокруг спокойно забирает офферы в Яндекс и VK...

Ты тоже можешь получить оффер в компанию, в которой тебя будут ценить и хорошо платить.

👋 Меня зовут Тихон, привет! Я — действующий Frontend-разработчик и ментор. Я за руку довожу до оффера на хорошую позицию в Big Tech и сопровождаю на испытательном сроке. В своем канале: 👉Объясняю, как проходить HR-фильтр и превращать отклики в реальные приглашения 👉Помогаю найти мотивацию, борюсь убеждениями, которые мешают развиваться 👉На примерах объясняю как проходить собеседования, включая техничку 👉Разбираю резюме и делюсь лайфхаками, например как аккуратно “пинговать” рекрутеров А еще регулярно публикую полезные материалы: ▪️Задачи, на которых валяться кандидаты ▪️База по микрофронтам ▪️Подборка из 100+ каналов с вакансиями для разработчиков ▪️100 вопросов, которые точно помогут тебе на собеседовании ▪️Чек лист проверки своего резюме А еще у меня множество успешных кейсов и трогательных отзывов, найти их можно в канале. Реклама, erid: 2W5zFGNbLL9 ИП Галактионов Тихон Витальевич, ИНН 771618975809

Задача: 531. Lonely Pixel I Сложность: medium Дано изображение размером m x n, состоящее из чёрных ('B') и белых ('W') пикселей. Верните количество чёрных одиночных пикселей. Чёрный одиночный пиксель — это символ 'B', расположенный в такой позиции, где в той же строке и в том же столбце нет других чёрных пикселей. Пример:

    
        Input: picture = [["W","W","B"],["W","B","W"],["B","W","W"]]
Output: 3
Explanation: All the three 'B's are black lonely pixels.{}
    

👨‍💻 Алгоритм: 1⃣ Подсчёт количества чёрных пикселей в строках и столбцах: Пройдите по всей матрице picture, для каждой чёрной клетки (x, y) увеличивайте rowCount[x] и colCount[y] на 1. 2⃣ Поиск одиночных чёрных пикселей: Снова пройдите по всей матрице и для каждой чёрной клетки (x, y) проверьте значения rowCount[x] и colCount[y]. Если оба значения равны 1, увеличьте переменную answer на 1. 3⃣ Возврат результата: Верните answer. 😎 Решение:

    
        var findLonelyPixel = function(picture) {
    let n = picture.length;
    let m = picture[0].length;
    
    let rowCount = new Array(n).fill(0);
    let columnCount = new Array(m).fill(0);
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (picture[i][j] === 'B') {
                rowCount[i]++;
                columnCount[j]++;
            }
        }
    }
    
    let answer = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (picture[i][j] === 'B' && rowCount[i] === 1 && columnCount[j] === 1) {
                answer++;
            }
        }
    }
    
    return answer;
};{}
    

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1219. Path with Maximum Gold Сложность: medium В золотом руднике размером m x n каждая ячейка содержит целое число, представляющее количество золота в этой ячейке, или 0, если она пуста. Верните максимальное количество золота, которое вы можете собрать при следующих условиях: - Каждый раз, когда вы находитесь в ячейке, вы собираете всё золото из этой ячейки. - Из вашей позиции вы можете сделать один шаг влево, вправо, вверх или вниз. - Вы не можете посещать одну и ту же ячейку более одного раза. - Никогда не посещайте ячейку с 0 золотом. - Вы можете начинать и прекращать сбор золота с любой позиции в сетке, которая содержит золото. Пример:

    
        Input: grid = [[0,6,0],[5,8,7],[0,9,0]]
Output: 24
Explanation:
[[0,6,0],
 [5,8,7],
 [0,9,0]]
Path to get the maximum gold, 9 -> 8 -> 7.{}
    

👨‍💻 Алгоритм: 1⃣Инициализация и подготовка: Инициализируйте константный массив DIRECTIONS для направления перемещений. Определите количество строк и столбцов в сетке. Инициализируйте переменную maxGold для хранения максимального количества собранного золота. 2⃣Функция DFS и обратный трек: Реализуйте функцию dfsBacktrack для поиска пути с максимальным золотом с помощью DFS и обратного трека. Обрабатывайте базовый случай, проверяя выход за пределы сетки или ячейки без золота. Пометьте текущую ячейку как посещённую и сохраните её значение. Исследуйте каждую из четырёх смежных ячеек и обновите максимальное количество золота, если найден лучший путь. Сбросьте текущую ячейку до её исходного значения для дальнейших исследований. 3⃣Поиск максимального золота: Используйте вложенные циклы для каждой ячейки в сетке, чтобы найти максимальное количество золота, начиная с этой ячейки, с помощью функции dfsBacktrack. Обновите maxGold при нахождении лучшего пути. Верните maxGold. 😎 Решение:

    
        var getMaximumGold = function(grid) {
    const directions = [0, 1, 0, -1, 0];
    const rows = grid.length;
    const cols = grid[0].length;
    let maxGold = 0;

    function dfsBacktrack(grid, rows, cols, row, col) {
        if (row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] === 0) {
            return 0;
        }
        const originalVal = grid[row][col];
        grid[row][col] = 0;
        let maxGold = 0;

        for (let i = 0; i < 4; i++) {
            maxGold = Math.max(maxGold, dfsBacktrack(grid, rows, cols, row + directions[i], col + directions[i + 1]));
        }

        grid[row][col] = originalVal;
        return maxGold + originalVal;
    }

    for (let row = 0; row < rows; row++) {
        for (let col = 0; col < cols; col++) {
            maxGold = Math.max(maxGold, dfsBacktrack(grid, rows, cols, row, col));
        }
    }

    return maxGold;
};{}
    

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1005. Maximize Sum Of Array After K Negations Сложность: easy Учитывая целочисленный массив nums и целое число k, измените массив следующим образом: выберите индекс i и замените nums[i] на -nums[i]. Вы должны применить этот процесс ровно k раз. Вы можете выбрать один и тот же индекс i несколько раз. Верните наибольшую возможную сумму массива после его модификации таким образом. Пример:

    
        Input: nums = [4,2,3], k = 1
Output: 5{}
    

👨‍💻 Алгоритм: 1⃣Сортировка массива: Отсортируйте массив nums по возрастанию, чтобы наибольшее количество раз менять самые маленькие (отрицательные) значения на их противоположные. 2⃣Модификация массива: Пройдитесь по отсортированному массиву и замените k наименьших значений на их противоположные (умножьте на -1). Если встретите 0, прекратите дальнейшие изменения, так как изменение 0 на -0 не имеет смысла. 3⃣Проверка остатка изменений: Если после первого прохода остались изменения (k нечетное), то найдите минимальное значение в измененном массиве и еще раз поменяйте его знак. Это обеспечит максимальную сумму. 😎 Решение:

    
        class Solution {
    largestSumAfterKNegations(nums, k) {
        nums.sort((a, b) => a - b);
        
        for (let i = 0; i < nums.length; i++) {
            if (k > 0 && nums[i] < 0) {
                nums[i] = -nums[i];
                k--;
            }
        }
        
        if (k % 2 === 1) {
            nums.sort((a, b) => a - b);
            nums[0] = -nums[0];
        }
        
        return nums.reduce((a, b) => a + b, 0);
    }
}{}
    

Ставь 👍 и забирай 📚 Базу знаний

Задача: 654. Maximum Binary Tree Сложность: medium Вам дан целочисленный массив nums без дубликатов. Из nums можно рекурсивно построить максимальное двоичное дерево, используя следующий алгоритм: создайте корневой узел, значение которого равно максимальному значению в nums. Рекурсивно постройте левое поддерево по префиксу подмассива слева от максимального значения. Рекурсивно постройте правое поддерево по суффиксу подмассива справа от максимального значения. Верните максимальное двоичное дерево, построенное из nums. Пример:

    
        Input: nums = [3,2,1,6,0,5]
Output: [6,3,5,null,2,0,null,null,1]{}
    

👨‍💻 Алгоритм: 1⃣Найдите максимальное значение в текущем подмассиве и создайте узел с этим значением. 2⃣Рекурсивно постройте левое поддерево для подмассива слева от максимального значения. 3⃣Рекурсивно постройте правое поддерево для подмассива справа от максимального значения. 😎 Решение:

    
        function TreeNode(val, left, right) {
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

var constructMaximumBinaryTree = function(nums) {
    if (!nums.length) return null;
    let maxIndex = nums.indexOf(Math.max(...nums));
    let root = new TreeNode(nums[maxIndex]);
    root.left = constructMaximumBinaryTree(nums.slice(0, maxIndex));
    root.right = constructMaximumBinaryTree(nums.slice(maxIndex + 1));
    return root;
};{}
    

Ставь 👍 и забирай 📚 Базу знаний

Задача: 1503. Last Moment Before All Ants Fall Out of a Plank Сложность: medium У нас есть деревянная доска длиной n единиц. Некоторые муравьи ходят по доске, каждый муравей движется со скоростью 1 единица в секунду. Некоторые муравьи движутся влево, другие движутся вправо. Когда два муравья, движущиеся в разных направлениях, встречаются в какой-то точке, они меняют свои направления и продолжают двигаться дальше. Предполагается, что изменение направлений не занимает дополнительного времени. Когда муравей достигает одного из концов доски в момент времени t, он сразу же падает с доски. Дано целое число n и два целых массива left и right, обозначающие позиции муравьев, движущихся влево и вправо соответственно. Верните момент, когда последний(е) муравей(и) падает(ют) с доски. Пример:

    
        Input: n = 4, left = [4,3], right = [0,1]
Output: 4
Explanation: In the image above:
-The ant at index 0 is named A and going to the right.
-The ant at index 1 is named B and going to the right.
-The ant at index 3 is named C and going to the left.
-The ant at index 4 is named D and going to the left.
The last moment when an ant was on the plank is t = 4 seconds. After that, it falls immediately out of the plank. (i.e., We can say that at t = 4.0000000001, there are no ants on the plank).{}
    

👨‍💻 Алгоритм: 1⃣Инициализируйте переменную ans значением 0. 2⃣Итерация по массиву left и обновление ans значением num, если оно больше текущего значения ans. 3⃣Итерация по массиву right и обновление ans значением n - num, если оно больше текущего значения ans. Верните значение ans. 😎 Решение:

    
        var getLastMoment = function(n, left, right) {
    let ans = 0
    for (let num of left) {
        ans = Math.max(ans, num)
    }
    for (let num of right) {
        ans = Math.max(ans, n - num)
    }
    return ans
}{}
    

Ставь 👍 и забирай 📚 Базу знаний

Задача: 560. Subarray Sum Equals K Сложность: easy Дан массив целых чисел nums и целое число k, вернуть общее количество подмассивов, сумма которых равна k. Подмассив - это непрерывная непустая последовательность элементов внутри массива. Пример:

    
        Input: nums = [1,1,1], k = 2
Output: 2{}
    

👨‍💻 Алгоритм: 1⃣Самый простой метод - рассмотреть каждый возможный подмассив данного массива nums. 2⃣Найти сумму элементов каждого из этих подмассивов и проверить равенство полученной суммы с заданным k. 3⃣Всякий раз, когда сумма равна k, увеличить счетчик, используемый для хранения необходимого результата. 😎 Решение:

    
        class Solution {
    subarraySum(nums, k) {
        let count = 0;
        for (let start = 0; start < nums.length; start++) {
            for (let end = start + 1; end <= nums.length; end++) {
                let sum = 0;
                for (let i = start; i < end; i++) {
                    sum += nums[i];
                }
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }
}{}
    

Ставь 👍 и забирай 📚 Базу знаний

Прокачать навыки вёрстки и фронтенда можно в телеграм! В этом канале опытный верстальщик делится структурированными уроками и различными материалами по HTML, CSS, JS, а также советами по заработку на фрилансе. Канал будет полезен: 1. начинающим и опытным верстальщикам 2. программистам 3. веб-дизайнерам Научиться и зарабатывать на верстке: @free_html_lessons