Задача: 911. Online Election
Сложность: medium

Вам даны два целочисленных массива persons и times. На выборах i-й голос был отдан за person[i] в момент времени times[i]. Для каждого запроса в момент времени t найдите человека, который лидировал на выборах в момент времени t. Голоса, отданные в момент времени t, будут учитываться в нашем запросе. В случае равенства голосов побеждает тот, кто проголосовал последним (среди равных кандидатов). Реализация класса TopVotedCandidate: TopVotedCandidate(int[] persons, int[] times) Инициализирует объект с массивами persons и times. int q(int t) Возвращает номер человека, который лидировал на выборах в момент времени t в соответствии с указанными правилами.

Пример:

Input
["TopVotedCandidate", "q", "q", "q", "q", "q", "q"]
[[[0, 1, 1, 0, 0, 1, 0], [0, 5, 10, 15, 20, 25, 30]], [3], [12], [25], [15], [24], [8]]
Output
[null, 0, 1, 1, 0, 0, 1]

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

1⃣Использовать два массива для хранения лиц и времени голосования.

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

3⃣На каждый запрос времени t, найти наибольший индекс времени, который не превышает t, и вернуть лидера на этот момент времени.

😎 Решение:

class TopVotedCandidate {
    private $times;
    private $leaders;

    function __construct($persons, $times) {
        $this->times = $times;
        $this->leaders = [];
        $counts = [];
        $leader = -1;

        foreach ($persons as $person) {
            if (!isset($counts[$person])) {
                $counts[$person] = 0;
            }
            $counts[$person]++;
            if (!isset($counts[$leader]) || $counts[$person] >= $counts[$leader]) {
                $leader = $person;
            }
            $this->leaders[] = $leader;
        }
    }

    function q($t) {
        $left = 0;
        $right = count($this->times) - 1;
        while ($left < $right) {
            $mid = intdiv($left + $right + 1, 2);
            if ($this->times[$mid] <= $t) {
                $left = $mid;
            } else {
                $right = $mid - 1;
            }
        }
        return $this->leaders[$left];
    }
}

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

Задача: 664. Strange Printer
Сложность: hard

Существует странный принтер с двумя особыми свойствами:

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

Пример:

Input: s = "aaabbb"
Output: 2
Explanation: Print "aaa" first and then print "bbb".

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

1⃣Инициализация и подсчет:
Создайте двумерный массив dp, где dp[i][j] представляет минимальное количество ходов для печати подстроки s[i:j+1].

2⃣Динамическое программирование:
Если s[i] == s[j], тогда dp[i][j] = dp[i][j-1], так как последний символ совпадает с предыдущим.
В противном случае, dp[i][j] = min(dp[i][k] + dp[k+1][j]) для всех i <= k < j, чтобы найти минимальное количество ходов.


3⃣Возврат результата:
Возвратите dp[0][n-1], где n - длина строки s, что представляет минимальное количество ходов для печати всей строки.

😎 Решение:

class Solution {
    function strangePrinter($s) {
        $n = strlen($s);
        $dp = array_fill(0, $n, array_fill(0, $n, 0));
        
        for ($length = 1; $length <= $n; $length++) {
            for ($i = 0; $i <= $n - $length; $i++) {
                $j = $i + $length - 1;
                $dp[$i][$j] = ($i === $j) ? 1 : $dp[$i][$j - 1] + 1;
                for ($k = $i; $k < $j; $k++) {
                    if ($s[$k] === $s[$j]) {
                        $dp[$i][$j] = min($dp[$i][$j], $dp[$i][$k] + ($k + 1 <= $j - 1 ? $dp[$k + 1][$j - 1] : 0));
                    }
                }
            }
        }
        return $dp[0][$n - 1];
    }
}

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

Задача: 899. Orderly Queue
Сложность: hard

Вам дана строка s и целое число k. Вы можете выбрать одну из первых k букв s и добавить ее в конец строки. Верните лексикографически наименьшую строку, которая может получиться после применения указанного шага за любое количество ходов.

Пример:

Input: s = "cba", k = 1
Output: "acb"

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

1⃣Если k равно 1, найти лексикографически наименьшую строку путем вращения строки и поиска минимального варианта.

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

3⃣Вернуть результат.

😎 Решение:

function orderlyQueue($s, $k) {
    if ($k == 1) {
        $minString = $s;
        for ($i = 1; $i < strlen($s); $i++) {
            $rotated = substr($s, $i) . substr($s, 0, $i);
            if ($rotated < $minString) {
                $minString = $rotated;
            }
        }
        return $minString;
    } else {
        $sArray = str_split($s);
        sort($sArray);
        return implode('', $sArray);
    }
}

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