Задача: 786. K-th Smallest Prime Fraction
Сложность: medium

Вам дан отсортированный массив целых чисел arr, содержащий 1 и простые числа, где все элементы массива arr уникальны. Также дано целое число k.

Для каждого i и j, где 0 <= i < j < arr.length, мы рассматриваем дробь arr[i] / arr[j].

Верните k-ую наименьшую дробь из рассмотренных. Верните ответ в виде массива из двух целых чисел размера 2, где answer[0] == arr[i] и answer[1] == arr[j].

Пример:

Input: arr = [1,2,3,5], k = 3
Output: [2,5]
Explanation: The fractions to be considered in sorted order are:
1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.
The third fraction is 2/5.

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

1⃣Инициализируйте пустую приоритетную очередь pq для хранения пар дробей и соответствующих им индексов. Итеративно пройдите по входному массиву arr, используя переменную цикла i. Для каждого элемента arr[i] вычислите дробь, образованную делением его на наибольший элемент в массиве (arr[arr.size() - 1]). Поместите пару, состоящую из отрицательного значения дроби (-1.0 * arr[i] / arr[arr.size() - 1]) и соответствующих индексов (i для числителя и arr.size() - 1 для знаменателя), в приоритетную очередь pq. Приоритетная очередь pq теперь содержит все дроби, образованные делением каждого элемента на наибольший элемент в массиве, отсортированные в порядке возрастания значений дробей.

2⃣Повторите следующие шаги k - 1 раз: удалите верхний элемент (наименьшую дробь) из приоритетной очереди pq и сохраните его индексы в переменной cur. Уменьшите индекс знаменателя (cur[1]--). Вычислите новую дробь, образованную делением числителя в cur[0] на уменьшенный знаменатель (arr[cur[1]]). Поместите новое значение дроби (-1.0 * arr[cur[0]] / arr[cur[1]]) и соответствующие индексы (cur[0] для числителя и cur[1] для знаменателя) в приоритетную очередь pq. После k - 1 итераций верхний элемент приоритетной очереди pq будет k-й наименьшей дробью.

3⃣Извлеките индексы числителя и знаменателя из верхнего элемента приоритетной очереди и сохраните их в result. Верните массив, содержащий значения числителя (arr[result[0]]) и знаменателя (arr[result[1]]), соответствующие k-й наименьшей дроби.

😎 Решение:

class Solution {
    function kthSmallestPrimeFraction($arr, $k) {
        $pq = new SplPriorityQueue();
        $pq->setExtractFlags(SplPriorityQueue::EXTR_BOTH);

        for ($i = 0; $i < count($arr) - 1; $i++) {
            $pq->insert([$i, count($arr) - 1], -($arr[$i] / $arr[count($arr) - 1]));
        }

        for ($i = 0; $i < $k - 1; $i++) {
            $cur = $pq->extract();
            list($numeratorIndex, $denominatorIndex) = $cur['data'];
            if ($denominatorIndex - 1 > $numeratorIndex) {
                $pq->insert([$numeratorIndex, $denominatorIndex - 1], -($arr[$numeratorIndex] / $arr[$denominatorIndex - 1]));
            }
        }

        $result = $pq->extract()['data'];
        return [$arr[$result[0]], $arr[$result[1]]];
    }
}

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

Задача: 378. Kth Smallest Element in a Sorted Matrix
Сложность: medium

Дана матрица размером n x n, где каждая строка и каждый столбец отсортированы в порядке возрастания. Верните k-й наименьший элемент в матрице.
Заметьте, что это k-й наименьший элемент в отсортированном порядке, а не k-й уникальный элемент.
Вы должны найти решение с использованием памяти лучше, чем O(n²).

Пример:

Input: matrix = [[-5]], k = 1
Output: -5

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

1⃣Инициализировать мин-кучу H. В нашем решении мы будем рассматривать каждую строку как отдельный список. Поскольку столбцы также отсортированы, мы можем рассматривать каждый столбец как отдельный список.

2⃣Взять первые элементы из min(N, K) строк, где N представляет количество строк, и добавить каждый из этих элементов в кучу. Важно знать, к какой строке и столбцу принадлежит элемент, чтобы в дальнейшем перемещаться по соответствующему списку.

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

😎 Решение:

class Solution {
    private function dfs($word, $length, &$visited, $dictionary) {
        if ($length == strlen($word)) {
            return true;
        }
        if ($visited[$length]) {
            return false;
        }
        $visited[$length] = true;
        for ($i = strlen($word) - ($length == 0 ? 1 : 0); $i > $length; $i--) {
            if (isset($dictionary[substr($word, $length, $i - $length)]) &&
                $this->dfs($word, $i, $visited, $dictionary)) {
                return true;
            }
        }
        return false;
    }

    function findAllConcatenatedWordsInADict($words) {
        $dictionary = array_flip($words);
        $answer = [];
        foreach ($words as $word) {
            $visited = array_fill(0, strlen($word), false);
            if ($this->dfs($word, 0, $visited, $dictionary)) {
                $answer[] = $word;
            }
        }
        return $answer;
    }
}

$solution = new Solution();
$words = ["cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat"];
print_r($solution->findAllConcatenatedWordsInADict($words));

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

Задача: 268. Missing Number
Сложность: easy

Дан массив nums, содержащий n различных чисел в диапазоне [0, n]. Верните единственное число в этом диапазоне, которого нет в массиве.

Пример:

Input: nums = [3,0,1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

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

1⃣Сначала отсортируйте массив nums.

2⃣Проверьте особые случаи: убедитесь, что число 0 находится в начале массива, а число n — в конце.

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

😎 Решение:

class Solution {
    function missingNumber($nums) {
        sort($nums);
        if ($nums[count($nums) - 1] != count($nums)) {
            return count($nums);
        } else if ($nums[0] != 0) {
            return 0;
        }
        for ($i = 1; $i < count($nums); $i++) {
            $expectedNum = $nums[$i - 1] + 1;
            if ($nums[$i] != $expectedNum) {
                return $expectedNum;
            }
        }
        return -1;
    }
}

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

Задача: 418. Sentence Screen Fitting
Сложность: medium

Если задан экран rows x cols и предложение, представленное в виде списка строк, верните количество раз, которое данное предложение может быть помещено на экран. Порядок слов в предложении должен оставаться неизменным, и слово не может быть разбито на две строки. Два последовательных слова в строке должны разделяться одним пробелом.

Пример:

Input: sentence = ["hello","world"], rows = 2, cols = 8
Output: 1

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

1⃣Преобразуйте предложение в единую строку с пробелами между словами и пробелом в конце.

2⃣Инициализируйте переменную для отслеживания текущей позиции в строке предложения. Для каждой строки экрана добавляйте количество символов, равное числу столбцов.

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

😎 Решение:

function wordsTyping($sentence, $rows, $cols) {
    $sentenceStr = implode(" ", $sentence) . " ";
    $length = strlen($sentenceStr);
    $pos = 0;
    
    for ($i = 0; $i < $rows; $i++) {
        $pos += $cols;
        if ($sentenceStr[$pos % $length] == " ") {
            $pos++;
        } else {
            while ($pos > 0 && $sentenceStr[($pos - 1) % $length] != " ") {
                $pos--;
            }
        }
    }
    
    return intdiv($pos, $length);
}

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