Сообщения

Показаны сообщения с ярлыком "Математика"

Целое число вывести словами на английском языке

Источник: https://leetcode.com/problems/integer-to-english-words/ Дано целое число num. Вывести его словами на английском языке. Пример 1: Дано: num = 123 Результат: "One Hundred Twenty Three" Пример 2: Дано : num = 12345 Результат : "Twelve Thousand Three Hundred Forty Five" Пример 3: Дано : num = 1234567 Результат : "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven" Пример 4: Дано : num = 1234567891 Результат : "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One" Ограничения: 0 <= num <= 2 31   - 1 Имплементация class Solution {     public String numberToWords(int num) {         if(num==0) {             return "Zero";         }         return helper(num);     }     public String helper(int n...

Разбиение числа на сумму с максимальным произведнием слагаемых

Источник: https://leetcode.com/problems/integer-break/ Дано целое число n , нужно представить его в виде суммы k положительных целых чисел , где k >= 2 , и произведение этих чисел максимально. Вернуть максимальное произведение. Пример 1: Дано: n = 2 Результат: 1 Пояснение: 2 = 1 + 1, 1 × 1 = 1. Пример 2: Дано: n = 10 Результат: 36 Пояснение: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36. Ограничения: 2 <= n <= 58 Идея решения Допустим мы представили число n в виде суммы, и произведение слагаемых этой суммы обозначим P = p1 * p2 * ...   pk. Рассмотрим некое слагаемое pi uи представим его в виде суммы pi-2 и 2. Если 2 (pi-2) > pi, то у нас получится ещё большее произведение, и это имеет место при pi > 4. Рассмотрим сумму pi-3 и 3, тогда 3*(pi-3) > pi при pi > 4.5. Если pi= 4, то (4-2)*2=4, а (4-3)*3=3. То есть Таким образом, нам нужно разбить исходное число на сумму двоек и троек, чтобы получить максимальное произведение.  В итоге нам нужно представить n = a 3 + ...

Отсортировать массив, трансформированный квадратичной функцией

Изображение
Источник: https://leetcode.com/problems/sort-transformed-array/ Дан отсортированный массив целых чисел nums и три клэффициента a ,   b   and   c . Применить квадратичную фугкцию f(x) = ax 2   + bx + c к каэжлму элементу nums[i]в массивеи вернуть результат в отсортированном порядк . Пример 1: Дано: nums = [-4,-2,2,4], a = 1, b = 3, c = 5 Результат: [3,9,15,33] Пример 2: Дано : nums = [-4,-2,2,4], a = -1, b = 3, c = 5 Результат: [-23,-5,1,7] Идея решения Квадратичную функцию можно переписать: ax^2+bx+c = a(x+p)^2 + q, где p и q можно выразить через a, b, c. Но в переписанной форме мы легко можем представить, где распаложена на декартовой плоскости парабола: она будет смещена по горизонтальной оси на -p, и по вертикальной оси на q. Например: x^2-7x+10=(x-3,5)^2-2,5. То  есть самая нижняя точка параболы смещена вправо на 3,5 и вниз на 2,5, как показано на рисунке:     Если коэффициент a отрицателен, то парабола будет повернута вниз, а экстрем...

Сумма ширин подпоследовательностей

Источник: https://leetcode.com/problems/sum-of-subsequence-widths/ Дан массив целых чисел nums . Для каждой непустой подпоследовательности  seq , назовем шириной разницу между минимальным и максимальным элементами подпоследовательности seq . Вернуть сумму ширин всех подпоследовательностей массива nums .  Поскольку ответ может быть очень большим, вернуть ответ по по модулю 10 9   + 7 . Пример 1: Дано: nums = [2,1,3] Результат: 6 Пояснение: Подпоследовательности массива: [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3]. Их соответствующие ширины: 0, 0, 0, 1, 1, 2, 2. Сумма ширин = 6. Примечания: 1 <= nums.length <= 20000 1 <= nums[i] <= 20000 Идея решения Исходная последовательность чисел не имеет значения, поэтому без ограничения общности мы можем отсортировать массив. Для каждого элемента отсортированного массива A[i] : Существуют i элементов которые меньше его, поэтому существуют 2 ^ i подпоследовательносетй,в которых A[i] - это максимум. Поэтому м...

Плюс один

Источник: 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...

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

Доно неотрицательное целое число 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 . Для каж...