6.26号刷题

第一题 172. Factorial Trailing Zeroes

题目描述

给定一个整数n，返回n!（n的阶乘）数字中的后缀0的个数。

注意：你的解法应该满足多项式时间复杂度。

算法

我们发现，所有结尾的0都是有5 * 2得来的，因此我们只需要计算n中5的个数即可。但是注意25，125，…可能包含多个5.

public class trailingZeroes172 {
    public int trailingZeroes(int n) {
        int zero = 0;
        long count = 5;
        for (int i = 1; count <= n; i++) {
            zero += n / count;
            count *= 5;
        }
        return zero;
    }
    
    //Refactor
    public int trailingZeroes2(int n) {
        int res = 0;
        while (n > 0) {
            n /= 5;
            res += n;
        }
        return res;
    }

}

第二题 233. Number of Digit One

题目描述

统计在小于等于n的数中，总共出现了多少个1

注意：
不是多少个数出现1，而是多少个1。11算两个

算法

if n = xyzdabc
对于千位
(1) xyz * 1000                     if d == 0
(2) xyz * 1000 + abc + 1           if d == 1
(3) xyz * 1000 + 1000              if d > 1

由此我们可以写出算法

public class countDigitOne233 {
    public int countDigitOne(int n) {
        if (n <= 0) return 0;
        int temp = n, x = 1, res = 0;

        while (temp > 0) {
            int left = temp / 10;
            res += left * x;
            int digit = temp % 10;

            if (digit == 1) {
                int right  = n % x;
                res += right + 1;
            }
            if (digit > 1) {
                res += x;
            }
            temp /= 10;
            x *= 10;
        }
        return res;
    }
}

第三题 9. Palindrome Number

题目描述

查看一个数字看是否能够形成回文数，注意不能使用额外空间

算法

我们将这个数从左到右不断累加，看最后是否和其本身相同

public class isPalindrome9 {
    public boolean isPalindrome(int x) {
        if (x < 0 || (x != 0 && x % 10 == 0)) return false;
        int res = 0, temp = x;
        while (temp > 0) {
            res = res * 10 + temp % 10;
            temp /= 10;
        }
        return x == res;
    }

    //Refactor
    public boolean isPalindrome2(int x) {
        if (x < 0 || (x != 0 && x % 10 == 0)) return false;
        int res = 0;
        while (x > res) {
            res = res * 10 + x % 10;
            x /= 10;
        }
        return x == res || x == res / 10;
    }
}

第四题 50. Pow(x, n)

题目描述

求一个数的n次方

算法

利用回溯，将算法复杂度减小到logn级别，每次对半开，减少计算量。

Double X

public class myPow50 {
    public double myPow(double x, int n) {
        if (n == 0) return 1;
        if (n < 0) {
            n = -n;
            x = 1/x;
        }
        if (Double.isInfinite(x))
            return 0.;
        return n % 2 == 0 ? myPow(x * x, n / 2) : x * myPow(x * x, n / 2);
    }
}

Double myPow

public class Solution {
    public double myPow(double x, int n) {
        if (n == 0) return 1;

        double half = myPow(x, n / 2);

        if (n % 2 == 0) {
            return half * half;
        } else {
            if (n > 0) {
                return x * half * half;
            }
            else {
                return 1 / x * half * half;
            }
        }        
    }
}

第五题 372. Super Pow

题目描述

计算a ^ b mod 1337的值。a是正整数，b是一个极大的正整数，以数组形式给出。

算法

ab % k = (a%k)(b%k)%k
a^1234567 % k = (a^1234560 % k) * (a^7 % k) % k 
= (a^123456 % k)^10 % k * (a^7 % k) % k
我们可以写出方程
f(a,1234567) = f(a, 1234560) * f(a, 7) % k = f(f(a, 123456),10) * f(a,7)%k;

通过回溯的方法，实现这个方法

public class superPow372 {
    int base = 1337;
    public int superPow(int a, int[] b) {
        return superPow(a, b, b.length - 1);
    }

    public int superPow(int a, int[] b, int length) {
        if (length == 0) return powMod(a, b[0]);

        return powMod(superPow(a, b, length - 1), 10) * powMod(a, b[length]) % base;
    }

    public int powMod(int a, int k) {
        a %= base;
        int result = 1;
        for (int i = 0; i < k; i++) {
            result = result * a % base;
        }
        return result;
    }

}

第六题 368. Largest Divisible Subset

题目描述

给定一个不重复正整数集合，寻找最大子集，使得子集中的任意一对元素 (Si, Sj) 均满足Si % Sj = 0或者Sj % Si = 0。

如果存在多种答案，返回其中之一即可。

测试用例如题目描述。

算法

采用动态规划的思想，首先将每个数可能存在的最长序列记录下来。然后找到对应的这个最长序列，之后再将每个数一一添加进去。

public class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        Arrays.sort(nums);
        int[] dp = new int[nums.length];
        dp[0] = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] % nums[j] == 0) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                } else {
                    dp[i] = Math.max(dp[i], 1);
                }
            }
        }

        int maxCount = 0;
        for (int i = 0; i < nums.length; i++) {
            if (dp[i] > dp[maxCount]) maxCount = i;
        }

        int count = dp[maxCount];
        int num = nums[maxCount];

        for (int i = maxCount; i >= 0; i--) {
            if (count == dp[i] && num % nums[i] == 0) {
                res.add(nums[i]);
                count--;
                num = nums[i];
            }
        }

        return res;        
    }
}

第七题 507. Perfect Number

题目描述

判断某正整数n是否等于除其本身外所有因子之和

算法

由于对称性，只需要小于等于自身开方即可

public class Solution {
    public boolean checkPerfectNumber(int num) {
        if (num <= 1) return false;

        int sum = 1, end  = num;
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                sum += i + num / i;
//                end = num / i;
            }
        }
        return sum == num;
    }
}