Сообщения

Показаны сообщения с ярлыком "Уровень: простой"

Сумма длинн слов, которые могут быть сформированы из заданного набора букв

Источник: https://leetcode.com/problems/find-words-that-can-be-formed-by-characters/ Дан массив строк words и строка chars . Страка хорошая , если ее можно составить из символов строки chars (каждый символ может быть использован только раз). Вернуть сумму длинн все хороших слов из массива words . Пример 1: Дано: words = ["cat","bt","hat","tree"], chars = "atach" Результат: 6 Пояснение: Мы можем сформировать строки "cat" и "hat", поэтому 3 + 3 = 6. Пример 2: Дано : words = ["hello","world","leetcode"], chars = "welldonehoneyr" Результат : 10 Пояснение : Мы можем сформировать строки "hello" и "world", поэтому 5 + 5 = 10. Ограничения: 1 <= words.length <= 1000 1 <= words[i].length, chars.length <= 100 words[i] и chars состоят из строчных букв английского алфавита   Идея решения Идея достаточно примитивна: нужно попробовать собрать ка...

Комнаты для совещаний

Источник: https://leetcode.com/problems/meeting-rooms/ Дан массив интервалов, в которые проходят совещания intervals, где intervals[i] = [start i , end i ] . Определить, можно ли посетить все интервалы. Пример 1: Дано: intervals = [[0,30],[5,10],[15,20]] Результат: false Пример 2: Дано : intervals = [[7,10],[2,4]] Результат : true Ограничения: 0 <= intervals.length <= 10 4 intervals[i].length == 2 0 <= start i   < end i   <= 10 6 Идея решения Фактически нам нужно отследить, перекрываются ли интервалы. Если перекрываются, что человек может присутствовать на одной встрече, а в это время начнется другая встреча. Два интервала, например [start1, end1] и [start2, end2] перекрываются, когда  min(end1, end2)>max(start1, start2). min(end1, end2) - это завершение первого интервала, max(start1, start2) - это начало второго интервала. И если первый интервал завершается позже начала второго интервала, то у нас имеет место перекрытие интервалов. Без ограни...

Плюс один

Источник: https://leetcode.com/problems/plus-one/ Дан не пустой массив десятичных чисел, которые представляют собой неотрицательное число. Увеличить это число на 1. Старший разряд числа находится в голове массива (в индексе 0)б каждая чейка массива содержит число от 0 до 9. Данное представление числа не имеет в начале нулей, кроме случая, когда массив и представляет собой 0. Пример 1: Дано: digits = [1,2,3] Результат: [1,2,4] Пояснение: Исходный массив кодирует число 123. 123+1=124. Пример 2: Дано : digits = [4,3,2,1] Результат : [4,3,2,2] Пример 3: Дано : digits = [0] Результат : [1] Ограничения: 1 <= digits.length <= 100 0 <= digits[i] <= 9 Идея решения Мы все в школе учились складыватьв столбик, когда к младшему разряду числа добавляется  младший разряд другого числа. Если их сумма меньше 9, то в младший разряд результирующего числа записывается эта сумма. Если же сумма больше 9, то в младший разряд записываем остаток от деления на 10, а целочисленную часть от...

Номер колонки в таблице Excel

Источник задачи: https://leetcode.com/problems/excel-sheet-column-number/ Дана строка columnTitle она представляет собой название колонки в таблице Excel. Рассчитать номер этой колонки. Например: A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ... Пример 1: Дано: columnTitle = "A" Результат: 1 Пример 2: Дано: columnTitle = "AB" Результат: 28 Пример 3: Дано: columnTitle = "ZY" Результат: 701 Пример 4: Дано: columnTitle = "FXSHRXW" Результат: 2147483647 Ограничения: 1 <= columnTitle.length <= 7 columnTitle состоит только из заглавных букв английсокго алфавита. columnTitle находится в диапазоне ["A", "FXSHRXW"] . Имплементация class Solution {    public int titleToNumber(String A) {          int base = 26; // 26 заглавных букв в алфавите         int result = 0; // просматриваем каждый символ строки         for (int i = 0; i < A.length...

Валидные скобки

Источник: https://leetcode.com/problems/valid-parentheses/ Дана строка s , состояшая из символов '(' ,   ')' ,   '{' ,   '}' ,   '[' и ']' . Определеить валидна ли последовательность скобок. Последовательность сокбок валидна: Открытые скобки закрываются тем же типом скобок. Открытые скобки закрываются в корректной последовательности.   Пример 1: Дано: s = "()" Результат: true Пример 2: Дано: s = "()[]{}" Результат : true Пример 3: Дано : s = "(]" Результат : false Пример 4: Дано : s = "([)]" Результат : false Example 5: Дано : s = "{[]}" Результат : true   Ограничения: 1 <= s.length <= 10 4 s состоит только из '()[]{}' . Идея решения Для проверки валидности выражений в скобках удобно использовать стеки. Каждую открывающую скобку бросаем в стек. Как только встречаем закрывающую скобку, смотрим, что у нас в верхушке стека. Там бует открывающая скобка, но нам нужн...

Валидный палиндром с удалением одного символа

Дана непустая строка s , в которой можно удалить 0 или 1 символ. Выяснить, можно ли таким образом получить палиндром. Пример 1: Дано: "aba" Результат: True Пример 2: Дано: "abca" Результат: True Пояснение: Чтобы получился палиндром, можно удалить символ 'c'. Примечания:   Строка состоит из букв нижнего регистра a-z. Максимальная длина строки равна 50000. Идея решения: Палиндром - это строка, которая читается одинаково, как слева направо, так и справа налево. Типовая проверка палиндрома состоит в том, что мы просматриваем символы одновременно слева и справа, два указателя движутся навстречу друг к другу, пока не встретятся. В нашей задаче допускается вариант, что есть какой-то лишний символ. В таком случае, просматривая строку на предмет палиндрома, возникнет ситуация, когда символ справа не равен символу слева. В таком случае нам нужно рассмотреть два варианта: если мы удалим символ справа, то получится палиндром? если мы удалим символ слева, то получи...

Проверить идентичность деревьев

Даны два бинарных дерева, написать функцию, которая проверяет, идентичны ли они. Два бинарных дерева идентичны, если у них одинаковая структура и на узлах в идентичных позициях храняться одинаковые значения. Пример 1: Дано: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] Результат: true Пример 2: Дано : 1 1 / \ 2 2 [1,2], [1,null,2] Результат : false Пример 3: Дано : 1 1 / \ / \ 2 1 1 2 [1,2,1], [1,1,2] Результат : false Идея решения Дерево А идентично дереву Б, если значения в корнях совпадают, а также идентичны левые и правые поддревья, для которых мы можем опять проверить корни и левые/правые поддеревья и так далее. Очевидно, для решения нам понадобится рекурси. Имплементация     public boolean isSameTree(TreeNode p, TreeNode q) {         if (...

Сумма квадратов

Доно неотрицательное целое число c , нужно определить, существуюь ли два целых числа a и b , что a 2  + b 2  = c. Пример 1: Дано: 5 Ответ: True Пояснение: 1 * 1 + 2 * 2 = 5 Пример 2: Дано: 3 Ответ: False Компилируемое решение public class Solution {     public boolean judgeSquareSum(int c) {         for (long a = 0; a * a <= c; a++) {             double b = Math.sqrt(c - a * a);             if (b == (int) b)                 return true;         }         return false;     } } Анализ сложности Сложность по времени :   O\big(\sqrt{c}\log c\big) O ( c ​ lo g c ) . Мы ищем среди \sqrt{c} c ​ значений, чтобы определить a a . Для каж...