力扣刷题篇之数与位3

系列文章目录

前言

数学问题

总结

前言

本系列是个人力扣刷题汇总，本文是数与位。刷题顺序按照[力扣刷题攻略] Re：从零开始的力扣刷题生活 - 力扣（LeetCode）

数学问题

204. 计数质数 - 力扣（LeetCode）

通过遍历从2开始到 n 的平方根，将每个质数的倍数标记为非质数，最终统计未被标记为非质数的数的个数。

class Solution {
    public int countPrimes(int n) {
        if (n <= 1) {
            return 0; // 小于等于1的情况下没有质数
        }

        // 创建一个布尔数组，用于标记是否是质数，初始化都为 true
        boolean[] notPrime = new boolean[n];
        notPrime[0] = notPrime[1] = true; // 0和1不是质数

        // 使用埃拉托斯特尼筛法，从2开始遍历到sqrt(n)
        for (int i = 2; i < Math.sqrt(n); i++) {
            if (!notPrime[i]) {
                // 如果当前数是质数，则将其倍数标记为非质数
                for (int j = 2; j * i < n; j++) {
                    notPrime[i * j] = true;
                }
            }
        }

        // 统计未被标记为非质数的数的个数
        int count = 0;
        for (int i = 2; i < notPrime.length; i++) {
            if (!notPrime[i]) {
                count++;
            }
        }
        return count;
    }
}

263. 丑数 - 力扣（LeetCode）

通过循环除以质因子 2、3、5 来判断是否是丑数。如果最终 n 等于 1，说明原始数字只包含质因子 2、3 和/或 5，即是丑数。

class Solution {
    public boolean isUgly(int n) {
        if(n<=0){
            return false;
        }
        while(n%2==0){
            n/=2;
        }
        while(n%3==0){
            n/=3;
        }
        while (n%5==0){
            n/=5;
        }
       
        return n==1;
    }
}

367. 有效的完全平方数 - 力扣（LeetCode）

使用二分查找的思想，将范围划分为 [1, num]，在每一步中找到中点 mid，然后判断 mid 的平方是否等于 num。如果是，则判断 num 是否能被 mid 整除；如果 mid 的平方小于 num，则更新搜索范围为 [mid+1, high]；如果 mid 的平方大于 num，则更新搜索范围为 [low, mid-1]。最终如果找到一个平方等于 num 的数，则返回 true，否则返回 false。

class Solution {
    public boolean isPerfectSquare(int num) {
        int low = 1;
        int high = num;

        // 使用二分查找
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int t = num / mid;

            // 如果 mid 的平方等于 num，判断 num 是否能被 mid 整除
            if (t == mid) {
                if (num % mid == 0) {
                    return true;
                }
                low = mid + 1;
            } else if (t < mid) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return false;
    }
}

1071. 字符串的最大公因子 - 力扣（LeetCode）

使用递归的思想。它检查两个字符串的长度，如果相等，则判断是否相等，如果不相等，则递归调用自身，去掉较长字符串的前缀部分，直到两个字符串相等或某一个为空。最终返回最大公约字符串。

class Solution {
    public String gcdOfStrings(String str1, String str2) {
        // 如果其中一个字符串为空，则返回另一个字符串
        if ("".equals(str1)) {
            return str2;
        }
        if ("".equals(str2)) {
            return str1;
        }

        // 如果两个字符串长度相等，返回它们本身或空字符串
        if (str1.length() == str2.length()) {
            return str1.equals(str2) ? str1 : "";
        } else if (str1.length() < str2.length()) {
            // 如果 str1 的长度小于 str2，判断 str1 是否为 str2 的前缀
            if (!str1.equals(str2.substring(0, str1.length()))) {
                return "";
            }
            // 递归调用 gcdOfStrings，去掉 str1 部分
            return gcdOfStrings(str1, str2.substring(str1.length()));
        } else {
            // 如果 str2 的长度小于 str1，判断 str2 是否为 str1 的前缀
            if (!str2.equals(str1.substring(0, str2.length()))) {
                return "";
            }
            // 递归调用 gcdOfStrings，去掉 str2 部分
            return gcdOfStrings(str2, str1.substring(str2.length()));
        }
    }
}