题解 | #丑数#

动态规划典型应用
思路：我想构造当前丑数，那么必然得通过某个丑数乘2或某个丑数乘3或某个丑数乘5来得到
---------那么，就用三个指针指向这最小的可用的这三种丑数

if (index < 7) {
            return index;
        }
        int[] res = new int[index];
        res[0] = 1;
        //开三个指针指向，每个丑数能有三次机会用来构造新的丑数，指针指向最新的能被使用该机会的丑数。如乘2的机会用完，pos2指针就得指向下一个丑数
        //结果而言，每个丑数都得被三个指针指一次，指针分别指向最小的可取的用来乘2、3、5的丑数
        int pos2 = 0;// 表示能通过当前指针所指乘2构造新的丑数
        int pos3 = 0;// 表示能通过当前指针所指乘3构造新的丑数
        int pos5 = 0;// 表示能通过当前指针所指乘5构造新的丑数
        // 一个丑数*2/3/5还是丑数
        System.out.print(1+" ");
        for (int i = 1; i < index; i++) {
            res[i] = Math.min(Math.min(res[pos2] * 2, res[pos3] * 3), res[pos5] * 5);
            System.out.print(res[i]+" ");
            if (res[i] == res[pos2] * 2) {
                pos2++;
            }
            if (res[i] == res[pos3] * 3) {
                pos3++;
            }
            if (res[i] == res[pos5] * 5) {
                pos5++;
            }
        }
        return res[index - 1];
    }