Задача: 337. House Robber III
Сложность: medium

Вор снова нашел себе новое место для краж. В этом районе есть только один вход, который называется корнем.
Кроме корня, каждый дом имеет только один родительский дом. После осмотра, умный вор понял, что все дома в этом месте образуют бинарное дерево. Полиция будет автоматически уведомлена, если два дома, напрямую связанные между собой, будут ограблены в одну ночь.
Дано корневое дерево бинарного дерева, верните максимальную сумму денег, которую вор может украсть, не уведомляя полицию.

Пример:

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

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

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

2⃣Рекурсивное исследование дерева:
В функции helper вызывайте её рекурсивно для левого и правого поддеревьев текущего узла.
Если грабить текущий узел, то нельзя грабить его потомков, поэтому сумма будет равна значению текущего узла плюс максимальные суммы для случаев, когда потомки не грабятся.
Если не грабить текущий узел, то можно свободно выбирать, грабить потомков или нет, поэтому сумма будет равна максимальной сумме из двух вариантов для каждого потомка.

3⃣Возврат результата:
В основной функции rob вызовите helper для корня дерева и верните максимальное значение из двух элементов массива, возвращенного функцией helper.

😎 Решение:

class TreeNode {
    public $val;
    public $left;
    public $right;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class Solution {
    function rob($root) {
        $answer = $this->helper($root);
        return max($answer[0], $answer[1]);
    }
    
    function helper($node) {
        if ($node === null) {
            return [0, 0];
        }
        
        $left = $this->helper($node->left);
        $right = $this->helper($node->right);
        
        $rob = $node->val + $left[1] + $right[1];
        $notRob = max($left[0], $left[1]) + max($right[0], $right[1]);
        
        return [$rob, $notRob];
    }
}

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

Задача: 377. Combination Sum IV
Сложность: medium

Дан массив различных целых чисел nums и целое число target. Верните количество возможных комбинаций, которые в сумме дают target.
Тестовые случаи сгенерированы так, что ответ помещается в 32-битное целое число.

Пример:

Input: nums = [9], target = 3
Output: 0

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

1⃣В этом подходе мы начнем со стратегии сверху вниз, которая, пожалуй, более интуитивна. Как следует из названия, стратегия сверху вниз начинается с исходных данных, и затем мы рекурсивно уменьшаем входные данные до меньшего масштаба, пока не достигнем уровней, которые больше невозможно разбить.

2⃣Из-за рекурсивной природы формулы мы можем напрямую перевести формулу в рекурсивную функцию.

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

😎 Решение:

class Solution {
    private $memo = [];

    public function combinationSum4($nums, $target) {
        return $this->combs($nums, $target);
    }

    private function combs($nums, $remain) {
        if ($remain == 0) {
            return 1;
        }
        if (isset($this->memo[$remain])) {
            return $this->memo[$remain];
        }

        $result = 0;
        foreach ($nums as $num) {
            if ($remain - $num >= 0) {
                $result += $this->combs($nums, $remain - $num);
            }
        }
        $this->memo[$remain] = $result;
        return $result;
    }
}

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

Задача: 461. Hamming Distance
Сложность: easy

Расстояние Хэмминга между двумя целыми числами — это количество позиций, в которых соответствующие биты различны.
Даны два целых числа x и y, верните расстояние Хэмминга между ними.

Пример:

Input: x = 3, y = 1
Output: 1

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

1⃣Во-первых, стоит упомянуть, что в большинстве (или, по крайней мере, во многих) языков программирования есть встроенные функции для подсчета битов, установленных в 1. Если вам нужно решить такую задачу в реальном проекте, то лучше использовать эти функции, чем изобретать велосипед.

2⃣Однако, поскольку это задача на LeetCode, использование встроенных функций можно сравнить с "реализацией LinkedList с использованием LinkedList". Поэтому рассмотрим также несколько интересных ручных алгоритмов для подсчета битов.

3⃣Пошаговый подсчет битов:
Выполните побитовое XOR между x и y.
Инициализируйте счетчик bitCount = 0.
Пока число не равно нулю:
Если текущий бит равен 1, увеличьте bitCount.
Сдвиньте число вправо на один бит.
Возвращайте bitCount.

😎 Решение:

class Solution {
    public function hammingDistance($x, $y) {
        return substr_count(decbin($x ^ $y), '1');
    }
}

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

Задача: 848. Shifting Letters
Сложность: medium

Вам дана строка s из строчных букв английского алфавита и целочисленный массив shifts такой же длины.

Назовем shift() буквы следующей буквой в алфавите (с переходом так, что 'z' становится 'a').
Например, shift('a') = 'b', shift('t') = 'u', и shift('z') = 'a'.
Теперь для каждого shifts[i] = x мы хотим сдвинуть первые i + 1 букв строки s на x раз.

Верните итоговую строку после применения всех таких сдвигов к s.

Пример:

Input: s = "abc", shifts = [3,5,9]
Output: "rpl"
Explanation: We start with "abc".
After shifting the first 1 letters of s by 3, we have "dbc".
After shifting the first 2 letters of s by 5, we have "igc".
After shifting the first 3 letters of s by 9, we have "rpl", the answer.

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

1⃣Вычислите общее количество сдвигов для всех символов строки, используя массив shifts.

2⃣Пройдите по строке s и примените вычисленные сдвиги к каждому символу, начиная с первого и уменьшая количество сдвигов на текущем шаге.

3⃣Постройте и верните итоговую строку после всех сдвигов.

😎 Решение:

class Solution {
    /**
     * @param String $s
     * @param Integer[] $shifts
     * @return String
     */
    function shiftingLetters($s, $shifts) {
        $totalShifts = array_sum($shifts) % 26;
        $sArray = str_split($s);
        
        for ($i = 0; $i < count($sArray); $i++) {
            $newCharValue = (ord($sArray[$i]) - ord('a') + $totalShifts) % 26;
            $sArray[$i] = chr($newCharValue + ord('a'));
            $totalShifts = ($totalShifts - $shifts[$i] + 26) % 26;
        }
        
        return implode('', $sArray);
    }
}

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

Задача: 1482. Minimum Number of Days to Make m Bouquets
Сложность: medium

Вам дан массив целых чисел bloomDay, целое число m и целое число k.

Вам нужно сделать m букетов. Для создания букета необходимо использовать k соседних цветов из сада.
Сад состоит из n цветов, i-й цветок расцветет на bloomDay[i] и затем может быть использован ровно в одном букете.

Верните минимальное количество дней, которое нужно подождать, чтобы можно было сделать m букетов из сада. Если сделать m букетов невозможно, верните -1.

Пример:

Input: bloomDay = [1,10,3,10,2], m = 3, k = 1
Output: 3
Explanation: Let us see what happened in the first three days. x means flower bloomed and _ means flower did not bloom in the garden.
We need 3 bouquets each should contain 1 flower.
After day 1: [x, _, _, _, _]   // we can only make one bouquet.
After day 2: [x, _, _, _, x]   // we can only make two bouquets.
After day 3: [x, _, x, _, x]   // we can make 3 bouquets. The answer is 3.

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

1⃣Инициализация:
Инициализируйте start как 0 и end как максимальное значение в массиве bloomDay.
Введите вспомогательную функцию getNumOfBouquets для подсчета количества букетов, которые можно сделать на определенный день.

2⃣Поиск минимального числа дней:
Выполняйте бинарный поиск, пока start меньше или равен end:
- рассчитайте mid как среднее значение между start и end.
- используйте getNumOfBouquets, чтобы определить, сколько букетов можно сделать на mid день.
- если количество букетов больше или равно m, сохраните mid как возможное решение и переместите end влево.
- иначе переместите start вправо.

3⃣Возвращение результата:
Верните найденное минимальное количество дней или -1, если сделать m букетов невозможно.

😎 Решение:

class Solution {
    private function getNumOfBouquets($bloomDay, $mid, $k) {
        $numOfBouquets = 0;
        $count = 0;
        foreach ($bloomDay as $day) {
            if ($day <= $mid) {
                $count++;
            } else {
                $count = 0;
            }
            if ($count == $k) {
                $numOfBouquets++;
                $count = 0;
            }
        }
        return $numOfBouquets;
    }
    
    function minDays($bloomDay, $m, $k) {
        if (count($bloomDay) < $m * $k) return -1;
        $start = 0;
        $end = max($bloomDay);
        $minDays = -1;
        while ($start <= $end) {
            $mid = (int)(($start + $end) / 2);
            if ($this->getNumOfBouquets($bloomDay, $mid, $k) >= $m) {
                $minDays = $mid;
                $end = $mid - 1;
            } else {
                $start = $mid + 1;
            }
        }
        return $minDays;
    }
}

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

🚨 60 минут до финала

Через час мы закроем краудфандинг easyoffer 2.0
Это последний шанс вписаться в самые выгодные условия.

👉 https://planeta.ru/campaigns/easyoffer

Задача: 629. K Inverse Pairs Array
Сложность: hard

Для целочисленного массива nums инверсная пара - это пара целых чисел [i, j], где 0 <= i < j < nums.length и nums[i] > nums[j]. Учитывая два целых числа n и k, верните количество различных массивов, состоящих из чисел от 1 до n, в которых существует ровно k инверсных пар. Поскольку ответ может быть огромным, верните его по модулю 109 + 7.

Пример:

Input: n = 3, k = 0
Output: 1

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

1⃣Инициализация
Создайте двумерный массив dp размером [n+1][k+1] и установите начальное значение dp[0][0] = 1. Остальные значения установите в 0.

2⃣Заполнение DP-таблицы
Используйте два вложенных цикла для заполнения таблицы DP. Внешний цикл перебирает длину массива i от 1 до n, а внутренний цикл перебирает количество инверсий j от 0 до k. Если j == 0, то dp[i][j] = 1. В противном случае обновляйте dp[i][j] с учетом всех возможных позиций вставки нового элемента в массив длины i-1.

3⃣Возвращение результата
Результатом будет значение dp[n][k].

😎 Решение:

function kInversePairs($n, $k) {
    $MOD = 1000000007;
    $dp = array_fill(0, $n + 1, array_fill(0, $k + 1, 0));
    $dp[0][0] = 1;

    for ($i = 1; $i <= $n; $i++) {
        $dp[$i][0] = 1;
        for ($j = 1; $j <= $k; $j++) {
            $dp[$i][$j] = ($dp[$i][$j - 1] + $dp[$i - 1][$j]) % $MOD;
            if ($j >= $i) {
                $dp[$i][$j] = ($dp[$i][$j] - $dp[$i - 1][$j - $i] + $MOD) % $MOD;
            }
        }
    }

    return $dp[$n][$k];
}

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

Задача: 925. Long Pressed Name
Сложность: easy

Ваш друг набирает на клавиатуре свое имя. Иногда, при наборе символа c, клавиша может быть долго нажата, и символ будет набран 1 или более раз. Вы исследуете набранные символы клавиатуры. Верните True, если возможно, что это было имя вашего друга, при этом некоторые символы (возможно, ни один) не были долго нажаты.

Пример:

Input: name = "alex", typed = "aaleex"
Output: true

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

1⃣Инициализировать два указателя i и j для строки имени и набранной строки соответственно.

2⃣Пройти по набранной строке:
Если символы имени и набранной строки совпадают, сдвинуть оба указателя.
Если символы не совпадают, проверить, является ли текущий символ набранной строки повторением предыдущего символа. Если да, сдвинуть указатель набранной строки.
Если символ не совпадает и не является повторением предыдущего символа, вернуть False.
После завершения цикла проверить, что все символы имени были обработаны.

3⃣Вернуть True, если все символы имени были обработаны, иначе False.

😎 Решение:

function isLongPressedName($name, $typed) {
    $i = 0;
    $j = 0;
    while ($j < strlen($typed)) {
        if ($i < strlen($name) && $name[$i] == $typed[$j]) {
            $i++;
        } elseif ($j == 0 || $typed[$j] != $typed[$j - 1]) {
            return false;
        }
        $j++;
    }
    return $i == strlen($name);
}

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

Задача: 489. Robot Room Cleaner
Сложность: hard

Вы управляете роботом в комнате, представленной бинарной сеткой m x n, где 0 — стена, а 1 — пустая ячейка.
Робот начинает в неизвестном месте, гарантированно пустом. У вас нет доступа к сетке, но вы можете перемещать робота через предоставленный API Robot.
Роботу нужно очистить всю комнату (т.е. все пустые ячейки). Он может двигаться вперед, поворачивать налево или направо на 90 градусов.
Если робот наталкивается на стену, его датчик препятствия обнаруживает это, и он остается на текущей ячейке.

Разработайте алгоритм для очистки всей комнаты, используя следующие API:

interface Robot {
  // возвращает true, если следующая ячейка открыта и робот перемещается в эту ячейку.
  // возвращает false, если следующая ячейка является препятствием и робот остается на текущей ячейке.
  boolean move();

  // Робот останется на той же ячейке после вызова turnLeft/turnRight.
  // Каждый поворот составляет 90 градусов.
  void turnLeft();
  void turnRight();

  // Очистить текущую ячейку.
  void clean();
}

Пример:

Input: room = [[1,1,1,1,1,0,1,1],[1,1,1,1,1,0,1,1],[1,0,1,1,1,1,1,1],[0,0,0,1,0,0,0,0],[1,1,1,1,1,1,1,1]], row = 1, col = 3
Output: Robot cleaned all rooms.
Explanation: All grids in the room are marked by either 0 or 1.
0 means the cell is blocked, while 1 means the cell is accessible.
The robot initially starts at the position of row=1, col=3.
From the top left corner, its position is one row below and three columns right.

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

1⃣Пометьте текущую ячейку как посещенную и очистите её.

2⃣Исследуйте четыре направления (вверх, вправо, вниз, влево) последовательно, двигаясь и очищая новые ячейки, если возможно.

3⃣Если движение невозможно (стена или посещенная ячейка), поверните направо и попробуйте снова, возвращаясь назад, если необходимо.

😎 Решение:

class Solution {
    private $robot;
    private $visited;
    private $directions;

    public function __construct() {
        $this->visited = [];
        $this->directions = [[-1, 0], [0, 1], [1, 0], [0, -1]];
    }

    private function goBack() {
        $this->robot->turnRight();
        $this->robot->turnRight();
        $this->robot->move();
        $this->robot->turnRight();
        $this->robot->turnRight();
    }

    private function backtrack($row, $col, $d) {
        $this->visited["$row,$col"] = true;
        $this->robot->clean();
        for ($i = 0; $i < 4; $i++) {
            $newD = ($d + $i) % 4;
            $newRow = $row + $this->directions[$newD][0];
            $newCol = $col + $this->directions[$newD][1];
            if (!isset($this->visited["$newRow,$newCol"]) && $this->robot->move()) {
                $this->backtrack($newRow, $newCol, $newD);
                $this->goBack();
            }
            $this->robot->turnRight();
        }
    }

    public function cleanRoom($robot) {
        $this->robot = $robot;
        $this->backtrack(0, 0, 0);
    }
}

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

Задача: 668. Kth Smallest Number in Multiplication Table
Сложность: hard

Почти каждый использовал таблицу умножения. Таблица умножения размером m x n - это целочисленная матрица mat, где mat[i][j] == i * j (индексация начинается с 1).

Даны три целых числа m, n и k. Верните k-й наименьший элемент в таблице умножения размером m x n.

Пример:

Input: m = 3, n = 3, k = 5
Output: 3
Explanation: The 5th smallest number is 3.

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

1⃣Установка границ поиска:
Установите нижнюю границу left равной 1 и верхнюю границу right равной m * n.

2⃣Бинарный поиск:
Используйте бинарный поиск, чтобы найти k-й наименьший элемент.
Для каждого среднего значения mid, посчитайте количество элементов в таблице умножения, которые меньше или равны mid.

3⃣Проверка количества элементов:
Если количество элементов меньше k, увеличьте нижнюю границу (left).
Если количество элементов больше или равно k, уменьшите верхнюю границу (right).

😎 Решение:

class Solution {
    function findKthNumber($m, $n, $k) {
        $left = 1;
        $right = $m * $n;
        
        while ($left < $right) {
            $mid = intdiv($left + $right, 2);
            if ($this->countLessEqual($m, $n, $mid) < $k) {
                $left = $mid + 1;
            } else {
                $right = $mid;
            }
        }
        
        return $left;
    }
    
    private function countLessEqual($m, $n, $x) {
        $count = 0;
        for ($i = 1; $i <= $m; $i++) {
            $count += min(intdiv($x, $i), $n);
        }
        return $count;
    }
}

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

Задача: 116. Populating Next Right Pointers in Each Node
Сложность: medium

Вам дано идеальное бинарное дерево, где все листья находятся на одном уровне, и у каждого родителя есть два детей. Бинарное дерево имеет следующее определение:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Заполните каждый указатель next так, чтобы он указывал на следующий правый узел. Если следующего правого узла нет, указатель next должен быть установлен в NULL.

Изначально все указатели next установлены в NULL.

Пример:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

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

1⃣Инициализируйте очередь Q, которую мы будем использовать во время обхода. Существует несколько способов реализации обхода в ширину, особенно когда речь идет о определении уровня конкретного узла. Можно добавлять в очередь пару (узел, уровень), и каждый раз, когда добавляются дети узла, мы добавляем (node.left, parent_level + 1) и (node.right, parent_level + 1). Этот подход не будет очень эффективен для нашего алгоритма, так как нам нужны все узлы на одном уровне, и для этого потребуется еще одна структура данных.

2⃣Более эффективный с точки зрения памяти способ разделения узлов одного уровня заключается в использовании некоторой разграничительной метки между уровнями. Обычно мы вставляем в очередь элемент NULL, который отмечает конец предыдущего уровня и начало следующего. Это отличный подход, но он все равно потребует некоторого количества памяти, пропорционально количеству уровней в дереве.

3⃣Подход, который мы будем использовать здесь, будет иметь структуру вложенных циклов, чтобы обойти необходимость указателя NULL. По сути, на каждом шаге мы записываем размер очереди, который всегда соответствует всем узлам на определенном уровне. Как только мы узнаем этот размер, мы обрабатываем только это количество элементов и не более. К моменту, когда мы закончим обработку заданного количества элементов, в очереди будут все узлы следующего уровня. Вот псевдокод для этого:

while (!Q.empty())
{
    size = Q.size()
    for i in range 0..size
    {
        node = Q.pop()
        Q.push(node.left)
        Q.push(node.right)
    }
}

Мы начинаем с добавления корня дерева в очередь. Поскольку на уровне 0 есть только один узел, нам не нужно устанавливать какие-либо соединения, и мы можем перейти к циклу while.

😎 Решение:

class Node {
    public $val;
    public $left = null;
    public $right = null;
    public $next = null;

    public function __construct($val) {
        $this->val = $val;
    }
}

class Solution {
    public function connect($root) {
        if ($root === null) {
            return $root;
        }

        $queue = new SplQueue();
        $queue->enqueue($root);

        while (!$queue->isEmpty()) {
            $size = $queue->count();
            for ($i = 0; $i < $size; $i++) {
                $node = $queue->dequeue();
                if ($i < $size - 1) {
                    $node->next = $queue->top();
                }

                if ($node->left !== null) {
                    $queue->enqueue($node->left);
                }
                if ($node->right !== null) {
                    $queue->enqueue($node->right);
                }
            }
        }

        return $root;
    }
}

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

Задача: 1002. Find Common Characters
Сложность: easy

Если задан массив строк words, верните массив всех символов, которые встречаются во всех строках внутри слов (включая дубликаты). Вы можете вернуть ответ в любом порядке.

Пример:

Input: words = ["bella","label","roller"]
Output: ["e","l","l"]

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

1⃣Инициализация частотного массива:
Создайте массив для хранения минимальной частоты каждого символа, который будет встречаться во всех словах.

2⃣Обработка каждого слова:
Для каждого слова создайте временный массив для хранения частоты каждого символа в этом слове.
Обновите основной частотный массив, сравнивая его с временным массивом и сохраняя минимальные частоты каждого символа.

3⃣Формирование результата:
Создайте результирующий массив, добавляя каждый символ столько раз, сколько его минимальная частота.

😎 Решение:

class Solution {
    function commonChars($words) {
        $minFreq = array_fill(0, 26, PHP_INT_MAX);
        
        foreach ($words as $word) {
            $freq = array_fill(0, 26, 0);
            foreach (str_split($word) as $char) {
                $freq[ord($char) - ord('a')]++;
            }
            for ($i = 0; $i < 26; $i++) {
                $minFreq[$i] = min($minFreq[$i], $freq[$i]);
            }
        }
        
        $result = [];
        for ($i = 0; $i < 26; $i++) {
            for ($j = 0; $j < $minFreq[$i]; $j++) {
                $result[] = chr($i + ord('a'));
            }
        }
        return $result;
    }
}

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

Задача: 1279. Traffic Light Controlled Intersection
Сложность: easy

Здесь есть пересечение двух дорог. Первая дорога - это дорога A, по которой автомобили движутся с севера на юг в направлении 1 и с юга на север в направлении 2. Вторая дорога - дорога B, по которой машины едут с запада на восток в направлении 3 и с востока на запад в направлении 4. На каждой дороге перед перекрестком есть светофор. Зеленый означает, что автомобили могут пересекать перекресток в обоих направлениях. Красный означает, что автомобили в обоих направлениях не могут пересекать перекресток и должны ждать, пока загорится зеленый свет. Светофор не может гореть зеленым одновременно на обеих дорогах. Это значит, что когда на дороге А горит зеленый свет, на дороге Б он красный, а когда на дороге Б горит зеленый свет, на дороге А он красный.
Изначально на дороге A горит зеленый сигнал светофора, а на дороге B - красный. Когда на одной дороге горит зеленый свет, все автомобили могут пересекать перекресток в обоих направлениях, пока на другой дороге не загорится зеленый.Два автомобиля, движущиеся по разным дорогам, не должны пересекать перекресток одновременно. Разработайте систему управления светофором на этом перекрестке без тупиков. Реализуйте функцию void carArrived(carId, roadId, direction, turnGreen, crossCar), где: carId - идентификатор автомобиля, который приехал. roadId - идентификатор дороги, по которой едет автомобиль.
direction - направление движения автомобиля. turnGreen - функция, которую можно вызвать, чтобы переключить светофор на зеленый свет на текущей дороге. crossCar - функция, которую можно вызвать, чтобы позволить текущему автомобилю пересечь перекресток. Ваш ответ считается правильным, если он позволяет избежать тупика на перекрестке.Переключение светофора на зеленый свет на дороге, где он уже был зеленым, считается неправильным ответом.

Пример:

Input: cars = [1,2,3,4,5], directions = [2,4,3,3,1], arrivalTimes = [10,20,30,40,40]
Output: [
"Car 1 Has Passed Road A In Direction 2",    // Traffic light on road A is green, car 1 can cross the intersection.
"Traffic Light On Road B Is Green",          // Car 2 requests green light for road B.
"Car 2 Has Passed Road B In Direction 4",    // Car 2 crosses as the light is green on road B now.
"Car 3 Has Passed Road B In Direction 3",    // Car 3 crosses as the light is green on road B now.
"Traffic Light On Road A Is Green",          // Car 5 requests green light for road A.
"Car 5 Has Passed Road A In Direction 1",    // Car 5 crosses as the light is green on road A now.
"Traffic Light On Road B Is Green",          // Car 4 requests green light for road B. Car 4 blocked until car 5 crosses and then traffic light is green on road B.
"Car 4 Has Passed Road B In Direction 3"     // Car 4 crosses as the light is green on road B now.
]

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

1⃣Если на дороге, по которой едет автомобиль, уже зеленый свет, вызываем функцию crossCar.

2⃣Если на дороге, по которой едет автомобиль, красный свет, вызываем функцию turnGreen, чтобы переключить свет на зеленый, и затем вызываем функцию crossCar.

3⃣Обеспечиваем, что функции turnGreen и crossCar вызываются атомарно для предотвращения гонок и тупиков.

😎 Решение:

class TrafficLight {
    private $greenRoad = 1;
    private $lock;

    public function __construct() {
        $this->lock = new \stdClass();
    }

    public function carArrived($carId, $roadId, $direction, $turnGreen, $crossCar) {
        synchronized($this->lock, function() use ($roadId, $turnGreen, $crossCar) {
            if ($this->greenRoad !== $roadId) {
                $turnGreen();
                $this->greenRoad = $roadId;
            }
            $crossCar();
        });
    }
}

function synchronized($lock, $callback) {
    $fp = fopen($lock, "r+");
    if (flock($fp, LOCK_EX)) {
        try {
            $callback();
        } finally {
            flock($fp, LOCK_UN);
        }
    }
    fclose($fp);
}

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

Задача: 83. Remove Duplicates from Sorted List
Сложность: easy

Дана голова отсортированного связного списка. Удалите все дубликаты таким образом, чтобы каждый элемент появлялся только один раз. Верните также отсортированный связный список.

Пример:

Input: head = [1,1,2]
Output: [1,2]

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

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

2⃣Если узел является дубликатом, мы изменяем указатель next текущего узла так, чтобы он пропускал следующий узел и напрямую указывал на узел, следующий за следующим.

3⃣Это позволяет исключить дубликаты из списка, продвигаясь вперёд по списку и корректируя связи между узлами для сохранения только уникальных элементов.

😎 Решение:

class ListNode {
    public $val = 0;
    public $next = null;

    public function __construct($val = 0, $next = null) {
        $this->val = $val;
        $this->next = $next;
    }
}

function deleteDuplicates($head) {
    $current = $head;
    while ($current !== null && $current->next !== null) {
        if ($current->next->val === $current->val) {
            $current->next = $current->next->next;
        } else {
            $current = $current->next;
        }
    }
    return $head;
}

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