每日一题:LeetCode:507.完美数

浏览次数 : 次 2022-01-21

博文字数统计 : 593字 | 阅读所需时长 : 2分

× 文章目录

1. 2021-12-31：LeetCode：507.完美数

每日一题：LeetCode：507.完美数
- 时间：2021-12-31
- 力扣难度：Easy
- 个人难度：Easy
- 数据结构：整型
- 算法：数学、模拟

2021-12-31：LeetCode：507.完美数

1. 题目描述

题目：原题链接
- 对于一个正整数，如果它和除了它自身以外的所有正因子之和相等，我们称它为「完美数」
- 给定一个整数 n，如果是完美数，返回 true，否则返回 false
- 注意同样值的数字不可以多次使用
输入输出规范
- 输入：正整数num
- 输出：布尔值，表示是否是完美数
输入输出示例
- 输入：nums = 28
- 输出：true

2. 方法：简单模拟

思路：暴力模拟+剪枝
- 暴力枚举
- 注意遍历过程可以剪枝，根据因子成对出现(对称性)的特点优化循环次数
复杂度分析：n是正整数的数值大小
- 时间复杂度：$O(\sqrt{n})$
- 空间复杂度：$O(1)$，只使用一个变量来记录因子常量空间和

题解

public boolean checkPerfectNumber(int num) {
    if (num == 1) return false;
    int sum = 1;
    for (int i = 2; i <= num / i; i++) {
        if (num % i == 0) {
            sum += i;
            if (i * i != num) sum += num / i;
        }
    }
    return sum == num;
}

3. 扩展：打印完美数

题目：打印指定数字n以内的所有完美数
- 输入：100
- 输出：[6, 28]
思路：暴力模拟+剪枝
复杂度分析：n是正整数的数值大小
- 时间复杂度：$O(n\sqrt{n})$
- 空间复杂度：$O(n)$，每次循环有一个sum，以及最终存放完美数结果的List

题解

// 打印n以内的完美数
public List<Integer> printPerfectNumber(int n) {
    List<Integer> res = new ArrayList<>();
    if(n <= 0) return res;

    for (int num = 2; num <= n; num++) {
        int sum = 1;
        for (int i = 2; i <= num / i; i++) {
            if (num % i == 0) {
                sum += i;
                if (i * i != num) sum += num / i;
            }
        }
        if(sum == num) res.add(num);
    }
    return res;
}

4. 其他特殊数字题目

素数：https://leetcode-cn.com/problems/prime-palindrome/
丑数：https://leetcode-cn.com/problems/ugly-number/
回文数：https://leetcode-cn.com/problems/palindrome-number/
自除数：https://leetcode-cn.com/problems/self-dividing-numbers/
快乐数：https://leetcode-cn.com/problems/happy-number/
顺次数：https://leetcode-cn.com/problems/sequential-digits/
累加数：https://leetcode-cn.com/problems/additive-number/
计数质数：https://leetcode-cn.com/problems/count-primes/
完全平方数：https://leetcode-cn.com/problems/perfect-squares/
如有其他，请评论区补充 ~ ~ ~

本文作者： Chthollists
发布时间： 2022-01-21 23:09:05
最后更新： 2022-01-21 23:09:05
本文标题： 每日一题:LeetCode:507.完美数
本文链接： https://chthollists.github.io/post/b30db932.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！