标签: Math

评分 0, 满分 5 星
0 票

最初的想法:判断当前线段与它前面第3条或者第5条线段是否相交,相交会发生在横线和竖线之间,3、5分别对应收缩型和扩张型的结构。这时漏掉了2、1、2、1、1这种同为竖线的情况,因此又在代码中加上了与前面第4条是否相交的判断。时空复杂度均满足题目要求,但是判线段是否相交使用了叉乘等计算几何中常用的算法,因此代码较长。

评分 5.00, 满分 5 星
1 票

假设a[n - 1]表示第n个这样的数,则a[0] = 1,显然,更大的丑数只能由小的丑数通过乘以2,3,5得到。维护三个头指针,一个尾指针,头指针h1,h2,h3分别指向a[h1],a[h2],a[h3]分别乘以2,3,5能够比目前得到的最大丑数稍大的最小丑数,尾指针则指向目前最大的丑数。显然,如果乘积小于最大的丑数,那就将头指针后移,否则选择三个值中最小的那个加入队尾,直到尾指针到达目标。

评分 0, 满分 5 星
0 票

可以果断的判断,在上百次迭代后,如果答案没有收敛到1,就可以排除这个数字了。

Comments Off on [LeetCode]Happy Number

评分 0, 满分 5 星
0 票

不申请额外的空间,只能每次取数字的首尾比较了。

Comments Off on [LeetCode]Palindrome Number

评分 5.00, 满分 5 星
2 票

题目传送。给定N(3 <= N <= 8000)个顶点的多边形P,积分区域D = \{(x, y) | (x, y) in P\},求解\iint_{D} (x + y)\mathrm{d}x\mathrm{d}y。好纯粹的数学题!首先,粗略地回顾了下二重积分,看到这样一个问题:假设有一薄平面,占有xoy平面上的闭区域D,点(x, y)处的面密度为\rho(x, y),假定\rho(x, y)D上连续,求薄平面的质量。