LeetCode 1390. 四因数_Michael阿明的博客-程序员宝宝

技术标签: LeetCode  

1. 题目

给你一个整数数组 nums,请你返回该数组中恰有四个因数的这些整数的各因数之和。

如果数组中不存在满足题意的整数,则返回 0 。

示例:
输入:nums = [21,4,7]
输出:32
解释:
214 个因数:1, 3, 7, 21
43 个因数:1, 2, 4
72 个因数:1, 7
答案仅为 21 的所有因数的和。
 
提示:
1 <= nums.length <= 10^4
1 <= nums[i] <= 10^5

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/four-divisors
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

  • 直接模拟从2到 n/2,当n很大的时候很耗时
class Solution {
    
public:
    int sumFourDivisors(vector<int>& nums) {
    
        int sum = 0;
        pair<bool,int> p;
        for(int i = 0; i < nums.size(); ++i)
        {
    
        	p = isfour(nums[i]);
            if(p.first)
                sum += p.second;
        }
        return sum;
    }

    pair<bool, int> isfour(int &n)
    {
    
    	if(n == 1)
    		return {
    false, 0};
    	int count = 2;
    	int divs = 1+n;
    	for(int i = 2; i <= n/2; ++i)
    	{
    
    		if(n%i == 0)
    		{
    
    			count++;
    			divs += i;
            }
    		if(count > 4)
    			return {
    false,0};
    	}
    	return {
    count==4,divs};
    }
};

在这里插入图片描述

  • 由于因数成对出现,所以从2遍历到 n \sqrt{n} n 即可
  • 注意一对因数是相同的情况
class Solution {
    
public:
    int sumFourDivisors(vector<int>& nums) {
    
        int sum = 0;
        pair<bool,int> p;
        for(int i = 0; i < nums.size(); ++i)
        {
    
        	p = isfour(nums[i]);
            if(p.first)
                sum += p.second;
        }
        return sum;
    }

    pair<bool, int> isfour(int &n)
    {
    
    	if(n == 1)
    		return {
    false, 0};
    	int count = 2;
    	int divs = 1+n;
    	for(int i = 2; i <= sqrt(n); ++i)
    	{
    
    		if(n%i == 0)
    		{
    
                if(i != n/i)
    			{
    
                    count += 2;
    			    divs += i+n/i;
                }
                else
                {
    
                    count += 1;
                    divs += i;
                }
            }
    		if(count > 4)
    			return {
    false,0};
    	}
    	return {
    count==4,divs};
    }
};

在这里插入图片描述

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_21201267/article/details/105033772

智能推荐

SpringCloud之Hystrix、Turbine的进阶使用及线上实战_瘦子没有夏天的博客-程序员宝宝

SpringCloud之Hystrix的进阶及线上实战使用上一小节我们了解Hystrix的基本概念和集成Feign的使用,在这小节中我们将学习Hystrix的高级用法和实际项目中需要使用的技术点。一、Hystrix DashboardHystrix Dashboard仪表盘是根据系统一段时间内发生的请求情况来展示的可视化面板,这些信息是每个HystrixCommand执行过程中的信息,这些信...

适应刘海屏_壮壮小朋友的博客-程序员宝宝

///////适应刘海屏变量phoneHeight: getApp().globalData.phoneHeight,样式 :style="{marginTop:phoneHeight+'px'}"

Kernel启动流程源码解析 9 sched_init_xichangbao的博客-程序员宝宝_sched_init(void)

一 sched_init这里只是简单过了一下sched_init,收集一些疑问,以后看书或阅读代码的时候再来寻找答案。1.0 sched_init定义在kernel/sched/core.c中void __init sched_init(void){    int i, j;    unsigned long alloc_size = 0,

夜神安卓模拟器adb命令详解_风抽过的烟头的博客-程序员宝宝_夜神adb

一、如何找到adb? 安装夜神安卓模拟器后,电脑桌面会有“夜神模拟器”的启动图标,鼠标右键--打开文件所在的位置,就会进入***\Nox\bin,比如小编的路径是C:\Program Files (x86)\Nox\bin,然后可以在该路径下找到nox_adb.exe二、如何连接设备? 首先需要进入\Nox\bin路径的cmd窗口,如何进入? 方式一:继续上述的步骤,进入\Nox\bin目录,然后按Shift键的同时,单击鼠标右键,就会看到“在此处打开命令窗口(W)”,点击...

Microsoft Visual Studio 2005 简体中文专业版(DVD)下载地址_weixin_30900589的博客-程序员宝宝

Microsoft Visual Studio 2005 简体中文专业版(DVD)下载地址 Microsoft Visual Studio 2005 简体中文专业版(DVD)http://www.sooweb.net/Soft/System-Utilities/Developer-Tools/1094.html试过了,能下载。在相关链接里还有M...

Python资源大全_云空的博客-程序员宝宝_python资源大全

Python资源Python 3.7.4 文档:https://docs.python.org/zh-cn/3.7/ 快速安装模块:pip3 install PyQt5 -i https://pypi.tuna.tsinghua.edu.cn/simple python开源项目及示例代码:https://www.cnblogs.com/dpf-learn/p/8053043....

随便推点

Python廖雪峰教程学习笔记:Day10_Comme_moik的博客-程序员宝宝

前言养成一个好的习惯只需要坚持21天,Day10获取对象信息判断对象类型,可以使用type()函数:type(123)# &lt;class 'int'&gt;type('apple')# &lt;class 'str'&gt;type(None)# &lt;type(None) 'NoneType'&gt;如果一个变量指向函数或者类,也可以用type()函数来判断:typ...

JSON.parse转换碰到换行符_Mr-K的博客-程序员宝宝

JSON.parse(),可以将字符串转换成对象,当改字符串中出现换行符'\'的时候,则会报错默认解析双'\\'为换行符,单'\'则会报错

Android 四大组件 之 Service_苍猫不是猫的博客-程序员宝宝

子曰:温故而知新,可以为师矣。 《论语》-- 孔子一、 简介Android 四大组件之一,特点是无需界面,用于在后台处理耗时的操作或长期任务。甚至在程序退出的情况下,我们也可以让 Service 在后台继续保持运行状态。二、 生命周期先来一张经典的图:从图上分析:Service 的生命周期会根据启动方式的不同有不同的生命周期回调。startService 和 bindSe...

python柱状图zzt_Python torch.diag方法代碼示例_weixin_39714015的博客-程序员宝宝

本文整理匯總了Python中torch.diag方法的典型用法代碼示例。如果您正苦於以下問題:Python torch.diag方法的具體用法?Python torch.diag怎麽用?Python torch.diag使用的例子?那麽恭喜您, 這裏精選的方法代碼示例或許可以為您提供幫助。您也可以進一步了解該方法所在模塊torch的用法示例。在下文中一共展示了torch.diag方法的29個代碼示...

xmanager5连接CENTOS6_weixin_33935505的博客-程序员宝宝

首先检查下系统版本[[email protected] ~]# cat /etc/issueCentOS release 6.5 (Final)Kernel \r on an \m一、若未安装桌面,先安装下桌面环境安装X Windows System:1验证可以安装的组件#yum grouplist2 安装X Windows System [[email protected] ~]# yum groupinstall ...

Visual Studio 远程调试编译开发树莓派程序(15.17.19版本) 笔记_一心只想搞钱的博客-程序员宝宝

树莓派(Linux)下的纯命令行开发调试,对于我这样的新手来说效率有些低。据说有个叫交叉编译器的神器,让我们可以在Windows下使用VS进行编辑、编译、调试或运行,最后在Linux下运行。而且运行大神们给的代码时,那些Makefile看着都头大,别说要我编写。 再次据说VS名下的插件VisualGDB神器可以帮我们把Linux下那些繁琐的工作(写Makefile、输入命令编译、使用命令调试等...

推荐文章

热门文章

相关标签