企业官网建设流程全解析

建设银行网站查询房贷信息查询,自己建一个网站需要什么,html布局模板,网站播放大视频如何做题目链接#xff1a;1390. 四因数#xff08;中等#xff09; 算法原理#xff1a; 解法#xff1a;记忆化枚举 28ms击败55.70% 时间复杂度O(n √M) 对于一个数n最暴力的方法就是从1开始枚举到n#xff0c;然后统计它有多少个因数#xff0c;再进行累加#xff0c;但这…题目链接1390. 四因数中等算法原理解法记忆化枚举28ms击败55.70%时间复杂度O(n × √M)对于一个数n最暴力的方法就是从1开始枚举到n然后统计它有多少个因数再进行累加但这样的话时间复杂度会飙升到O(N²)即使通过也会超时的所以咱们可以在上面那个基础上逐渐优化①咱只需找俩因数即可因为一个数至少有俩因数1和它本身这就已经是俩因数了因此咱们只需在它俩中间再找俩即可所以逐个枚举时就可以从2开始枚举到n-1即可②咱只需找一次因数即可因为因数一定是成对出现的比如说针对21枚举到3时会出现21÷37这里3是21的因数但同时7也是21的因数因此咱们找一次因数即可但这里有个细节比如说针对16枚举到4时会出现16÷44但4只能算一个因数因此这时累加时只能加一个鉴于以上分析我们就没必要从2遍历到n-1了因为会算重复所以咱们只需要遍历一半即可即从2开始枚举到√n这是时间复杂度的一个巨大的优化③备忘录优化由于同一个数可能重复出现因此当这个数第一次出现的时候就存进哈希表下次遍历的时候就没必要重新算一遍了答疑Q1如果出现两个相同的因数的话那么只能算一次吧加上只能成为奇数啊但是咱们要求的是4因数是偶数因数相同的时候咱就没必要算了啊直接跳过呗不可以虽然不会少算但会多算比如16的因数是1、2、4、8、16如果直接把4跳过会把16也算成四因数的数导致结果偏大Java代码class Solution { public int sumFourDivisors(int[] nums) { int ret0; //建立备忘录 MapInteger,Integer hashnew HashMap(); for(int x:nums){ //先往备忘录里瞅瞅 if(hash.containsKey(x)){ rethash.get(x); continue; } int count0,sum0; for(int i2;iMath.pow(x,0.5);i){ if(x%i0i!x/i){ count2; sum(ix/i); }else if(x%i0ix/i){ count; sumi; } if(count2) break; } if(count2){ hash.put(x,x1sum); ret(x1sum); } } return ret; } }