文档章节

Perfect Number

叶枫啦啦
 叶枫啦啦
发布于 2017/06/27 15:34
字数 424
阅读 6
收藏 0
点赞 0
评论 0

问题:

We define the Perfect Number is a positive integer that is equal to the sum of all its positive divisors except itself.

Now, given an integer n, write a function that returns true when it is a perfect number and false when it is not.

Example:

Input: 28
Output: True
Explanation: 28 = 1 + 2 + 4 + 7 + 14

Note: The input number n will not exceed 100,000,000. (1e8)

解决:

① 第一种思路是暴力解决,但是超时了。

public class Solution {
    public boolean checkPerfectNumber(int num) {
        if(num <= 0) return false;
        int sum = 0;
        for (int i = 1;i < num ;i ++ ) {
            if (num % i == 0) {
                sum += i;
            }
        }
        if (num == sum) {
            return true;
        }else{
            return false;
        }
    }
}

② 根据上一个解法,我们考虑2-sqrt(nums)范围内的数,之后的就是nums/之前的数。要注意的是要考虑到i!=num / i的情况。

public class Solution { //14ms
    public boolean checkPerfectNumber(int num) {
        if (num == 1) return false;
        int sum = 0;
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                sum += i;
                if (i != num / i) sum += num / i;
            }
        }
        sum ++;
        return sum == num;
    }
}

进阶版****:

public class Solution { //14ms
    public boolean checkPerfectNumber(int num) {
        if (num == 1) return false;
        int sum = 0;
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                sum += i + num / i;
            }
        }
        sum ++;
        return sum == num;
    }
}

每个完美数都可以写成从1开始的几个自然数之和,如:
6 = 1 + 2 + 3
28 = 1 + 2 + 3 + 4 + 5 + 6 + 7
我么可以看出,最后一个加数是最大的不能被2整除的因子n。由求和公式可以得到最终的和:                   sum = n *(n + 1)/ 2

public class Solution { //10ms
    public boolean checkPerfectNumber(int num) {       
        if(num <= 1) {
            return false;
        }        
        int sum = 0;
        int n = num;
        while(n % 2 == 0) { //可以被2整除
            n /= 2;
        }
        sum = n * (n + 1) / 2;
        return sum == num;
    }
}

④ sum = 1 + 2 + ...... + 最大的不能被2整除的因子。

public class Solution { //11ms
    public boolean checkPerfectNumber(int num) {
       if(num == 0 || num == 1) return false;
        int sum = 1;
        int n = 2;
        while(num % n == 0){
            sum += n;
            sum += num / n;
            n = 2 * n;          
        }

        return sum == num ? true : false;
    }
}

© 著作权归作者所有

共有 人打赏支持
叶枫啦啦
粉丝 3
博文 540
码字总数 260604
作品 0
海淀
 HDU 3826 Squarefree number:题目解答源码

  HDU 3826 Squarefree number:题目解答源码   In mathematics,a squarefree number is one which is divisible by no perfect squares,except 1.For example,10 is square-free but 1......

爱mili ⋅ 2016/09/20 ⋅ 0

poj 1274 The Perfect Stall

The Perfect Stall Description Farmer John completed his new barn just last week, complete with all the latest milking technology. Unfortunately, due to engineering problems, all......

locusxt ⋅ 2013/12/07 ⋅ 0

topcoder Single Round 624(500)

题目 Problem Statement Byteland is a city with many skyscrapers, so it's a perfect venue for BASE jumping. Danilo is an enthusiastic BASE jumper. He plans to come to Byteland an......

面码 ⋅ 2014/06/13 ⋅ 0

2015年2月份最佳的免费 UI 工具包

设计师们最喜欢 UI 工具包,这是一种思路拓展的方法,同时可以利用它们来解决各种复杂的项目,同时可用来了解其他设计师的风格。这里我们收集了最近这一个月一些最棒的 UI 工具包,简介就不再...

oschina ⋅ 2015/02/24 ⋅ 14

[CareerCup] 18.2 Shuffle Cards 洗牌

18.2 Write a method to shuffle a deck of cards. It must be a perfect shuffle—in other words, each of the 52! permutations of the deck has to be equally likely. Assume that you ......

机器的心脏 ⋅ 2017/12/14 ⋅ 0

一个查询结果集放到视图后查询很慢

mysql 数据库,一个很复杂的 查询比如 select from a left join b ...等 这个单独查询很快的 但是把他放到视图里 通过 select from 视图名 查询很慢 这个怎么解决 第三方平台只支持查询我们这...

zqb666 ⋅ 2014/07/23 ⋅ 1

决战Leetcode: easy part(51-96)

本博客是个人原创的针对leetcode上的problem的解法,所有solution都基本通过了leetcode的官方Judging,个别未通过的例外情况会在相应部分作特别说明。 欢迎互相交流! email: tomqianmaple@...

qq_32690999 ⋅ 02/09 ⋅ 0

Perfect:Swift 语言服务器端软件框架简介

Perfect:Swift 语言服务器端软件框架 Perfect 开源项目 参与 Perfect 开发 Slack 在线协同 Perfect:Swift 语言服务器端软件框架 Perfect是一组完整、强大的工具箱、软件框架体系和Web应用服...

rockford ⋅ 2017/11/29 ⋅ 0

Project Perfect让Swift在服务器端跑起来-引言(一)

编者语:今天是大年初一,先和大家简单说一句猴年快乐! 你认识Swift或者是在客户端,因为它是苹果用来开发客户端的新一代语言。在Swift开源后苹果让它不仅在MacOS/iOS上跑,也运行到了Linux...

微笑的江豚 ⋅ 2016/06/02 ⋅ 0

【新手】请教有关guess and check pattern的习题。

习题内容是:Use the guess and check pattern to determine if a triangle is a perfect triangle. A perfect triangle has side lengths that are multiples of 3, 4, and 5. Ask the user......

zrz_108 ⋅ 2014/11/22 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

zblog2.3版本的asp系统是否可以超越卢松松博客的流量[图]

最近访问zblog官网,发现zlbog-asp2.3版本已经进入测试阶段了,虽然正式版还没有发布,想必也不久了。那么作为aps纵横江湖十多年的今天,blog2.2版本应该已经成熟了,为什么还要发布这个2.3...

原创小博客 ⋅ 今天 ⋅ 0

聊聊spring cloud的HystrixCircuitBreakerConfiguration

序 本文主要研究一下spring cloud的HystrixCircuitBreakerConfiguration HystrixCircuitBreakerConfiguration spring-cloud-netflix-core-2.0.0.RELEASE-sources.jar!/org/springframework/......

go4it ⋅ 今天 ⋅ 0

二分查找

二分查找,也称折半查找、二分搜索,是一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于...

人觉非常君 ⋅ 今天 ⋅ 0

VS中使用X64汇编

需要注意的是,在X86项目中,可以使用__asm{}来嵌入汇编代码,但是在X64项目中,再也不能使用__asm{}来编写嵌入式汇编程序了,必须使用专门的.asm汇编文件来编写相应的汇编代码,然后在其它地...

simpower ⋅ 今天 ⋅ 0

ThreadPoolExecutor

ThreadPoolExecutor public ThreadPoolExecutor(int corePoolSize, int maximumPoolSize, long keepAliveTime, ......

4rnold ⋅ 昨天 ⋅ 0

Java正无穷大、负无穷大以及NaN

问题来源:用Java代码写了一个计算公式,包含除法和对数和取反,在页面上出现了-infinity,不知道这是什么问题,网上找答案才明白意思是负的无穷大。 思考:为什么会出现这种情况呢?这是哪里...

young_chen ⋅ 昨天 ⋅ 0

前台对中文编码,后台解码

前台:encodeURI(sbzt) 后台:String param = URLDecoder.decode(sbzt,"UTF-8");

west_coast ⋅ 昨天 ⋅ 0

实验楼—MySQL基础课程-挑战3实验报告

按照文档要求创建数据库 sudo sercice mysql startwget http://labfile.oss.aliyuncs.com/courses/9/createdb2.sqlvim /home/shiyanlou/createdb2.sql#查看下数据库代码 代码创建了grade......

zhangjin7 ⋅ 昨天 ⋅ 0

一起读书《深入浅出nodejs》-node模块机制

node 模块机制 前言 说到node,就不免得提到JavaScript。JavaScript自诞生以来,经历了工具类库、组件库、前端框架、前端应用的变迁。通过无数开发人员的努力,JavaScript不断被类聚和抽象,...

小草先森 ⋅ 昨天 ⋅ 0

Java桌球小游戏

其实算不上一个游戏,就是两张图片,不停的重画,改变ball图片的位置。一个左右直线碰撞的,一个有角度碰撞的。 左右直线碰撞 package com.bjsxt.test;import javax.swing.*;import j...

森林之下 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部