丑数
丑数
http://www.nowcoder.com/questionTerminal/6aa9e04fc3794f68acf8778237ba065b
丑数
- 第n个丑数肯定是第i个丑数乘以2,3或5得来的，1<=i<=n-1
- 考虑从前往后的动态规划求解丑数，假如已知前n-1个丑数，求解第n个丑数，那么三个指针p2,p3,p5,分别指向三个分别乘以2,3,5正好大于第n-1个丑数的丑数，求得三个乘积的最小值即为第n个丑数。
- 求出第n个丑数，最重要的是如何实现状态的转移，即p2,p3,p5的转移：将刚才贡献了第n个丑数的指针+1即可。分析：假设p2贡献了第n个丑数，那么(p2+1)乘以2肯定正好大于第n个丑数，而第n个丑数取的是三个乘积的最小值，所以也会 大于等于 第n个丑数，注意这里的大于等于，可能会存在两个指针都贡献了第n个丑数，那么两个指针都要加1
查看6道真题和解析