Задача: 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);
    }
}

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

Задача: 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;
};

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

Задача: 918. Maximum Sum Circular Subarray
Сложность: medium

Если задан круговой целочисленный массив nums длины n, верните максимально возможную сумму непустого подмассива nums. Круговой массив означает, что конец массива соединяется с его началом. Формально, следующий элемент nums[i] равен nums[(i + 1) % n], а предыдущий элемент nums[i] равен nums[(i - 1 + n) % n]. Подмассив может включать каждый элемент фиксированного буфера nums не более одного раза. Формально, для подмассива nums[i], nums[i + 1], ..., nums[j] не существует i <= k1, k2 <= j, при этом k1 % n == k2 % n.

Пример:

Input: nums = [1,-2,3,-2]
Output: 3

👨‍💻 Алгоритм:

1⃣Найти стандартную максимальную сумму подмассива с помощью алгоритма Кадане.

2⃣Найти минимальную сумму подмассива с помощью алгоритма Кадане и вычесть ее из общей суммы массива.

3⃣Вернуть максимум между стандартной максимальной суммой подмассива и общей суммой массива минус минимальную сумму подмассива, если результат не равен 0 (чтобы учесть случай, когда все числа отрицательные).

😎 Решение:

var maxSubarraySumCircular = function(nums) {
    const kadane = (arr) => {
        let currentSum = arr[0], maxSum = arr[0];
        for (let i = 1; i < arr.length; i++) {
            currentSum = Math.max(arr[i], currentSum + arr[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    };

    const maxKadane = kadane(nums);
    const totalSum = nums.reduce((a, b) => a + b, 0);
    const minKadane = kadane(nums.map(num => -num));

    return Math.max(maxKadane, totalSum + minKadane === 0 ? maxKadane : totalSum + minKadane);
};

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

Задача: 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;
};

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

Задача: 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;
}

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

Задача: 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;
};

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

Задача: 204. Count Primes
Сложность: medium

Дано целое число n, верните количество простых чисел, которые строго меньше n.

Пример:

Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

👨‍💻 Алгоритм:

1️⃣Создайте список последовательных целых чисел от 2 до n: (2, 3, 4, ..., n). Пусть p будет переменной, используемой во внешнем цикле, проходящем от 2 до n. Изначально p равно 2, самому маленькому простому числу.

2️⃣Перечислите кратные числа p, считая с шагом p от pp до n и отметьте их в списке (это будут pp, pp + p, pp + 2*p и т.д.; само число p должно быть простым). Найдите наименьшее число в списке, большее p, которое не отмечено. Если такого числа нет, остановитесь. В противном случае, пусть p теперь равно этому новому числу (следующее простое) и повторите шаг 2.

3️⃣Когда алгоритм завершится, все оставшиеся числа, которые не отмечены, являются простыми.

😎 Решение:

class Solution {
    countPrimes(n) {
        if (n <= 2) {
            return 0;
        }

        let numbers = new Array(n).fill(true);
        for (let p = 2; p <= Math.sqrt(n); ++p) {
            if (numbers[p]) {
                for (let j = p * p; j < n; j += p) {
                    numbers[j] = false;
                }
            }
        }

        let numberOfPrimes = 0;
        for (let i = 2; i < n; i++) {
            if (numbers[i]) {
                ++numberOfPrimes;
            }
        }

        return numberOfPrimes;
    }
}

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

Задача: 245. Shortest Word Distance II
Сложность: medium

Дан массив строк wordsDict и две строки word1 и word2, которые уже существуют в массиве. Верните наименьшее расстояние между вхождениями этих двух слов в списке.
Обратите внимание, что word1 и word2 могут быть одинаковыми. Гарантируется, что они представляют собой два отдельных слова в списке.

Пример:

Input: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
Output: 1

👨‍💻 Алгоритм:

1️⃣Переберите список wordsDict и сохраните индексы слова word1 в список indices1 и индексы слова word2 в список indices2. Инициализируйте переменную shortestDistance = INT_MAX.

2️⃣Переберите индексы в списке indices1 и для каждого индекса найдите верхнюю границу в списке indices2, используя бинарный поиск, и сохраните этот индекс в переменную x. Рассмотрите индексы indices2[x] и indices2[x - 1], обновляя shortestDistance, если индексы не совпадают.

3️⃣Верните значение переменной shortestDistance.

😎 Решение:

class Solution {
    shortestWordDistance(wordsDict, word1, word2) {
        const indices1 = [];
        const indices2 = [];
        wordsDict.forEach((word, i) => {
            if (word === word1) {
                indices1.push(i);
            }
            if (word === word2) {
                indices2.push(i);
            }
        });

        let shortestDistance = Infinity;
        indices1.forEach(index => {
            const x = indices2.findIndex(i => i > index);
            if (x !== -1) {
                shortestDistance = Math.min(shortestDistance, indices2[x] - index);
            }
            if (x > 0 && indices2[x - 1] !== index) {
                shortestDistance = Math.min(shortestDistance, index - indices2[x - 1]);
            }
        });
        return shortestDistance;
    }
}

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

Задача: 300. Longest Increasing Subsequence
Сложность: medium

Дан массив целых чисел nums, верните длину самой длинной строго возрастающей подпоследовательности.

Пример:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

👨‍💻 Алгоритм:

1⃣Инициализируйте массив dp длиной nums.length, все элементы которого равны 1. dp[i] представляет длину самой длинной возрастающей подпоследовательности, которая заканчивается элементом с индексом i.


2⃣Итерируйтесь от i = 1 до i = nums.length - 1. В каждой итерации используйте второй цикл for для итерации от j = 0 до j = i - 1 (все элементы перед i). Для каждого элемента перед i, проверьте, меньше ли этот элемент, чем nums[i]. Если да, установите dp[i] = max(dp[i], dp[j] + 1).


3⃣Верните максимальное значение из dp.

😎 Решение:

function lengthOfLIS(nums) {
  if (nums.length === 0) {
    return 0;
  }

  const dp = Array(nums.length).fill(1);

  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  return Math.max(...dp);
}

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

Задача: 1207. Unique Number of Occurrences
Сложность: easy

Дан массив целых чисел arr. Верните true, если количество вхождений каждого значения в массиве уникально, или false в противном случае.

Пример:

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

👨‍💻 Алгоритм:

1⃣Сохраните частоты элементов массива arr в хэш-таблице freq.

2⃣Итерируйтесь по хэш-таблице freq и вставьте частоты всех уникальных элементов массива arr в хэш-набор freqSet.

3⃣Верните true, если размер хэш-набора freqSet равен размеру хэш-таблицы freq, иначе верните false.

😎 Решение:

var uniqueOccurrences = function(arr) {
    let freq = new Map();
    for (let num of arr) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }
    let freqSet = new Set(freq.values());
    return freq.size === freqSet.size;
};

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

Задача: 672. Bulb Switcher II
Сложность: medium

Есть комната с n лампочками, пронумерованными от 1 до n, которые изначально все включены, и четыре кнопки на стене. Каждая из четырех кнопок имеет разную функциональность:
Кнопка 1: Переключает состояние всех лампочек.
Кнопка 2: Переключает состояние всех лампочек с четными номерами (т.е. 2, 4, ...).
Кнопка 3: Переключает состояние всех лампочек с нечетными номерами (т.е. 1, 3, ...).
Кнопка 4: Переключает состояние всех лампочек с номером j = 3k + 1, где k = 0, 1, 2, ... (т.е. 1, 4, 7, 10, ...).
Необходимо сделать ровно presses нажатий кнопок. Для каждого нажатия можно выбрать любую из четырех кнопок для нажатия.
Даны два целых числа n и presses, вернуть количество различных возможных состояний после выполнения всех presses нажатий кнопок.

Пример:

Input: n = 1, presses = 1
Output: 2
Explanation: Status can be:
- [off] by pressing button 1
- [on] by pressing button 2

👨‍💻 Алгоритм:

1⃣Рассчитаем возможные множества остатков: то есть какие множества c_i = f_i (mod 2) возможны.

2⃣Так как c_i ≡ f_i и c_i ≤ f_i, если ∑f_i ≠ ∑c_i, или если ∑f_i < ∑c_i, это невозможно. В противном случае это возможно простым построением: выполните операции, указанные c_i, затем выполните операцию номер 1 с четным числом оставшихся операций.

3⃣Для каждого возможного множества остатков симулируем и запоминаем, как будут выглядеть первые 6 лампочек, сохраняя это в структуре Set. В конце возвращаем размер этого множества.

😎 Решение:

var flipLights = function(n, m) {
    let seen = new Set();
    n = Math.min(n, 6);
    let shift = Math.max(0, 6 - n);
    for (let cand = 0; cand < 16; ++cand) {
        let bcount = cand.toString(2).split('1').length - 1;
        if (bcount % 2 == m % 2 && bcount <= m) {
            let lights = 0;
            if ((cand >> 0) & 1) lights ^= 0b111111 >> shift;
            if ((cand >> 1) & 1) lights ^= 0b010101 >> shift;
            if ((cand >> 2) & 1) lights ^= 0b101010 >> shift;
            if ((cand >> 3) & 1) lights ^= 0b100100 >> shift;
            seen.add(lights);
        }
    }
    return seen.size;
}

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