数字问题-LeetCode 263、264、274、275
数字问题-LeetCode 263、264、274、275
作者：TeddyZhang，公众号：算法工程师之路
1
编程题
【LeetCode #263】丑数
编写一个程序判断给定的数是否为丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
示例 1:
输入: 6 输出: true 解释: 6 = 2 × 3
解题思路：
思路挺简单的，就是对这个数整除 2 或者整除 3 或者整除 5，然后看最后是不是等于 1。如果不能够整除，那么就 不是丑数了！
class Solution {
public:
bool isUgly(int num) {
int d[] = {, , };
for(auto x: d){
while(num > && num % x == ){
num /= x;
}
}
return num == ;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/ugly-number
【LeetCode #264】丑数II
编写一个程序，找出第 n 个丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。
示例: 输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
解题思路：
一个丑数一定是另一个丑数乘以2或3或5得到的（1除外），那么dp数据就是储存前n个丑数，由于要按照 顺序来进行储存，因此，dp[i] = min(2 * dp[i2], 2 * dp[i3], 2 * dp[i5]);
class Solution {
public:
int nthUglyNumber(int n) {
vector<int> dp(n);
dp[] = ;
int i2 = , i3 = , i5 = , i = ;
while(i < n){
dp[i] = min( * dp[i2], min( * dp[i3], * dp[i5]));
if(dp[i] == * dp[i2]) i2++;
if(dp[i] == * dp[i3]) i3++;
if(dp[i] == * dp[i5]) i5++;
i++;
}
return dp[n-1];
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/ugly-number-ii
【LeetCode 274】H指数
给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。 h 指数的定义: “h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）至多有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数不多于 h 次。）”
示例: 输入: citations = [3,0,6,1,5] 输出: 3
解题思路：
题目有点难以理解，可以直接看图，如上图所示，绿色正方形的边长即为h的值。 因此，需要对引用次数进行排序处理，然后寻找citations[i]>=i+1的位置即可！
class Solution {
public:
int hIndex(vector<int>& citations) {
sort(citations.begin(), citations.end(), [=](int a, int b){
return a > b;
});
int res = ;
for(int i = ; i < citations.size(); i++){
if(citations[i] >= i+)
res++;
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/h-index
【LeetCode #275】h指数 II
给定一位研究者论文被引用次数的数组（被引用次数是非负整数），数组已经按照升序排列。编写一个方法，计算出研究者的 h 指数。 h 指数的定义: “h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）至多有 h 篇论文分别被引用了至少 h 次。（其余的 N - h 篇论文每篇被引用次数不多于 h 次。）"
示例: 输入: citations = [0,1,3,5,6] 输出: 3
解题思路：
使用274题的方法也可以解决这个问题，但在本题中给定了引用数是有序的！ 因此可以直接使用二分法来搜索上题图中正方形的边长！
class Solution {
public:
int hIndex(vector<int>& citations) {
int total = citations.size(), res = ;
for (int l = , r = total - ; l <= r;){
int mid = l + (r-l) / ;
if (citations[mid] >= total - mid){
res = total - mid;
r = mid - ;
} else{
l = mid + ;
}
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/h-index-ii