服务器ip做网站,衡阳网站优化,建筑网建设通官网,增加wordpress插件今天看剑指offer的时候碰到了“丑数”这个问题#xff0c;说这个“丑数”#xff0c;常规的情况是#xff0c;一般人碰到这个问题会感觉到无从下手#xff0c;为什么呢#xff1f;因为从一般人的角度来看#xff0c;比如2乘以2.3.5分别为4、6、10,3乘以2.3.5的话为6、9、…今天看剑指offer的时候碰到了“丑数”这个问题说这个“丑数”常规的情况是一般人碰到这个问题会感觉到无从下手为什么呢因为从一般人的角度来看比如2乘以2.3.5分别为4、6、10,3乘以2.3.5的话为6、9、15两个结果中有交叉的部分 接下来就想建立一个存储结构将生成的这些丑数都保存进来于是想会不会有一种数据结构能够支持查找数据结构中的元素呢在O(1)的复杂度里找到这个元素是否存在于这个数据结构里换句话来说我想用哈希的思想但是又碍于空间的消耗 想走一个捷径。。于是。。百思不得其解 看了书上给的解法收到了启发思路很简单我们换种丑数的计算方式不是靠“插入”这种操作而是根据之前的数组里的东西“生成”丑数丑数的生成因子只有2、3和5那么我们可以保存三个index下标分别为2、3、5在已生成的丑数中寻找下标寻找这个下标对应的丑数乘以各自的生成因子后第一个大于已有丑数中的最大值分别保存这三个下标并从生成的三个数中找到最小的添加到丑数的末尾以此循环生成丑数。 根据此思想写出的代码如下 #includeiostream#includevectorint min(int x,int y){ int min; x y ? min y : min x; return min;}void generate_ugly(int *ugly,int length,int T2,int T3,int T5){ int max ugly[length-1]; int i; for(iT2;ilength;i) { if(ugly[i]*2 ugly[length-1]) { T2 i; break; } } for(iT3;ilength;i) { if(ugly[i]*3 ugly[length-1]) { T3 i; break; } } for(iT5;ilength;i) { if(ugly[i]*5 ugly[length-1]) { T5 i; break; } } ugly[length] min(min(ugly[T2]*2,ugly[T3]*3),ugly[T5]*5);}using namespace std;int main(){ int ugly[1500]{1,2,3,4,5}; int i,length5,T2,T3,T5; for(i0;ilength;i) { if(ugly[i]*2 ugly[length-1]) { T2 i; break; } } for(i0;ilength;i) { if(ugly[i]*3 ugly[length-1]) { T3 i; break; } } for(i0;ilength;i) { if(ugly[i]*5 ugly[length-1]) { T5 i; break; } } for(i0;i1495;i) { generate_ugly(ugly,length,T2,T3,T5); length; } cout ugly[1499] endl; system(pause); return 0; } 看到结果的时候担心了一下说这int类型会不会溢出 于是lz很小白的去网上查找了int类型的表示范围和编译器的位数有关。比如说32位的编译器int类型的表示范围为2^32 -1 ~ - 2^32 。转载于:https://www.cnblogs.com/xiawen/archive/2013/04/15/3022095.html
