Задача: 984. String Without AAA or BBB
Сложность: medium

Даны два целых числа a и b, верните любую строку s, такую что:

s имеет длину a + b и содержит ровно a букв 'a' и ровно b букв 'b'.
Подстрока 'aaa' не встречается в s.
Подстрока 'bbb' не встречается в s.

Пример:

Input: a = 4, b = 1
Output: "aabaa"

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

1⃣Инициализация переменных:
Завести пустую строку s и переменные a_count и b_count для отслеживания оставшихся 'a' и 'b' соответственно.

2⃣Создание строки:
Добавляйте символы в строку s, попеременно добавляя 'a' и 'b', чтобы избегать подстрок 'aaa' и 'bbb'.
Если в строке подряд уже два символа 'a' и осталось ещё 'b', добавьте 'b' и наоборот.
Если оба символа возможны для добавления, выбирайте тот, которого осталось больше.

3⃣Добавление оставшихся символов:
После основной логики добавления символов, добавьте оставшиеся 'a' или 'b' в конец строки, если они остались.

😎 Решение:

class Solution {
    function strWithout3a3b($a, $b) {
        $result = [];
        
        while ($a > 0 || $b > 0) {
            if (count($result) >= 2 && $result[count($result) - 1] == $result[count($result) - 2]) {
                if ($result[count($result) - 1] == 'a') {
                    $result[] = 'b';
                    $b--;
                } else {
                    $result[] = 'a';
                    $a--;
                }
            } else {
                if ($a >= $b) {
                    $result[] = 'a';
                    $a--;
                } else {
                    $result[] = 'b';
                    $b--;
                }
            }
        }
        
        return implode('', $result);
    }
}

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

Задача: 342. Power of Four
Сложность: easy

Дано целое число n. Верните true, если оно является степенью числа четыре. В противном случае верните false.

Целое число n является степенью числа четыре, если существует целое число x такое, что n == 4^x.

Пример:

Input: n = 16
Output: true

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

1⃣Проверка неотрицательности:
Убедитесь, что n больше нуля, так как степени числа четыре всегда положительны.

2⃣Проверка логарифмом:
Используйте логарифм для проверки, является ли число степенью четырех. Число n является степенью четырех, если логарифм n по основанию 4 является целым числом.

3⃣Проверка побитовым оператором:
Число является степенью четырех, если оно является степенью двух (только один бит установлен) и количество нулей после этого бита четно.

😎 Решение:

class Solution {
    function isPowerOfFour($n) {
        if ($n <= 0) return false;
        $log_n_base_4 = log($n) / log(4);
        return $log_n_base_4 == floor($log_n_base_4);
    }
}

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

Задача: 764. Largest Plus Sign
Сложность: medium

Вам дано целое число n. У вас есть бинарная сетка размером n x n, в которой все значения изначально равны 1, за исключением некоторых индексов, указанных в массиве mines. Элемент массива mines с индексом i определяется как mines[i] = [xi, yi], где grid[xi][yi] == 0.
Верните порядок самого большого крестообразного знака из 1, выровненного по осям, который содержится в сетке. Если такого знака нет, верните 0.
Крестообразный знак из 1 порядка k имеет некоторый центр grid[r][c] == 1, а также четыре луча длиной k - 1, идущих вверх, вниз, влево и вправо, состоящие из 1. Обратите внимание, что за пределами лучей креста могут быть 0 или 1, проверяется только соответствующая область крестообразного знака на наличие 1.

Пример:

Input: n = 5, mines = [[4,2]]
Output: 2
Explanation: In the above grid, the largest plus sign can only be of order 2. One of them is shown.

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

1⃣Создайте сетку размером n x n, заполненную единицами. Затем используйте массив mines, чтобы установить значения нулей в соответствующих ячейках сетки.

2⃣Для каждой ячейки в сетке создайте четыре дополнительных сетки: left, right, up и down, которые будут хранить длину непрерывных единиц, простирающихся в соответствующем направлении от каждой ячейки.

3⃣Пройдите по всей сетке и для каждой ячейки определите минимальную длину луча среди четырех направлений. Эта минимальная длина будет определять порядок крестообразного знака с центром в данной ячейке. Обновите максимальный порядок крестообразного знака и верните его после завершения обхода всей сетки. Если такого знака нет, верните 0.

😎 Решение:

class Solution {
    function orderOfLargestPlusSign($N, $mines) {
        $banned = [];
        foreach ($mines as $mine) {
            $banned[$mine[0] * $N + $mine[1]] = true;
        }
        
        $ans = 0;
        for ($r = 0; $r < $N; ++$r) {
            for ($c = 0; $c < $N; ++$c) {
                $k = 0;
                while ($k <= $r && $r < $N - $k && $k <= $c && $c < $N - $k &&
                      !isset($banned[($r - $k) * $N + $c]) &&
                      !isset($banned[($r + $k) * $N + $c]) &&
                      !isset($banned[$r * $N + $c - $k]) &&
                      !isset($banned[$r * $N + $c + $k])) {
                    $k++;
                }
                $ans = max($ans, $k);
            }
        }
        return $ans;
    }
}

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