Советы и хитрости для простых алгоритмов
Хотя моя программа подошла к концу, я знаю, что только начинаю свой путь. Я очень кинестетический и визуальный ученик, поэтому настоящая проблема начинается с алгоритмов обучения. Я знаю, что практика поможет, и я надеюсь научиться некоторым образцам решения проблем, но борьба реальна!
Чтобы закрепить некоторые знания, я собираюсь пройти через простой алгоритм решения - надеюсь, оставлю это здесь, поскольку я продолжаю разработку, чтобы я мог оглянуться назад.
Вот проблема, которую я попытался решить сегодня, вместе с примечаниями и советами (в основном для себя).
Https://leetcode.com/problems/reverse-integer/
Вот подробности:
Для 32-битного целого числа со знаком обратные цифры целого числа.
Примечание:
Предположим, мы имеем дело со средой, которая может хранить только целые числа в диапазоне 32-битных целых чисел со знаком: [-231, 231 - 1]. Для решения этой проблемы предположим, что ваша функция возвращает 0 при переполнении обратного целого числа.
Пример 1:
Ввод: x = 123
Выход: 321
Пример 2:
Ввод: x = -123
Выход: -321
Пример 3:
Ввод: x = 120
Выход: 21
Пример 4:
Ввод: x = 0
Выход: 0
Когда я впервые занялся этим алгоритмом, я подумал, что могу использовать некоторые встроенные методы, такие как обратный. В конечном итоге я использовал это как часть решения.
Первая ошибка / совет
Знайте, с какими данными вы работаете!
Вот пустой код, который они оставляют вам:
var reverse = function(x) { };
Я сразу закодировал это, потому что мне в этом случае удобнее работать с массивом.
var reverse = function(x) { x.split(“ “) }
Мне сразу сказали, что x.split не является функцией. Почему? Потому что я работаю с целым числом, а не со строкой! Приятно отметить, что как привычка для меня, насколько я знаю, это могло бы вызвать смущение, будь это во время интервью в прямом эфире.
Моя вторая попытка кода помогла мне визуализировать каждый шаг решения. Для меня это важно, потому что я должен это увидеть, чтобы поверить :)
Вот вторая попытка с примечаниями:
var reverse = function(x) { let string = x.toString( ) let array = string.split(“ “) return array.reverse( ).join(“ “) }
Сломано в голове:
Given the first test case, 123 — let string = x.toString() // returns “123” let array = string.split(“”) // returns [“1”, “2”, “3”] array.reverse // [“3”, “2”, “1”] array.join // “321”
Я думаю, что решение позволяло возвращать строку в Leetcode, но вы увидите, что я возвращаю целое число в более позднем решении. Это сработало для первого тестового примера, который привел меня ко второму самостоятельному совету.
Всегда думайте о крайних и других случаях
Что делать, если число отрицательное? Если я запущу приведенный выше код для целого числа -123, он вернет 321-, а это не то, что мы хотим.
Итак, я мог поступить несколькими способами, но решил сначала спросить число, положительное оно или отрицательное. Следовательно, код теперь выглядит так:
var reverse = function(x) { if (x > 0) { let string = x.toString( ) let array = string.split(“ “) return Math.abs(array.reverse( ).join(“”)) } else { let positive = Math.abs(x) let string = positive.toString( ); let array = string.split(“”) return -Math.abs(array.reverse( ).join(“ “)) } }
Это решение решило проблему! Тем не менее, я хотел сказать последний совет по подготовке к собеседованию.
Есть ли лучший и более эффективный способ кодирования этого?
Ответ был определенно положительным. После просмотра другого решения есть еще много чего добавить к размышлениям. Вот одно из решений, которое немного поразило меня.
const reverse = x => { const limit = 2147483648 const k = x < 0 ? -1 : 1; const n = Number(String(Math.abs(x)).split(‘ ‘).reverse( ).join(“ “)); return n > limit ? 0 : n * k; }
Итак, давайте разберемся с этим:
Установка лимита
Это то, что мне нужно, чтобы мне было удобнее смотреть и спрашивать интервьюера. «Есть ли ограничения?» Я пропустил направление в проблеме с leetcode:
Ограничения:
-2³¹ <= x <= 2³¹ — 1
Первый константный предел в этом решении устраняет это ограничение. 2³¹ - 1 = 2147483648.
Вторая строка позволяет преобразовать возвращаемое значение в отрицательное или положительное путем умножения его на отрицательную единицу или положительную единицу.
const k = x < 0 ? -1 : 1
Другими словами: если x меньше нуля, вернуть -1, если нет, вернуть 1.
Третья строка - это суперсолидированный способ выполнения цепных вычислений, который мне очень нравится!
const n = Number(String(Math.abs(x)).split(“ “).reverse( ).join(“ “));
Другими словами: дайте мне число как окончательный результат взятия абсолютного числа.
let’s say test case of 123 // absolute is 123 turning it into a string // “123” splitting it into an array //[“1”, “2”, “3”] reversing it // [“3”, “2”, “1”] joining it // “321” running Number(“321”) = 321
Это невероятно, и я понял, что мне нужно лучше познакомиться с этими встроенными операциями Javascript, чтобы иметь возможность их использовать.
Делайте это так, как вам удобно
Однако мой мозг не обязательно сейчас работает таким образом. Я надеюсь, что когда-нибудь так и будет. Вот моя последняя работа, которая работает с этими новыми ограничениями.
var reversed = function(x) { if (x > 0) { let string = x.toString( ) let array = string.split(“”) let result = Math.abs(array.reverse( ).join(“”)) if (result < 2147483648) { return result } else { return 0 } } else { let positive = Math.abs(x) let string = positive.toString( ) let array = string.split( ) let result = -Math.abs(array.reverse( ).join(“”)) if (result > -2147483648) { return result } else { return 0 } } }
Определите свои слабые стороны
LeetCode - отличный ресурс для проверки времени выполнения и памяти. Хотя время выполнения моего решения составляет около 100 мс, что быстрее, чем у 48% других представленных материалов, использование памяти 40,5 МБ всего примерно на 9% меньше, чем у большинства представленных решений. Мне нужно переделать его снова и посмотреть, смогу ли я сделать его лучше, чтобы я понял это.
Твердость
На данный момент я знаю только одно. Я полон решимости решать проблемы и совершенствоваться в них. Может быть, работодатели не будут рассматривать алгоритмы как одно из моих сильнейших качеств. Однако я буду продолжать, пока не стану лучше, и буду продолжать решать проблему, пока не найду решение. Моим друзьям, коллегам и товарищам по кодированию: продолжайте!
- Келси