Сообщения

Дизайн рекомендательной системы по поисковому слову

Изображение
 Источник: https://leetcode.com/problems/search-suggestions-system   Дан строковый массив products и сттрока searchWord . Сделайте дизайн системы, которая рекомендует не более 3 продуктов из массива products после введения каждой следующей буквы из строки searchWord . Названия рекомендованных продуктов должны иметь тот же префикс, что и введеный префикс слова searchWord . Если названий с общим префиксом существует более, чем 3, то вывести 3 лексикографически минимальных названия. Пример 1: Дано: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse" Результат: [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]] Пояснение: продукты отсортированные в лексикографическом порядке = ["mobile"...

Сумма минимальных значений подмассивов

Источник: https://leetcode.com/problems/sum-of-subarray-minimums/ Дан массив целых числе arr, надо найти сумму минимумов min(b) , где b - это непрерывный подмассив массива arr . Поскольку ответ может быть очень большим, то его надо вернуть по модулю 10 9   + 7 . Пример 1: Дано: arr = [3,1,2,4] Результат: 17 Объяснение: Непрерывные подмассивы: [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. Минимумы в каждом подмассиве: 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Суммв: 17. Пример 2: Дано : arr = [11,81,94,43,3] Результат : 444 Ограничения: 1 <= arr.length <= 3 * 10 4 1 <= arr[i] <= 3 * 10 4 Идея решения Монотонный стек - это стек, в котором элементы идут в возрастающем порядке. Часто в алгоритмах идею монотонного стека реализуют следующим кодом (С++): for ( int i = 0 ; i < A.size(); i++){ while (!in_stk.empty() && in_stk.top() > A[i]){ in_stk.pop(); } in_stk.push(A[i]); } Для чего полезен монотонный стек? (1) найти предыдущи...

Паттерн посещения сайтов с наивысшим рангом

Источник: https://leetcode.com/problems/analyze-user-website-visit-pattern Даны два строковых массива: username и website , и целочисленный массив timestamp . Все массивы имеют одинаковую длинну, и кортеж [username[i], website[i], timestamp[i]] обозначает, что пользователь username[i] посетил вебсайт website[i] в момент timestamp[i] . Паттерн - это список трех вебсайтов (не обязательно различных). Например,   ["home", "away", "love"] ,   ["leetcode", "love", "leetcode"] , и ["luffy", "luffy", "luffy"] - это три паттерна. Ранг паттерна - это число пользователей, посетивших все вебсайты в паттерне в том порядке, в котором они появляются в паттерне . Например, если паттерн ["home", "away", "love"] , его ранг - это число пользователей x таких, что x посетил "home" затем "away" и затем "love" . Аналогично, если паттерн ...