Анимация: три решения для палиндромных чисел |

алгоритм

Название взято из выпуска LeetCode № 9: Количество палиндромов. Сложность вопроса — «Легко», а текущий проходной балл — 56,0%.

Описание темы

Определяет, является ли целое число палиндромом. Палиндром — это целое число, которое одинаково читается в положительном порядке (слева направо) и в обратном порядке (справа налево).

Пример 1:

输入: 121
输出: true

Пример 2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

Пример 3:

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

Передовой:

Можете ли вы решить это, не преобразовывая целые числа в строки?

Тематический анализ

Решение 1: Общее решение

Лучший способ понять это — сначалаЦелое число в строку, а затем разбить строку на массивы, вам нужно только зациклить половину длины массива, чтобы определить, равны ли соответствующие элементы.

описание анимации

Код

///简单粗暴，看看就行
class Solution {
    public boolean isPalindrome(int x) {
        String reversedStr = (new StringBuilder(x + "")).reverse().toString();
        return (x + "").equals(reversedStr);
    }
}

Решение 2. Усовершенствованное решение --- математическое решение

Соответствующие числа в целых числах получаются округлением и операциями сравнения остатка.

Например: число 1221.

  • Подсчитав 1221/1000, получим первую 1
  • Вычислив 1221 % 10, можно получить последнюю 1
  • Сравнивать
  • Затем выньте 22, чтобы продолжить сравнение.

описание анимации

Код

class Solution {
    public boolean isPalindrome(int x) {
        //边界判断
        if (x < 0) return false;
        int div = 1;
        //
        while (x / div >= 10) div *= 10;
        while (x > 0) {
            int left = x / div;
            int right = x % 10;
            if (left != right) return false;
            x = (x % div) / 10;
            div /= 100;
        }
        return true;
    }
}

Решение 3: Расширенное решение --- гениальное решение

Интуитивно глядя на числа-палиндромы, создается впечатление, что числа складываются пополам, чтобы посмотреть, могут ли они совпасть одно за другим.

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

Здесь следует отметить, что, поскольку количество цифр палиндрома может быть нечетным или четным, когда его длина четная, оно должно быть равным при сложении пополам; когда его длина нечетная, то после сложения пополам, Есть длина, которую нужно отбросить на одну цифру (поделить на 10 и округлить в большую сторону).

Конкретные методы заключаются в следующем:

  • Каждый раз, когда выполняется остаточная операция (%10), извлекается наименьшее число:y = x % 10
  • Добавьте наименьшее число в конец полученного числа:revertNum = revertNum * 10 + y
  • Для каждой младшей значащей цифры x делится на 10
  • судитьxэто меньше, чемrevertNum, когда он меньше, это означает, что число было вдвое или больше половины
  • Наконец, оцените нечетные и четные числа: если оно четное, то revertNum равно x; если оно нечетное, среднее число находится в самом младшем бите revertNum, и оно должно быть равно x после деления на 10.

описание анимации

Код

class Solution {
    public boolean isPalindrome(int x) {
        //思考：这里大家可以思考一下，为什么末尾为 0 就可以直接返回 false
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;
        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }
        return x == revertedNumber || x == revertedNumber / 10;
    }
}

End

Дань LGD

Категории