剑指offer第三十四题：丑数
1 //============================================================================ 2 // Name : JZ-C-34.cpp 3 // Author : Laughing_Lz 4 // Version : 5 // Copyright : All Right Reserved 6 // Description : 丑数 7 //============================================================================ 8 9 #include10 #include 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\n"); 87 else 88 printf("solution1 failed\n"); 89 90 if (GetUglyNumber_Solution2(index) == expected) 91 printf("solution2 passed\n"); 92 else 93 printf("solution2 failed\n"); 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 }