Как будет отсортирован следующий массив [-1, 0, 1, 2, -1, -4, -2, -3, 3, 0, 4].sort()?

🥱 Предыстория

На выходных я решал литкод, и в задаче 3sum было необходимо отсортировать массив по возрастанию, перед тем как перейти к основной реализации алгоритма.

Я написал решение, подебажил на бумаге — всё работает, отправляю код на проверку — не работает 🤷‍♂️. Перепроверяю всё глазами — ну должно же работать!

Сдаюсь и начинаю дебажить в VS Code и вижу, что сортировка массива работает не так как я ожидал.

ℹ️ Объяснение

Если перейти на MDN и прочитать документацию Array.prototype.sort(), то станет всё понятно.

Метод sort() в JavaScript преобразует элементы в строки и затем сравнивает их последовательности значений кодов UTF-16. Это означает, что при сортировке числа рассматриваются как строки.

Таким образом, числа в данном случае сортируются на основе их строкового представления. Например, '-10' будет идти перед '-2', потому что строка '10' идет перед строкой '2' в лексикографическом порядке.

Чтобы выполнить числовую сортировку массива, нужно предоставить функцию сравнения методу sort(), как показано здесь:

[-1, 0, 1, 2, -1, -4, -2, -3, 3, 0, 4].sort((a, b) => a - b);


Это даст вам [-4, -3, -2, -1, -1, 0, 0, 1, 2, 3, 4] — числовую сортировку.

https://t.me/cherkashindev/136

Всем привет. Сегодня решил взять задачку посложнее начального уровня и вот что из этого вышло. Ссылка на задачу:

https://leetcode.com/problems/reverse-integer/description/

Как я понял задачу: на вход подается целое число в пределах от -2 ** 31 <= x <= (2 ** 31) - 1. Нужно вернуть целое число с цифрами в обратном порядке и тем же знаком(+/-). Если результат вышел за пределы -2 ** 31 <= x <= (2 ** 31) - 1 вернуть 0.

Что пришло в голову сразу же, как можно решить в лоб:

Сначала отбросим знак в какую-нибудь переменную и будем работать с неотрицательным числом. Для этого определим статический метод класса, который будет определять, отрицательное ли наше число. В общем то, можно прямо в функции было сравнивать заданное число с нулем, но принцип единственной ответственности (SRP) запрещает:

Самая проблема, что мы не знаем порядка числа(сколько цифр в числе), поэтому принял решение брать последнюю цифру в числе через остаток от деления на 10 и отбрасывать ее через целочисленное деление на 10:

Ну и завернуть все это в цикл while, с условием пока x - положительный :

В принципе на этом можно было бы и закончить, все таки 15% лучших по скорости, но уж как то все это кривовато. Пока думал, как же определить количество разрядов в числе, где-то на границе создания вертелось, что можно проще и вот эта строка не давала покоя: count = len(str(x))

Тут мы определяем количество разрядов просто по количеству символов, а что если для решения задачи работать не с числом, а с символами, которые их означают?

И таки да, сначала число приводим к строке, затем через срез разворачиваем строку и приводим обратно к числу.

Схлопнем эти три строки в одну, поправим логику в методе проверки результата и отправим итоговое решение:

В принципе результат даже улучшился, по скорости обработки такое решение вошло в 6% лучших предложенных.

Посмотрим, что же предлагает нам chatGPT:

Я добился результата за 20 минут, бот за две секунды. Я конечно понимаю, что я новичок, что алгоритмические задачки хорошо сформулированы, но разница в производительности заставляет задуматься.

Тоже забавная задачка – со “сломанной клавиатурой”. Решил в ней Arrays.binarySearch использовать для поиска буквы слова в наборе “сломанных клавишей”, да и чтобы не забыть о его (метода) существовании в целом.

Судя по статистике – нормально получилось, в общем-то.

class Solution {

public int canBeTypedWords(String text, String brokenLetters) {

var brL = brokenLetters.toCharArray();

Arrays.sort(brL);

var words = text.split(" ");

int canTypeCnt = 0;

for (var word : words) {

boolean canType = true;

for (int i = 0; i < word.length(); i++) {

if (Arrays.binarySearch(brL, word.charAt(i)) >= 0) {

canType = false;

break;

}

}

if (canType) {

canTypeCnt++;

}

}

return canTypeCnt;

}

}

Success:

Runtime:2 ms, faster than 91.93% of Java online submissions.

Memory Usage:42.7 MB, less than 23.23% of Java online submissions.

Оригинал.