刷题日记 24.5.6

lc201. 数字范围按位与（MD）

给你两个整数 left 和 right ，表示区间 [left, right] ，返回此区间内所有数字 按位与 的结果（包含 left 、right 端点）。

示例 1：

输入：left = 5, right = 7
输出：4

示例 2：

输入：left = 0, right = 0
输出：0

示例 3：

输入：left = 1, right = 2147483647
输出：0

提示：

0 <= left <= right <= 2^31 - 1

可以通过将两个数字不断向右移动，直到数字相等，即数字被缩减为它们的公共前缀。然后，通过将公共前缀向左移动，将0添加到公共前缀的右边以获得最终结果

class Solution {
    public int rangeBitwiseAnd(int left, int right) {
        int shift = 0;
        while (left < right) {
            right >>= 1;
            left >>= 1;
            shift++;
        }
        return left << shift;
    }
}

lc9. 回文数（EZ）

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。

示例 1：

输入：x = 121
输出：true

示例 2：

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

示例 3：

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

提示：

-231 <= x <= 231 - 1

**进阶：**你能不将整数转为字符串来解决这个问题吗？

考虑进阶情况和非进阶情况。非进阶的话自然是把数字转换为字符串来处理，然后用双指针法

class Solution {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }
        if (x == 0) {
            return true;
        }
        String num = String.valueOf(x);
        int l = 0, r = num.length() - 1;
        while (l < r) {
            if (num.charAt(l) != num.charAt(r)) {
                return false;
            }
            l++;
            r--;
        }
        return true;
    }
}

如果要考虑进阶要求，那么可以考虑通过取余和取整的操作来获取数字的最高位和最低位，然后进行比较

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;
    }
}

lc66. 加一（EZ）

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位，数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

示例 2：

输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。

示例 3：

输入：digits = [0]
输出：[1]

提示：

1 <= digits.length <= 100
0 <= digits[i] <= 9

从数字的最高位（也就是数组的最后一个下标）开始向低位模拟（也就是数组的低下标位置）

class Solution {
    public int[] plusOne(int[] digits) {
        int len = digits.length;
        for (int i = len - 1; i >= 0; i--) {
            if (digits[i] != 9) {
                digits[i]++;
                for (int j = i + 1; j < len; j++) {
                    digits[j] = 0;
                }
                return digits;
            }
        }
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }
}

lc172. 阶乘后的零（MD）

给定一个整数 n ，返回 n! 结果中尾随零的数量。

提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

示例 1：

输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0

示例 2：

输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0

示例 3：

输入：n = 0
输出：0

提示：

0 <= n <= 104

**进阶：**你可以设计并实现对数时间复杂度的算法来解决此问题吗？

$n! $尾零的数量即为 $n!$ 中因子 10 的个数，而 $10=2\times 5$ ，因此转换成求$ n!$ 中质因子 2 的个数和质因子 5 的个数的较小值。

由于质因子 5 的个数不会大于质因子 2 的个数，我们可以仅考虑质因子 5 的个数。

而 $n!$ 中质因子 5 的个数等于 $[1,n]$ 的每个数的质因子 555 的个数之和，我们可以通过遍历 $[1,n]$ 的所有 5 的倍数求出。

class Solution {
    public int trailingZeroes(int n) {
        int res = 0;
        while (n != 0) {
            n /= 5;
            res += n;
        }
        return res;
    }
}