点击关注上方“五分钟学算法”,

设为“置顶或星标”,第一时间送达干货。

又一道可以投机取巧的算法题:完美数

转自编程如画,作者灵魂画师牧码


今天分享的题目来源于 LeetCode 第 507 号问题:完美数。这是一道标签为 数学 的题目,本文不仅提供一般的解题思路,同时在文章末尾分享它的 投机取巧 的解法。

一、题目链接

https://leetcode-cn.com/problems/perfect-number/

二、题目描述

对于一个 正整数,如果它和除了它自身以外的所有正因子之和相等,我们称它为“完美数”。

给定一个 整数 n, 如果他是完美数,返回 True,否则返回 False

示例:

输入: 28
输出: True
解释: 28 = 1 + 2 + 4 + 7 + 14

提示:

输入的数字 n 不会超过 100,000,000. (1e8)

三、题目分析

完美数字的定义:一个整数等于除其自身之外的所有的因子之和。

由于不能包含自身,所以 n 必定大于1。

学过数学的都知道,1 是任意数字的因子,所以寻找其它因子的范围是 [2, sqrt(n)]

为什么是到 sqrt(n) 呢?

以数字 36 为例。

它的非自身外正因子有,1、2、3、4、6、9、12、18,其中 1 和 6 单独计算,[2, 18]、[3, 12]、[4, 9] 都是对应关系,所以只需要遍历到 36 的平方根 6 就可以获取全部正因子。

1单独计算的原因是要排除自身,6单独计算的原因是 6 * 6 = 36,两个值相同,故而只能计算一遍。

四、图片理解


又一道可以投机取巧的算法题:完美数

又一道可以投机取巧的算法题:完美数

又一道可以投机取巧的算法题:完美数

又一道可以投机取巧的算法题:完美数

又一道可以投机取巧的算法题:完美数

又一道可以投机取巧的算法题:完美数

又一道可以投机取巧的算法题:完美数

又一道可以投机取巧的算法题:完美数

五、参考代码


class Solution {
    public boolean checkPerfectNumber(int num) {
        if(num == 1) {
            return false;
        }
        int sum = 1// 正整数一定会有一个1,同时不用考虑自身,所以单独处理
        int i = 2;
        double sqrt = Math.sqrt(num);
        for(;i < sqrt;i++) {
            if(num % i == 0) {
                sum += i;
                sum += num / i;
            }
        }
        // 此处单独处理的原因在于只需要加1次i值,如果在循环中会加2次
        if(i * i == num) {
            sum += i;
        }
        return sum == num;
    }
}


事实上,在题目给出的范围里面,完美数是非常上的,只有  6, 28, 496, 8128, 33550336 这几个,可以通过判断该数字是否为以下几个来解决。

//投机取巧的解法
class Solution {
public:
    bool checkPerfectNumber(int num) {
        return num == 6 || num == 28 || num == 496 || num == 8128 || num == 33550336;
    }
};



END



又一道可以投机取巧的算法题:完美数

● 我这些年从来没有用过算法,除了出去面试的时候

● 摸鱼神器,千万别让老板看见!

● 面试了15位来自985/211高校的2020届研究生,熬夜赶出了这篇文章

为啥SQL加了索引会使数据查找更快?


又一道可以投机取巧的算法题:完美数


点“在看你懂得 

又一道可以投机取巧的算法题:完美数

原文始发于微信公众号(五分钟学算法):又一道可以投机取巧的算法题:完美数