JZ-C-34

剑指offer第三十四题：丑数
  1 //============================================================================
  2 // Name        : JZ-C-34.cpp
  3 // Author      : Laughing_Lz
  4 // Version     :
  5 // Copyright   : All Right Reserved
  6 // Description : 丑数
  7 //============================================================================
  8 
  9 #include <iostream>
 10 #include <stdio.h>
 11 using namespace std;
 12 // ====================算法1的代码====================
 13 
 14 bool IsUgly(int number) {
 15     while (number % 2 == 0)
 16         number /= 2;
 17     while (number % 3 == 0)
 18         number /= 3;
 19     while (number % 5 == 0)
 20         number /= 5;
 21 
 22     return (number == 1) ? true : false;
 23 }
 24 
 25 int GetUglyNumber_Solution1(int index) {
 26     if (index <= 0)
 27         return 0;
 28 
 29     int number = 0;
 30     int uglyFound = 0;
 31     while (uglyFound < index) {
 32         ++number;
 33 
 34         if (IsUgly(number)) {
 35             ++uglyFound;
 36         }
 37     }
 38 
 39     return number;
 40 }
 41 
 42 // ====================算法2的代码====================
 43 
 44 int Min(int number1, int number2, int number3);
 45 
 46 int GetUglyNumber_Solution2(int index) {
 47     if (index <= 0)
 48         return 0;
 49 
 50     int *pUglyNumbers = new int[index];
 51     pUglyNumbers[0] = 1;
 52     int nextUglyIndex = 1;
 53 
 54     int *pMultiply2 = pUglyNumbers;
 55     int *pMultiply3 = pUglyNumbers;
 56     int *pMultiply5 = pUglyNumbers;
 57 
 58     while (nextUglyIndex < index) { //重点在这里
 59         int min = Min(*pMultiply2 * 2, *pMultiply3 * 3, *pMultiply5 * 5);
 60         pUglyNumbers[nextUglyIndex] = min;
 61 
 62         while (*pMultiply2 * 2 <= pUglyNumbers[nextUglyIndex])
 63             ++pMultiply2; //指针向后移一位，以确保下次判断Min(*pMultiply2 * 2, *pMultiply3 * 3, *pMultiply5 * 5)时候，会有比此次最小值还大的数 ？
 64         while (*pMultiply3 * 3 <= pUglyNumbers[nextUglyIndex])
 65             ++pMultiply3;
 66         while (*pMultiply5 * 5 <= pUglyNumbers[nextUglyIndex])
 67             ++pMultiply5;
 68 
 69         ++nextUglyIndex;
 70     }
 71 
 72     int ugly = pUglyNumbers[nextUglyIndex - 1];
 73     delete[] pUglyNumbers;
 74     return ugly;
 75 }
 76 
 77 int Min(int number1, int number2, int number3) {
 78     int min = (number1 < number2) ? number1 : number2;
 79     min = (min < number3) ? min : number3;
 80     return min;
 81 }
 82 
 83 // ====================测试代码====================
 84 void Test(int index, int expected) {
 85     if (GetUglyNumber_Solution1(index) == expected)
 86         printf("solution1 passed
");
 87     else
 88         printf("solution1 failed
");
 89 
 90     if (GetUglyNumber_Solution2(index) == expected)
 91         printf("solution2 passed
");
 92     else
 93         printf("solution2 failed
");
 94 }
 95 
 96 int main(int argc, char** argv) {
 97     Test(1, 1);
 98     Test(2, 2);
 99     Test(3, 3);
100     Test(4, 4);
101     Test(5, 5);
102     Test(6, 6);
103     Test(7, 8);
104     Test(8, 9);
105     Test(9, 10);
106     Test(10, 12);
107     Test(11, 15);
108     Test(1500, 859963392);
109     Test(0, 0);
110 
111     return 0;
112 }