- 思路1
出错代码:
class Solution
{
public:
int nthUglyNumber(int n)
{
if(n == 1)
{
return 1;
}
int i = 1;
int flag = 1;
while(1)
{
i++;
if(isUgly(i))
{
flag++;
}
if(flag == n)
{
break;
}
}
return i;
}
private:
bool isUgly(int n)
{
vector<int> nums;
if(n == 3 || n == 5 || n == 2)
{
return true;
}
while(n)
{
nums.push_back(n % 10);
n = n / 10;
}
if(nums[0] == 5 || nums[0] == 0)
{
//可以被5整除
return isUgly(n / 5);
}
else if(is3Divisible(nums))
{
return isUgly(n / 3);
}
else
{
//能被2整除
return isUgly(n / 2);
}
return false;
}
bool is3Divisible(vector<int>& nums)
{
int sum = 0;
for(int i = 0;i < nums.size();i++)
{
sum = sum + nums[i];
}
if((sum % 3) == 0)
{
return true;
}
else
{
return false;
}
}
};
这次出错出在了
bool isUgly(int n)
{
vector<int> nums;
int number = n;
if (n == 3 || n == 5 || n == 2)
{
return true;
}
while (n)
{
nums.push_back(n % 10);
n = n / 10;
}
if (nums[0] == 5 || nums[0] == 0)
{
//可以被5整除
return isUgly(number / 5);
}
else if (is3Divisible(nums))
{
return isUgly(number / 3);
}
else
{
//能被2整除
return isUgly(number / 2);
}
return false;
}
code2 代码出错 出错在
else
{
//能被2整除
return isUgly(number / 2);
}
当number = 7
时可以测出这个bug。
code3 修改后的代码,果然不出我所料,超时了。跑了几个数据都通过了,但是当n = 218
时,leetcode提示Time Limit Exceeded
。
class Solution
{
public:
int nthUglyNumber(int n)
{
if (n == 1)
{
return 1;
}
int i = 1;
int flag = 1;
while (1)
{
i++;
if (isUgly(i))
{
flag++;
}
if (flag == n)
{
break;
}
}
return i;
}
private:
bool isUgly(int n)
{
vector<int> nums;
int number = n;
if (n == 3 || n == 5 || n == 2)
{
return true;
}
while (n)
{
nums.push_back(n % 10);
n = n / 10;
}
if (nums[0] == 5 || nums[0] == 0)
{
//可以被5整除
return isUgly(number / 5);
}
else if (is3Divisible(nums))
{
return isUgly(number / 3);
}
else if(is2Divisible(nums))
{
//能被2整除
return isUgly(number / 2);
}
return false;
}
bool is3Divisible(vector<int>& nums)
{
int sum = 0;
for (int i = 0; i < nums.size(); i++)
{
sum = sum + nums[i];
}
if ((sum % 3) == 0)
{
return true;
}
else
{
return false;
}
}
bool is2Divisible(vector<int>& nums)
{
if (nums[0] % 2 == 0)
{
return true;
}
else
{
return false;
}
}
};
再一次出错的代码
class Solution
{
public:
int nthUglyNumber(int n)
{
vector<int> ugly;
ugly.push_back(1);
int Multiply2 = 0;
int Multiply3 = 0;
int Multiply5 = 0;
int i2 = 0;
int i3 = 0;
int i5 = 0;
while (true)
{
if (n < ugly.size())
{
return ugly[n - 1];
}
else
{
Multiply2 = ugly[i2] * 2;
Multiply3 = ugly[i3] * 3;
Multiply5 = ugly[i5] * 5;
int min = GetMin(Multiply2, Multiply3, Multiply5);
ugly.push_back(min);
if (min == Multiply2)
{
i2++;
}
else if (min == Multiply3)
{
i3++;
}
else
{
i5++;
}
}
}
}
private:
int GetMin(int number1, int number2,int number3)
{
int min = (number1 < number2) ? number1 : number2;
min = (min < number3) ? min : number3;
return min;
}
};
n = 10
可以测出这个bug
最终AC版的code
class Solution
{
public:
int nthUglyNumber(int n)
{
vector<int> ugly;
ugly.push_back(1);
int Multiply2 = 0;
int Multiply3 = 0;
int Multiply5 = 0;
int i2 = 0;
int i3 = 0;
int i5 = 0;
while (true)
{
if (n < ugly.size())
{
return ugly[n - 1];
}
else
{
Multiply2 = ugly[i2] * 2;
Multiply3 = ugly[i3] * 3;
Multiply5 = ugly[i5] * 5;
int min = GetMin(Multiply2, Multiply3, Multiply5);
ugly.push_back(min);
if (min == Multiply2)
{
i2++;
}
if (min == Multiply3)
{
i3++;
}
if(min == Multiply5)
{
i5++;
}
}
}
}
private:
int GetMin(int number1, int number2,int number3)
{
int min = (number1 < number2) ? number1 : number2;
min = (min < number3) ? min : number3;
return min;
}
};