Присылайте свои решения в комментариях! Таймкоды: 00:00 Вступление. 00:15 Уровень сложности задачи на Leetcode. 00:31 Условия задачи. 02:05 Разбор решения. 08:53 Запуск кода. 10:10 Сложность получившегося алгоритма по времени и по памяти. 10:46 Что запланировано на следующий выпуск.
Задача интересная, особенно мне понравилось решение из видео. function isPalindrome(x) { if (x < 0) return false; if (x < 10) return true; // Сначала должна идти эта строка, чтобы при x === 0 сработал return true if (x % 10 === 0) return false; let reverse = 0; while (x > reverse) { reverse *= 10; reverse += x % 10; x = Math.trunc(x / 10); } return x === reverse || x === Math.trunc(reverse / 10); } Мне интересен расчет сложности алгоритма в данном случае. Когда мы считаем сложность алгоритма для функций, которые принимают строку или массив, то исходим из числа элементов в них. В задаче для одного и того же решения если считать n === кол-ву цифр, сложность алгоритма будет O (n), а если принимать n === самому числу, то сложность будет O (lg n). Поэтому возник вопрос: для функций, которые принимают на вход числа принято считать n равным самому числу? Или it's up to us и допустимы оба варианта?
@@frontendscience спасибо, классно, что ограничений нет здесь :) Ведь как лучше записывать зависит от того, сколько полезной информации несет в себе тот или иной вариант записи.
@@EvilYou Интересное решение, до тысячи вроде работает... А какой смысл в остатке от деления на 10 с остатка от деления на 100, если можно сразу взять остаток от деления на 10? 🤔
Я в видео как раз рассказал, что метод из первого видео (про строку) универсальный и подойдет и для чисел. Но если мы знаем, что у нас числовой палиндром, то можно использовать более оптимальный алгоритм (работающий только с числами).
Эта несложная задачка поможет мне решить задачу Кому интересно: Reverse Number is a number which is the same when reversed. For example, the first 20 Reverse Numbers are: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101 TASK: You need to return the nth reverse number. (Assume that reverse numbers start from 0 as shown in the example.) NOTES: 1 < n
ничего себе сравнение. приведённая тобой задача значительно сложнее. сейчас часа четыре на неё убил. но таки да, есть решение условно за O(1), если заметить, что в последовательности чисел-палиндромов, если выкинуть число 0, сначала идёт 9 однозначных чисел, потом 9 двузначных, потом 90 трёхзначных, потом 90 четырёхзначных, потом 900 пятизначных, потом 900 шестизначных, и так далее.
Спасибо! Интерестное решение, но разве если число будет 0, то функция не будет возвращать false? Ведь 0%10 === 0. Надо еще поставить проверку на 0 перед проверкой x%10 === 0.
Не смотря видео, такой вариант прокатит? const isPalindromeNumber = function (x) { return Number(x.toString().split('').reverse().join('')) === x }; кстати неплохо оставлять сслку на саму задачу в оригинале, если не трудно
Конкретно в этом случае линейная сложность хуже, чем константная. Рекомендую посмотреть видео про то, как расчитывать сложность алгоритма: ua-cam.com/video/Fu4BzQNN0Qs/v-deo.html
@@ruff3d приведение к строке, создание массива, реверс, джоин- это всё O(n) и O(n) space, сравнение строк просто O(n). Где вы увидели O(1) ? Может я что-то не так понимаю
@@NinjaNoobful n - указывает на количество итераций. В моем примере их нет. Возможно под капотом движок сделает какие-нить цыклы, но это явно оптимизировано
Спасибо за разбор!) Подскажите, а когда есть массив к примеру [‘радар’, ‘вор’, ‘доход’, ‘потом’] Как в этом случае быть? Как найти среди них палиндромы? Может я пропустила какое-то ваше видео((
Нужно использовать функцию проверяющую на палиндром и отфильтровать только палиндромы в массиве. arr.filter((str) => return isPalindrome(str) ) Видео где мы разбираем такую функцию вот: ua-cam.com/video/eXjUz2Kuuw4/v-deo.html
Я часто смотрю ваши видео, действительно вы хорошо разбираете задачки, правда мне не всегда понятно так как многое ещё не проходила, но всё равно очень интересно, не находила канал лучше чем ваш😉 Возник вопрос, в продолжении к этому, а как с помощью цикла новичку можно решить?) Посмотрела все видео про палиндромы, но для меня пока сложновато(
Вот так у меня вышло function numPalindrome(n) { if (n < 0) return false if (n % 10 === 0) return false let i = n let rev = 0 while (i > 0) { rev *= 10 rev += i % 10 i = Math.floor(i/10) } return rev == n }
js считает, что 0 % 10 === 0 следовательно порядок должен быть такой if (num < 0) return false; if (num < 10) return true; if (num % 10 === 0) return false;
Можно было. Но я в видео говорил что надо решить задачу без конвертации в строку так как есть ограничение по памяти. 1:14 нужно решить задачу за O(1) по памяти
вот так вот решила function isNumPalindrom (num) { if(num < 0 || num % 10 === 0) return false; if(num < 10) return true; let rev = ''; let cur = num; while (num > rev) { rev += cur % 10 cur = Math.trunc(cur / 10) } return rev == num; }
@@fusted4630 Остаток от деления нуля на 10 равен нулю, поэтому сработет второй if и функция вернет false. Если поменять второй и третий if местами, тогда ноль возвращал бы true 🤔
Присылайте свои решения в комментариях!
Таймкоды:
00:00 Вступление.
00:15 Уровень сложности задачи на Leetcode.
00:31 Условия задачи.
02:05 Разбор решения.
08:53 Запуск кода.
10:10 Сложность получившегося алгоритма по времени и по памяти.
10:46 Что запланировано на следующий выпуск.
Спасибо. Прям очень интересно алгоритмы узнавать!
Нужна еще одна проверка : при x = 0 остаток от деления тоже будет 0, функция вернет false
Задача интересная, особенно мне понравилось решение из видео.
function isPalindrome(x) {
if (x < 0) return false;
if (x < 10) return true; // Сначала должна идти эта строка, чтобы при x === 0 сработал return true
if (x % 10 === 0) return false;
let reverse = 0;
while (x > reverse) {
reverse *= 10;
reverse += x % 10;
x = Math.trunc(x / 10);
}
return x === reverse || x === Math.trunc(reverse / 10);
}
Мне интересен расчет сложности алгоритма в данном случае. Когда мы считаем сложность алгоритма для функций, которые принимают строку или массив, то исходим из числа элементов в них.
В задаче для одного и того же решения если считать n === кол-ву цифр, сложность алгоритма будет O (n), а если принимать n === самому числу, то сложность будет O (lg n).
Поэтому возник вопрос: для функций, которые принимают на вход числа принято считать n равным самому числу? Или it's up to us и допустимы оба варианта?
тут реально up to us - просто когда пишется сложность то нужна ремарка типа: O(n) - где n - это длина числа (кол-во цифр в числе)
@@frontendscience спасибо, классно, что ограничений нет здесь :)
Ведь как лучше записывать зависит от того, сколько полезной информации несет в себе тот или иной вариант записи.
Сам додумался только до этого:
function isPalindromeNumber(n) {
if (n < 0) return false;
if (n < 10) return true;
if (Math.trunc(n / 10) === n % 10) return true; // < 100
if (Math.trunc(n / 100) === (n % 100) % 10) return true; // < 1000
}
@@EvilYou Интересное решение, до тысячи вроде работает... А какой смысл в остатке от деления на 10 с остатка от деления на 100, если можно сразу взять остаток от деления на 10? 🤔
@@SerzhNesteruk вообще да, это лишнее условие
Спасибо! Было интересно
Рад, что было полезно
А есть решение, чтобы сразу и строку, и число определяло на палиндром?
Я в видео как раз рассказал, что метод из первого видео (про строку) универсальный и подойдет и для чисел. Но если мы знаем, что у нас числовой палиндром, то можно использовать более оптимальный алгоритм (работающий только с числами).
@@frontendscienceСпасибо
Эта несложная задачка поможет мне решить задачу
Кому интересно:
Reverse Number is a number which is the same when reversed.
For example, the first 20 Reverse Numbers are:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33, 44, 55, 66, 77, 88, 99, 101
TASK:
You need to return the nth reverse number. (Assume that reverse numbers start from 0 as shown in the example.)
NOTES:
1 < n
ничего себе сравнение. приведённая тобой задача значительно сложнее. сейчас часа четыре на неё убил. но таки да, есть решение условно за O(1), если заметить, что в последовательности чисел-палиндромов, если выкинуть число 0, сначала идёт 9 однозначных чисел, потом 9 двузначных, потом 90 трёхзначных, потом 90 четырёхзначных, потом 900 пятизначных, потом 900 шестизначных, и так далее.
Спасибо! Интерестное решение, но разве если число будет 0, то функция не будет возвращать false? Ведь 0%10 === 0. Надо еще поставить проверку на 0 перед проверкой x%10 === 0.
Нет не будет проблемы - у нас же есть на строку выше проверка if (x < 10) return true
@@frontendscience эта проверка на строку ниже, и до неё проверка не дойдет, потому что x%10 === 0 вернет false раньше
@@ОлегБордуляк-й1ю хммм. В codepen код верный, в видео перепутан порядок строк.
@@frontendscience Классный канал) Интерестные решения) много нового для себя получаю) спасибо)
@@ОлегБордуляк-й1ю Рад слышать! )
Не смотря видео, такой вариант прокатит?
const isPalindromeNumber = function (x) {
return Number(x.toString().split('').reverse().join('')) === x
};
кстати неплохо оставлять сслку на саму задачу в оригинале, если не трудно
аа все, понял в чем загвоздка, нужно сначала видео смотреть))
@@vty4261 ага ;)
Хорошая идея - будем прикладывать ссылку.
function isPalindromeNumber(num) {
if (num
function isPalindromeNumber(num) {
if (num
Хорошие варианты как для палиндрома любого типа. но при этом у нас линейная сложность по памяти выходит.
@@frontendscience линейная сложность по памяти, это плохо?(извините, ещё не сильно разбираюсь)
Конкретно в этом случае линейная сложность хуже, чем константная.
Рекомендую посмотреть видео про то, как расчитывать сложность алгоритма: ua-cam.com/video/Fu4BzQNN0Qs/v-deo.html
function pol(n) {
const s = n.toString();
return Array.from(s).reverse().join('') === s
}
Благодарю за решение, но в условии как раз сказано что такой вариант не подойдет - надо более оптимальный. Хотя этот универсальный
@@frontendscience в каком плане более оптимальный? Как по мне это О(1).
А понял, ну если это констрейн то ок
@@ruff3d приведение к строке, создание массива, реверс, джоин- это всё O(n) и O(n) space, сравнение строк просто O(n). Где вы увидели O(1) ? Может я что-то не так понимаю
@@NinjaNoobful n - указывает на количество итераций. В моем примере их нет. Возможно под капотом движок сделает какие-нить цыклы, но это явно оптимизировано
Спасибо, крутой цикл видео, очень полезный. Хотя я работаю фронтом уже 1.5 года, но некоторые задачи сразу моему пониманию не даются)
Все придет с практикой, потом как орешки щелкать будете))
Спасибо за разбор!)
Подскажите, а когда есть массив к примеру [‘радар’, ‘вор’, ‘доход’, ‘потом’]
Как в этом случае быть? Как найти среди них палиндромы?
Может я пропустила какое-то ваше видео((
Нужно использовать функцию проверяющую на палиндром и отфильтровать только палиндромы в массиве.
arr.filter((str) => return isPalindrome(str) )
Видео где мы разбираем такую функцию вот: ua-cam.com/video/eXjUz2Kuuw4/v-deo.html
@@frontendscience огромное Вам спасибо!;)))
Я часто смотрю ваши видео, действительно вы хорошо разбираете задачки, правда мне не всегда понятно так как многое ещё не проходила, но всё равно очень интересно, не находила канал лучше чем ваш😉
Возник вопрос, в продолжении к этому, а как с помощью цикла новичку можно решить?) Посмотрела все видео про палиндромы, но для меня пока сложновато(
Благодарю рад слышать!
Все прийдет с практикой.
Вот решение: codepen.io/puzankov/pen/vYxqzQG?editors=0011
@@frontendscience теперь понятно, спасибо, что ответили😊
А почему if ( x < 10 ) равно true. Это же наоборот плохо и false? не
число состоящие из одной цифры принято считать также палиндромом
Вот так вроде работает)
const isPalindrom = (num) => {
let rev = 0;
if (num % 10 === 0 && num !== 0) {
return false;
}
while (rev < num) {
rev = Number(`${rev}` + (num % 10));
if (rev < num) {
num = Math.trunc(num / 10);
}
}
return rev === num;
};
Вот так у меня вышло
function numPalindrome(n) {
if (n < 0) return false
if (n % 10 === 0) return false
let i = n
let rev = 0
while (i > 0) {
rev *= 10
rev += i % 10
i = Math.floor(i/10)
}
return rev == n
}
js считает, что 0 % 10 === 0
следовательно порядок должен быть такой
if (num < 0) return false;
if (num < 10) return true;
if (num % 10 === 0) return false;
Благодарю за уточнение! Действительно, чтобы при 0 правильно сработало, надо поменять порядок! Подправил в codpene!
Это задача easy level сразу видно
А можно ведь было вот так ещё сделать?
const isPalindrom = (x) => x.toString() === x.toString().split('').reverse().join('')
Можно было. Но я в видео говорил что надо решить задачу без конвертации в строку так как есть ограничение по памяти. 1:14 нужно решить задачу за O(1) по памяти
@@frontendscience Ой, тогда извиняюсь, я походу этот момент прослушал
вот так вот решила
function isNumPalindrom (num) {
if(num < 0 || num % 10 === 0) return false;
if(num < 10) return true;
let rev = '';
let cur = num;
while (num > rev) {
rev += cur % 10
cur = Math.trunc(cur / 10)
}
return rev == num;
}
Класс! Благодарю за решение!
Не правильный код, 0 выдаст false, хотя 0 палиндром
почему 0 выдаст false?
@@fusted4630 Остаток от деления нуля на 10 равен нулю, поэтому сработет второй if и функция вернет false.
Если поменять второй и третий if местами, тогда ноль возвращал бы true 🤔
Дякую
function isPolindrome (num) {
let result = num.toString().split('').reverse().join('')
if(num == +result) {
return true
}
return false
}
console.log(isPolindrome(-12))
как вам такое решение
@@thismusic2581так условие, что нельзя переводить в строку
const isPalindromeNumber = num => {
if (
!Number.isInteger(num)
|| num < 0
|| num % 10 === 0 && num !== 0
) {
return false;
}
let rev = 0;
while (num > rev) {
const digit = num % 10;
rev = rev * 10 + digit;
if (num > rev) {
num = (num - digit) / 10;
}
}
return num === rev;
};
Никто не найдёт решение с константой по памяти
function reverse(a){
var rev=function(n){
let r = 0
while(n != 0){
r = r * 10 + n % 10
n = Math.floor(n / 10)
}
return r
}
return a
Nice )