难度说明：🟢简单🟡中等🔴困难

hot150-18-数学

🟢01-回文数（9）

1.题目内容

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

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

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

示例 1：

输入：x = 121
输出：true

示例 2：

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

示例 3：

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

2.题解思路

👻方法1：遍历法

/**
 * 009 回文数
 */
public class Solution1 {
    /**
     * 回文数：逆序都是一样的数字（回归到和回文字符串判断的思路）
     * 正序逆序遍历序列一致、双指针遍历等
     */
    public boolean isPalindrome(int x) {
        String xstr = String.valueOf(x);
        // 获取逆序后的数字
        StringBuffer reverseStr = new StringBuffer();
        for (int i = xstr.length() - 1; i >= 0; i--) {
            reverseStr.append(xstr.charAt(i));
        }
        // 判断正序、逆序是否一致
        return xstr.equals(reverseStr.toString()); // 字符串比较
    }
}

• 复杂度分析

  • 时间复杂度：O（n） 遍历一遍元素

  • 空间复杂度：O（n）需要辅助字符串存储逆序后的元素

👻方法2：双指针法

• 思路分析：和判断回文字符串类似，将数字转化为字符串，然后通过双指针的方式来进行判断

public class Solution2 {
    /**
     * 回文数：逆序都是一样的数字（回归到和回文字符串判断的思路）
     * 正序逆序遍历序列一致、双指针遍历等
     */
    public boolean isPalindrome(int x) {
        String xstr = String.valueOf(x);
        // 定义双指针进行遍历
        int start = 0,end = xstr.length()-1;
        // 遍历元素，指针相遇则循环结束
        while(start<end){
            // 判断指针指向元素是否相同
            if(xstr.charAt(start)!=xstr.charAt(end)){
                return false;
            }
            // 指针后移，继续比较下个位置
            start++;
            end--;
        }
        return true;
    }
}

• 复杂度分析

  • 时间复杂度：O（n）最多只需要遍历一半的元素

  • 空间复杂度：O（1）只需要两个指针记录比较的位置

👻方法3：数学规律法（全反转）（不转化为字符串的思路）

• 通过分析数学规律，单独处理一些额外的情况
  • x<0：负数反转后不符合数学规律，直接返回false
  • x>=0：采用数位分离的思路对数字进行逆序，判断最终得到的数字和x是否一致

/**
 * 009 回文数
 */
public class Solution2 {
    /**
     * 在不使用字符串或者数组的情况下进行判断
     */
    public boolean isPalindrome(int x) {

        /**
         * 数学规律分析：
         * 1.过滤：如果x为负数或者其以0结尾(x==0是满足的)，则其回文序列不符合数学约定，对于这部分的数据可以先过滤掉
         * 2.反转：如果为正数，则判断反转后的数字和原数字是否一致
         */
        // 过滤
        if (x < 0 ) { // x < 0 || (x % 10 == 0 && x != 0) 如果是全反转，则整数部分直接交由后面的反转逻辑校验
            return false;
        }

        // 反转数字(只需要反转一半)
        int reverseNum = 0;
        int num = x;
        // 基于数位分离的思想
        while (num != 0) {
            reverseNum = reverseNum * 10 + num % 10; // 每次截取最后一个位置的数字，随后构建逆序序列
            num = num / 10;
        }
        return reverseNum == x;
    }

}

• 复杂度分析

  • 时间复杂度：O（n）n 为数字长度（采用数位分离的思路对数字进行逆序）

  • 空间复杂度：O（1），需要常数级空间存储逆序的数字

👻方法4：数学规律法（一半反转）（不转化为字符串的思路）

• 通过分析数学规律，单独处理一些额外的情况，然后翻转一半的数字进行比较
• 当原始数字小于或等于反转后的数字时，就意味着我们已经处理了一半位数的数字了

class Solution {
    public boolean isPalindrome(int x) {
        // 特殊情况：
        // 如上所述，当 x < 0 时，x 不是回文数。
        // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
        // 则其第一位数字也应该是 0
        // 只有 0 满足这一属性
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }

        // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
        // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == revertedNumber || x == revertedNumber / 10;
    }
}

• 复杂度分析

  • 时间复杂度：O(logn)，对于每次迭代，会将输入除以 10，因此时间复杂度为 O(logn)

  • 空间复杂度：O(1)。只需要常数空间存放若干变量

🟢02-加1（66）

1.题目内容

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

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：digits = [9]
输出：[1,0]
解释：输入数组表示数字 9。
加 1 得到了 9 + 1 = 10。
因此，结果应该是 [1,0]。

2.题解思路

👻方法1：数学规律法

• 思路分析：
  • 因为只有数字9才会引起+1后的进位，因此只需要关注数字9会不会引起进位
  • 逆序遍历数字：
    • 如果是数字9，则说明出现进位，需要将当前位置置为0，然后继续遍历下个数字
    • 如果非数字9，则执行+1操作并返回（这里有个技巧是不需要每次都去带进位，而是巧妙用这个+1的思路，如果没有出现进位则可以直接返回）
    • 逆序遍历结束后，如果程序正常执行，则说明存在进位，则需要把这个进位补充到数组头部（如果不存在进位，则在遍历过程中就会返回结果）
      • 加长数组：构建一个加长数组（长度+1），然后copy原来的digits，然后设定newDigits[0] = 1
      • 加长数组：直接构建一个加长数组（长度+1），不需要copy（因为能走到这一步的只能是[0,0,0,]这种形式）
  • 案例分析：
    • 10：逆序遍历，非数字9，执行+1，返回11
    • 19：逆序遍历，第一个数字是9，则置为0=》10，此时存在进位1（和+1有异曲同工之妙）继续往前遍历，得到20（直接返回）
    • 99：逆序遍历，第一个数字是9，则置为0=》90，此时存在进位1 继续往前遍历，得到00，遍历结束。for 正常结束并没有返回，说明还存在进位，则构建新数组，在头部补充进位，得到100

/**
 * 066 加一
 */
public class Solution1 {
    /**
     * 数学规律法：逆序遍历数字元素
     * 1.判断数字是否为9，为9则置为0（且带有进位1，这个进位1和加1的作用是等价的，因此不需要额外定义变量维护carry）
     */
    public int[] plusOne(int[] digits) {
        for(int i = digits.length-1;i>=0;i--){
            if(digits[i]==9){
                digits[i]=0; // 继续遍历
            }else{
                // 如果当前元素非9，执行+1，并返回
                digits[i] += 1;
                return digits;
            }
        }
        // 如果for完整遍历完成，说明还存在进位，则需要加长数组，在头部补足进位
//        int[] newDigits = new int[digits.length+1];
//        Arrays.copyOfRange(digits,1,newDigits.length);
//        newDigits[0] = 1;
//        return newDigits;

        digits= new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }

    public static void main(String[] args) {
        int[] digits = new int[]{9,9};
        Solution1 solution1 = new Solution1();
        solution1.plusOne(digits);
    }
}

• 复杂度分析

  • 时间复杂度：O（n）

  • 空间复杂度：O（1） 如果是基于原数组操作，最后只需要加长一位

🟡03-阶乘后的零（172）

1.题目内容

给定一个整数 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

2.题解思路

👻方法1：阶乘法（❌）

• 思路分析：正常思路分析就是计算n的阶乘，然后数位分离统计尾随0的个数（逆序统计，遇到非0则结束统计）
  • 数值溢出：使用int接收处理需考虑阶乘的大数运算问题（int类型最多支持存储12!，超出则无法正常计算），因此要选择long或者BigDecimal来支持大数阶乘运算

/**
 * 阶乘后的零（172）
 */
public class Solution1 {
    /**
     * 1.计算阶乘数
     * 2.统计尾随0
     */
    public int trailingZeroes(int n) {
        // 定义阶乘结果
        int res = 1;
        while(n>0){
            res *= n;
            n--;
        }
        /*
        for (int i = 1; i <= n; i++) {
            res *= i;
        }
         */

        // 统计尾随0
        int count = 0;
        while (res > 0) {
            if (res % 10 == 0) {
                count++; // 存在尾随0，计数+1
                res = res / 10; // 去掉尾部元素，进行下一次判断
            } else {
                // 遇到非尾随0直接结束(尾随0：接收)
                return count;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int n = 7;
        Solution1 solution1 = new Solution1();
        System.out.println(solution1.trailingZeroes(13));
    }
}

• 复杂度分析

  • 时间复杂度：

  • 空间复杂度：

👻方法2：计算5的倍数的个数

• 思路分析：将思路转化为思考怎样的乘法会出现尾随零
  • 将N阶乘的尾随零转化为查找【1，N】范围区间内5的倍数的个数
  • 实现：不断将n除以5，累加每次做了除后的n

public int trailingZeroes(int n) {
    return n == 0 ? 0 : n / 5 + trailingZeroes(n / 5); 
}

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

• 复杂度分析

  • 时间复杂度：

  • 空间复杂度：

🟢04-x的平方根（69）

1.题目内容

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

2.题解思路

👻方法1：规律法

/**
 * 069 x 的平方根
 */
public class Solution1 {

    /**
     * 不能使用内置函数求解：硬核思路就是遍历每个自然数的平方，然后得到最接近目标数的
     * 但需注意用long类型处理数据，否则可能出现数值溢出问题
     */
    public int mySqrt(int x) {
        long res = 0;
        for (long i = 0; i * i <= x; i++) {
            res = i;
        }
        return (int) res;
    }
}

// 不用long的思路：采用除法思路
class Solution {
public:
    int mySqrt(int x) {
        int ans =0;
        if (x<2) return x;
        for(int i =1; x/i>=i;i++){
            ans =i;
        }
        return ans;
    }
};

• 复杂度分析

  • 时间复杂度：O（logN）

  • 空间复杂度：O（1）占用常数级空间

🟡05-Pow（x，n）（50）

1.题目内容

​ 实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xⁿ ）

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

2.题解思路

👻方法1：常规法（❌暴力遍历，超出时间限制）

• 思路分析：常规思路就是如何计算x的n次幂，需要区分n与0的比较
  • n=0：任何数的0次幂都是1
  • n>0：n个x累乘
  • n<0：n个x累乘取倒数，或者先取倒数后累乘

class Solution {
    public double myPow(double x, int n) {
        // 定义操作结果
        double res = 1;
        if(n==0){
            return 1;
        }else if(n>0){
            // 如果n>0，则是n个x累乘
            for(int i=1;i<=n;i++){
                res *= x;
            }
        }else {
            // 如果n<0,则为x的倒数的累乘
            x = 1/x;
            for(int i=1;i<= (-1)*n ;i++){ // 将n切为整数
                res *= x;
            }
        }
        return res;
    }
}

• 复杂度分析

  • 时间复杂度：

  • 空间复杂度：

👻方法2：递归+快速幂

• 思路分析：先理解【方法1】的思路，推导实现公式
  • 例如 x⁶⁴：x => x² => x⁴ => x⁸ => x¹⁶ => x³² => x⁶⁴
  • 例如 x⁷⁷：x => x² => x⁴ => x⁹ => x¹⁹ => x³⁸ => x⁷⁷
• 结合上述规律分析
  • 当要计算 xⁿ 时，先递归计算出 y = x^n/2（n/2向下取整）
  • 根据递归计算的结果，如果n为偶数，则xⁿ=y²，如果n为奇数则xⁿ=y² × x
• 算法实现：
  • 确定递归函数，得到 xⁿ 的值（这个递归函数只处理n>=0的情况）
  • 随后再在myPow方法中做n的正负处理

/**
 * q50 Pow(x,n)
 */
public class Solution2 {
    /**
     * 递归计算 y = x ^n/2^
     * - 如果n为偶数则 x ^n^ = y * y
     * - 如果n为奇数则 x ^n^ = y * y * x
     */
    public double myPow(double x, int n) {
        return n >= 0 ? quickly(x, n) : (1.0 / quickly(x, -n));
    }

    /**
     * 递归计算 x^n^
     */
    public double quickly(double x, int n) {
        if (n == 0) {
            return 1;
        }
        double y = quickly(x, n / 2);
        return n % 2 == 0 ? y * y : y * y * x;
    }
}

• 复杂度分析

  • 时间复杂度：O（log n）对 n 进行二分拆分

  • 空间复杂度：O（1）

🔴06-直线上最多的点数（149）

1.题目内容

给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

示例 1：

输入：points = [[1,1],[2,2],[3,3]]
输出：3

示例 2：

输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4

提示：

• 1 <= points.length <= 300
• points[i].length == 2
• -104 <= xi, yi <= 104
• points 中的所有点 互不相同

2.题解思路

👻方法1：三层暴力循环

• 思路分析：三层循环暴力遍历，每次拿到3个点判断，然后计算3个点构成的斜率是否相等（注意除法转乘法，避免精度丢失）
  • 第1层循环：拿到(x,y)节点
  • 第2层循环：拿到(x1,y2)节点（从i+1的位置开始）
  • 第3层循环：拿到(x2,y2)节点（从j+1的位置开始），随后基于此计算斜率并统计斜率相同的情况
    • 以(x,y)\(x1,y1)两点构成一线，然后判断(x2,y2)点是否可以加入这条直线
      • (y1-y)/(x1-x) = (y2-y1)/(x2-x1) => 转成乘法(y1-y) * (x2-x1) = (y2-y1) * (x1-x)
      • 如果斜率相同，则cur++（cur表示当前轮次起点可构成直线的节点个数，起始从0开始）
    • 第3层循环遍历完成，便可以更新当前轮次的 max ，然后继续寻找下一个i、j点位，进行新一轮的斜率计算

/**
 * 149 直线上最多的点数
 */
public class Solution1 {

    /**
     * 遍历法：
     * 1.每个点都有可能作为起点，固定起点然后遍历其他点
     * 2.起点相同，如果遍历的过程中计算两个点的斜率相同则说明在同一直线上
     * 斜率 K = (y2-y1)/(x2-x1)
     */
    public int maxPoints(int[][] points) {
        int m = points.length, n = points[0].length;
        // 临界长度判断
        if (m <= 2) {
            return m;
        }

        // 大于3个节点则进行遍历判断
        int max = 2; // 最少有两个节点构成一线
        for (int i = 0; i < m - 2; i++) {
            // 获取起点坐标
            int x = points[i][0], y = points[i][1];
            // 遍历其他点
            for (int j = i + 1; j < m - 1; j++) {
                // 获取当前坐标点
                int x1 = points[j][0], y1 = points[j][1];
                // 定义当前轮次的直线点
                int cur = 2; // 起点计数为2（已经有2个点构成一线了，此处判断是否要补充新的点）
                for (int k = j + 1; k < m; k++) {
                    int x2 = points[k][0], y2 = points[k][1];
                    // 判断斜率是否相同（此处为了避免除法导致浮点数精度误差，采用惩罚思路比较）
                    if ((y1 - y) * (x2 - x1) == (y2 - y1) * (x1 - x)) {
                        cur++;
                    }
                }
                // 当前轮次判断完成，更新最大值
                max = Math.max(max, cur);
            }
        }
        // 返回结果
        return max;
    }

}

• 复杂度分析

  • 时间复杂度：O(n³) 三层遍历

• 空间复杂度：O(1) 需要常数级的空间存储点坐标和最大值