【LeetCode】Math

[263] Ugly Number [Easy]

一个数的质因子只有2，3，5就叫丑数，写个函数判断丑数。

 1 //Author: Wanying
 2 //注意 0 和 1 的corner case， 你居然还没一次AC==
 3 //想好了再写，不然等着挂吧==！！！！！
 4 class Solution {
 5 public:
 6     bool isUgly(int num) {
 7         if (num == 0 || num == 1) {
 8             return num;
 9         }
10         while(num % 2 == 0) {
11             num = num / 2 ;
12         }
13         while(num % 3 == 0) {
14             num = num / 3;
15         }
16         while(num % 5 == 0) {
17             num = num / 5;
18         }
19         return num == 1;
20     }
21 };

View Code

[264] Ugly Number II [Medium]

第一个丑数是1，返回第n个丑数是多少。

思路：dp，第u个丑数一定是 min(vec[idx2]*2, vec[idx3]*3, vec[idx5] *5） || 所以，要存idx2，idx3，idx5，而且vec里面不能有重复的丑数.

 1 //Author: Wanying
 2 //DP: idx2, idx3, idx5
 3 
 4 class Solution {
 5 public:
 6     int nthUglyNumber(int n) {
 7         vector<int> vec(1,1);
 8         int idx2 = 0, idx3 = 0, idx5 = 0;
 9         for(size_t i = 2; i <= n; ++i) {
10             int v2 = vec[idx2] * 2, v3 = vec[idx3] * 3, v5 = vec[idx5] * 5;
11             int ith = min(v2, min(v3, v5));
12             if (ith == v2) {
13                 idx2++;
14             } 
15             if (ith == v3) {
16                 idx3++;
17             }
18             if (ith == v5) {
19                 idx5++;
20             }
21             vec.push_back(ith);
22         }
23         return vec[n-1];
24     }
25 };

View Code

[313] Super Ugly Number [Medium]

跟Ugly Number II类似，变化在于质因子不是[2,3,5]了，变成了透传进来的数组。所以思路就从用3个idx变成了用一个数组的idx，其他一样，注意bug-free.

 1 //Author: Wanying
 2 class Solution {
 3 public:
 4     int nthSuperUglyNumber(int n, vector<int>& primes) {
 5         vector<int> idx(primes.size(), 0);
 6         vector<int> ans(1, 1);
 7         for (size_t i = 2; i <= n; ++i) {
 8             int ith = INT_MAX;
 9             for (int j = 0; j < primes.size(); ++j) {
10                 int tmp = ans[idx[j]] * primes[j];
11                 ith = min(tmp, ith);
12             }
13             for (int j = 0; j < primes.size(); ++j) {
14                 int tmp = ans[idx[j]] * primes[j];
15                 if (ith == tmp) {
16                     idx[j] ++;
17                 }
18             }
19             ans.push_back(ith);
20         }
21         return ans[n-1];
22     }
23 };

View Code

[172] Factorial Trailing Zeroes [Easy]

给定一个数n，求出n!中结尾0的个数。

考虑到造成结尾0的，只有5*2的倍数，或者直接10， 100这种，所以，我们就用 n/5 得到n中5的个数，但是可能还有25,125这种含有不止一个5的情况，所以公式如下：

ans = n/5 + n/25 + n/125 + ......

n/5 是移除所有单个的5， n/25是移除多余的5，同理.....

 1 /*
 2  *    Author: Wanying
 3  *    Language: C++
 4  *    Date: 2017/03/11
 5  *    考虑到25, 125 这种数字中不止一个5， 所以公式如下： ans = n/5 + n/25 + n/125 + ...... 
 6  *    n/5 是移除所有单个的5， n/25是移除多余的5， 同理.....
 7 */
 8 class Solution {
 9 public:
10     int trailingZeroes(int n) {
11         int ans = 0;
12         long long  x = 5; //x一直乘5， int会溢出
13         while (n >= x) {
14             ans += n / x;
15             x *= 5;
16             //cout << x << " ";
17         }
18         return ans;
19     }
20 };

View Code

[166] Fraction to Recurring Decimal [Medium]

给两个数，分别代表分子，分母，求小数的表示形式，可能有循环节

Given numerator = 1, denominator = 2, return "0.5".
Given numerator = 2, denominator = 1, return "2".
Given numerator = 2, denominator = 3, return "0.(6)".

模拟竖式除法，用个map记录循环节，还是不懂的话，自己在草稿纸上写个 3/444 你就懂了：）

注意corner case， int可能越界，全用long long 表示

 1 /*
 2  * author: Wanying
 3  * Date: 2017/03/11
 4  * 思路就是模拟竖式除法，用个map记录循环节
 5  * company： google
 6 */
 7 
 8 class Solution {
 9 public:
10     string fractionToDecimal(int numerator, int denominator) {
11         long long n = numerator, d = denominator; //不能用int, corner case: n = INT_MIN, d = -1; 除完了越界
12         string ans = "";
13         if (n == 0) return "0";
14         if (n < 0 ^ d < 0) {
15             ans += "-";
16         }
17         n = abs(n), d = abs(d);
18         ans += to_string(n/d);
19         //能整除直接返回整数部分
20         if (n % d == 0) {
21             return ans;
22         }
23         ans += ".";
24         long long r = (n % d);  // 余数也要用 long long, 不然(-1, -2147483648) 这组会溢出
25         map<int, int> mp; //模拟竖式除法，找循环节
26         while (r) {
27             if (mp.count(r) > 0) {
28                 ans.insert(mp[r], "(");
29                 ans += ")";
30                 break;
31             }
32             mp[r] = ans.size();
33             cout << r << " ";
34             r *= 10;
35             ans += to_string(r/d);
36             r = r % d;
37         }
38         return ans;
39     }
40 };

View Code