Задача: 463. Island Perimeter
Сложность: easy

Дан двумерный массив grid, где:
1 — суша
0 — вода
Нужно найти периметр острова (все стороны, соприкасающиеся с водой или краем карты).

Пример:

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]  
Output: 16

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

1⃣Пройти через каждую ячейку сетки и, когда вы находитесь в ячейке с значением 1 (ячейка суши), проверить окружающие (СВЕРХУ, СПРАВА, СНИЗУ, СЛЕВА) ячейки.

2⃣Ячейка суши без каких-либо окружающих ячеек суши будет иметь периметр 4. Вычесть 1 за каждую окружающую ячейку суши.

3⃣Когда вы находитесь в ячейке с значением 0 (ячейка воды), ничего не делать. Просто перейти к следующей ячейке.

😎 Решение:

class Solution {
    public function islandPerimeter($grid) {
        $rows = count($grid);
        $cols = count($grid[0]);
        
        $result = 0;
        
        for ($r = 0; $r < $rows; $r++) {
            for ($c = 0; $c < $cols; $c++) {
                if ($grid[$r][$c] == 1) {
                    $up = ($r == 0) ? 0 : $grid[$r-1][$c];
                    $left = ($c == 0) ? 0 : $grid[$r][$c-1];
                    $down = ($r == $rows-1) ? 0 : $grid[$r+1][$c];
                    $right = ($c == $cols-1) ? 0 : $grid[$r][$c+1];
                    
                    $result += 4 - ($up + $left + $right + $down);
                }
            }
        }
        
        return $result;
    }
}

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

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

Если задан массив nums целых чисел, верните длину самой длинной арифметической подпоследовательности в nums. Примечание: Подпоследовательность - это массив, который может быть получен из другого массива путем удаления некоторых или ни одного элемента без изменения порядка оставшихся элементов. Последовательность seq является арифметической, если seq[i + 1] - seq[i] имеют одинаковое значение (для 0 <= i < seq.length - 1).

Пример:

Input: nums = [3,6,9,12]
Output: 4

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

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

2⃣Заполнение массива dp:
Пройдитесь по каждому элементу массива nums.
Для каждого элемента nums[j] (где j идет от 0 до i-1), вычислите разность d = nums[i] - nums[j].
Обновите dp[i][d] на основе значения dp[j][d].

3⃣Поиск максимальной длины:
Пройдите по массиву dp и найдите максимальное значение среди всех значений dp[i][d].

😎 Решение:

class Solution {
    function longestArithSeqLength($nums) {
        if (empty($nums)) return 0;
        
        $dp = array_fill(0, count($nums), []);
        $maxLength = 0;
        
        for ($i = 0; $i < count($nums); $i++) {
            for ($j = 0; $j < $i; $j++) {
                $diff = $nums[$i] - $nums[$j];
                if (isset($dp[$j][$diff])) {
                    $dp[$i][$diff] = $dp[$j][$diff] + 1;
                } else {
                    $dp[$i][$diff] = 2;
                }
                $maxLength = max($maxLength, $dp[$i][$diff]);
            }
        }
        
        return $maxLength;
    }
}

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

Задача: 1470. Shuffle the Array
Сложность: easy

Дан массив nums, состоящий из 2n элементов в форме [x1, x2, ..., xn, y1, y2, ..., yn].

Верните массив в форме [x1, y1, x2, y2, ..., xn, yn].

Пример:

Input: nums = [2,5,1,3,4,7], n = 3
Output: [2,3,5,4,1,7] 
Explanation: Since x1=2, x2=5, x3=1, y1=3, y2=4, y3=7 then the answer is [2,3,5,4,1,7].

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

1⃣Создайте массив result размером 2 * n.

2⃣Итеративно пройдите по массиву nums от 0 до n - 1:
Сохраните элемент xi+1, то есть nums[i], в индекс 2 * i массива result.
Сохраните элемент yi+1, то есть nums[i + n], в индекс 2 * i + 1 массива result.

3⃣Верните массив result.

😎 Решение:

class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $n
     * @return Integer[]
     */
    function shuffle($nums, $n) {
        $result = array_fill(0, 2 * $n, 0);
        for ($i = 0; $i < $n; ++$i) {
            $result[2 * $i] = $nums[$i];
            $result[2 * $i + 1] = $nums[$n + $i];
        }
        return $result;
    }
}

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

Задача: 1140. Stone Game II
Сложность: medium

Алиса и Боб продолжают свои игры с кучами камней. Есть несколько куч, расположенных в ряд, и в каждой куче положительное количество камней piles[i]. Цель игры - закончить с наибольшим количеством камней.
Алиса и Боб ходят по очереди, начиная с Алисы. Изначально M = 1.
В свой ход каждый игрок может взять все камни из первых X оставшихся куч, где 1 <= X <= 2M. Затем, мы устанавливаем M = max(M, X).
Игра продолжается до тех пор, пока все камни не будут взяты.
Предполагая, что Алиса и Боб играют оптимально, верните максимальное количество камней, которые может получить Алиса.

Пример:

Input: piles = [2,7,9,4,4]
Output: 10
Explanation:  If Alice takes one pile at the beginning, Bob takes two piles, then Alice takes 2 piles again. 
Alice can get 2 + 4 + 4 = 10 piles in total. If Alice takes two piles at the beginning, then Bob can take all three piles left. 
In this case, Alice get 2 + 7 = 9 piles in total. So we return 10 since it's larger. 

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

1⃣Создать рекурсивную функцию f, которая принимает три параметра: p (игрок), i (индекс текущей кучи),
и m (максимальное количество куч, которые можно взять за ход).
Если i равен длине массива кучи, вернуть 0 (базовый случай рекурсии). Если значение уже вычислено ранее (dp[p][i][m] != -1), вернуть его.

2⃣ Инициализировать переменную s как количество камней, взятых текущим игроком за ход, и переменную res для хранения результата текущего состояния.
Если ход Боба, инициализировать res большим числом, так как Боб хочет минимизировать результат.
Если ход Алисы, инициализировать res маленьким числом, так как Алиса хочет максимизировать результат.

3⃣Итеративно обновлять значение res в зависимости от того, чей ход, и обновлять значения в dp[p][i][m]. В конце вернуть res.

😎 Решение:

class Solution {

    function stoneGameII($piles) {
        $n = count($piles);
        $dp = array_fill(0, 2, array_fill(0, $n + 1, array_fill(0, $n + 1, -1)));

        function f($p, $i, $m, &$dp, &$piles) {
            if ($i == count($piles)) return 0;
            if ($dp[$p][$i][$m] != -1) return $dp[$p][$i][$m];
            $res = $p == 1 ? 1000000 : -1;
            $s = 0;
            for ($x = 1; $x <= min(2 * $m, count($piles) - $i); $x++) {
                $s += $piles[$i + $x - 1];
                if ($p == 0) {
                    $res = max($res, $s + f(1, $i + $x, max($m, $x), $dp, $piles));
                } else {
                    $res = min($res, f(0, $i + $x, max($m, $x), $dp, $piles));
                }
            }
            return $dp[$p][$i][$m] = $res;
        }

        return f(0, 0, 1, $dp, $piles);
    }
}

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