【LeetCode】丑数题目合辑

这篇具有很好参考价值的文章主要介绍了【LeetCode】丑数题目合辑。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

263. 丑数

【LeetCode】丑数题目合辑,LeetCode刷题,leetcode,算法,职场和发展
【LeetCode】丑数题目合辑,LeetCode刷题,leetcode,算法,职场和发展
【LeetCode】丑数题目合辑,LeetCode刷题,leetcode,算法,职场和发展

思路

  • 首先,丑数必须是正整数,因此对于 n<1 都可以直接返回 false;
  • 对于 n >= 1 ,如果 n 能够被 2/3/5 整除,说明它们是丑数。

代码

class Solution {
public:
    bool isUgly(int n) {
        // ugly只能是正整数
        if(n < 1) return false;
        vector<int> factors = {2, 3, 5};
        for(int i=0; i<=2; ++i){
            while(n % factors[i] == 0){
                n /= factors[i];
            }
        }
        return n == 1;
    }
};

264. 丑数 II

【LeetCode】丑数题目合辑,LeetCode刷题,leetcode,算法,职场和发展
【LeetCode】丑数题目合辑,LeetCode刷题,leetcode,算法,职场和发展
【LeetCode】丑数题目合辑,LeetCode刷题,leetcode,算法,职场和发展

方法一:最小堆

思路

  • 要得到第 n 个丑数,可以使用最小堆实现。
  • 初始化堆为空,首先将最小的丑数 1 加入。每次取出堆顶元素 x ,则 x 是堆中最小的丑数,2x、3x、5x 必然也是丑数,因此将它们也加入最小堆。
  • 但是上述做法会出现重复元素,为了避免这种情况,用哈希集合去重,避免相同元素多次加入堆。
  • 在排除重复元素的情况下,第 n 次从最小堆中取出的元素即为第 n 个丑数。

代码

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> factor = {2, 3, 5};
        priority_queue<long, vector<long>, greater<long>> heap;
        unordered_set<long> s;
        // 先把丑数 1 加入
        s.insert(1L);
        heap.push(1L);
        long cur;
        for(int i=0; i<n; ++i){
            cur = heap.top();
            heap.pop();
            for(int f : factor){
                // 依次计算 2x 3x 5x
                long temp = cur * f;
                // s中没有temp 将其存入
                if(!s.count(temp)){
                    s.insert(temp);
                    heap.push(temp);
                }
            }
        }
        return (int)cur;
    }
};

方法二:动态规划(三指针法)

思路

  • 方法一使用最小堆,会预先存储较多的丑数,维护最小堆的过程也导致时间复杂度较高。可以使用动态规划的方法进行优化。

  • 定义数组 dp,其中 dp[i] 表示第 i 个丑数,则 dp[n] 为这道题的答案。其中,dp[1] = 1。

  • 剩余的丑数我们可以通过三个指针 p2 、p3、p5 计算得到。pi 的含义是有资格同 i 相乘的最小丑数的位置。这里资格指的是:如果一个丑数nums[pi]通过乘以 i 可以得到下一个丑数,那么这个丑数nums[pi]就永远失去了同 i 相乘的资格,我们把pi++,让 nums[pi] 指向下一个丑数即可。

  • 举例说明:

    一开始,丑数只有{1},1 可以同 2,3,5相乘,取最小的 1×2=2 添加到丑数序列中。

    现在丑数中有{1,2},在上一步中,1 已经同 2 相乘过了,所以今后没必要再比较 1×2 了,因此认为 1 失去了同 2 相乘的资格。

    现在 1 有与 3,5 相乘的资格,2 有与 2,3,5 相乘的资格,但是 2×3 和 2×5 肯定比 1×3 和 1×5 大,因此没必要比较。所以我们只需要比较 1×3,1×5,2×2

    依此类推,每次我们都分别比较有资格同 2,3,5 相乘的最小丑数,选择最小的那个作为下一个丑数,假设选择到的这个丑数是同 i(i=2,3,5)相乘得到的,所以它失去了同 i 相乘的资格,把对应的pi++,让 pi 指向下一个丑数即可。

代码

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> dp(n+1);
        dp[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for(int i=2; i<=n; ++i){
            int num2 = 2 * dp[p2];
            int num3 = 3 * dp[p3];
            int num5 = 5 * dp[p5];
            dp[i] = min(min(num2, num3), num5);
            // 确定dp[i]是由哪个数字生成的
            if(dp[i] == num2)   p2++;
            if(dp[i] == num3)   p3++;
            if(dp[i] == num5)   p5++;
        }
        return dp[n];
    }
};

1201. 丑数 III

【LeetCode】丑数题目合辑,LeetCode刷题,leetcode,算法,职场和发展

【LeetCode】丑数题目合辑,LeetCode刷题,leetcode,算法,职场和发展
【LeetCode】丑数题目合辑,LeetCode刷题,leetcode,算法,职场和发展

方法:二分查找 + 容斥原理

思路

  • 首先要注意的是,这道题和前两题对于“丑数”的定义并不相同。这里不能直接枚举丑数 x(三指针法),因为 x 太大了,会导致超时。

  • 这道题是 878. 第 N 个神奇数字 的升级版。把两个数改为了三个数,难度更高。与 878 题相比,这题的只需要修改求小于等于 x 的丑数个数的函数,二分查找部分一模一样。建议先复习 878 题,下面附上该题的思路图。

    【LeetCode】丑数题目合辑,LeetCode刷题,leetcode,算法,职场和发展

  • 把小于等于 x 的 a 的倍数、b 的倍数、c 的倍数组成的集合分别叫做 A、B、C ,小于等于 x 的丑数相当于集合 A∪B∪C ,集合的元素个数为 ∣A∪B∪C∣,由 容斥原理可得:

    ∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣

  • 因此,小于等于 x 的丑数的个数为:x/a + x/b + x/c - x/lcm_a_b - x/lcm_b_c - x/lcm_a_c + x/lcm_a_b_c 。可以使用最小公倍数函数 std::lcm

  • 接下来通过二分搜索,不断缩小边界,直到某个位置所对应的数恰好包含了 n 个丑数因子为止。

代码

class Solution {
public:
    using ll = long long;
    ll nthUglyNumber(ll n, ll a, ll b, ll c) {
        ll lcm_a_b = std::lcm(a, b), lcm_a_c = std::lcm(a, c), lcm_b_c = std::lcm(b, c);
        ll lcm_a_b_c= std::lcm(lcm_a_b, c);
        // 最小的丑数必然是a、b、c的最小值
        ll left = min(min(a, b), c);
        ll right = n * left;
        while(left + 1 < right){
            ll mid = (left + right) / 2;
            if(mid/a + mid/b + mid/c - mid/lcm_a_b - mid/lcm_a_c - mid/lcm_b_c + mid/lcm_a_b_c < n){
                left = mid;
            }
            else right = mid;
        }
        return right;
    }
};

313. 超级丑数

【LeetCode】丑数题目合辑,LeetCode刷题,leetcode,算法,职场和发展
【LeetCode】丑数题目合辑,LeetCode刷题,leetcode,算法,职场和发展
【LeetCode】丑数题目合辑,LeetCode刷题,leetcode,算法,职场和发展

方法:“多路归并”

思路

  • 这道题其实是 264. 丑数 II 的进阶,前者固定使用三个指针,分别对应于 2、3、5,而这道的primes数组长度不固定,因此使用指针数组来对应 primes 的每一个值。

  • 第一个丑数一定是 1,而「往后产生的丑数」都是基于「已有丑数」而来(使用「已有丑数」乘上「给定质因数」primes[i] )。具体过程如图所示。

    【LeetCode】丑数题目合辑,LeetCode刷题,leetcode,算法,职场和发展文章来源地址https://www.toymoban.com/news/detail-646723.html

    • 显然,我们需要每次取值最小的一个,然后让指针后移(指向下一个丑数),不断重复这个过程,直到找到第 n 个丑数。
    • 另外,由于我们每个指针移动和 dp的构造,都是单调递增,因此可以通过与 dp[i-1] 进行比较来实现去重,而无须引用 Set 结构。

代码

class Solution {
public:
    long nthSuperUglyNumber(int n, vector<int>& primes) {
        int len = primes.size();
        // 指针数组
        vector<long> ptr(len, 1);
        vector<long> dp(n+1, 0);
        dp[1] = 1;
        for(int i=2;i<=n;++i){
            int flag = 0;
            dp[i] = primes[0] * dp[ptr[0]];
            for(int j=0; j<len; ++j){
                long cur = primes[j] * dp[ptr[j]];
                if(cur < dp[i]){
                    flag = j;
                    dp[i]= cur;
                }     
            }
            ptr[flag]++;
            // 如果当前值和上一个丑数一样,那么跳过该丑数
            if(dp[i] == dp[i-1]) i--;
        
        }
        return dp[n];
    }
};

总结

  • 以上是丑数的所有相关题目,丑数的定义并不固定,因此需要仔细理解题意后再开始计算。
  • 对于 263. 丑数,运用简单的数学思想即可解决;
  • 对于264. 丑数II ,使用了最小堆动态规划(即三指针的方法),但是最小堆的方法比较费时,更推荐方法二;
  • 对于1201. 丑数III ,与一般的丑数定义不同,是 878. 第 N 个神奇数字 的升级版,使用了二分查找容斥原理
  • 对于313.超级丑数 ,是 264. 丑数II 的升级版,将三指针方法扩展为多指针即可求解,也可以理解为多路归并法

参考资料

  1. 丑数 II 官方题解
  2. 三指针方法的理解方式
  3. 313. 超级丑数:【宫水三叶】一题双解 :「优先队列」&「多路归并」

到了这里,关于【LeetCode】丑数题目合辑的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • leetcode算法刷题——链表

    题意:删除链表中等于给定值 val 的所有节点。 示例 1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 示例 2: 输入:head = [], val = 1 输出:[] 示例 3: 输入:head = [7,7,7,7], val = 7 输出:[] 在链表类中实现这些功能: get(index):获取链表中第 index 个节点的值。如果索引无效,

    2024年02月21日
    浏览(47)
  • 【贪心算法】leetcode刷题

    贪心算法无固定套路。 核心思想:先找局部最优,再扩展到全局最优。 两种思路: 1、从大到小。局部最优就是大饼干喂给胃口大的,充分利用饼干尺寸喂饱一个,全局最优就是喂饱尽可能多的小孩。 先遍历的胃口,在遍历的饼干 2、从小到大。 小饼干先喂饱小胃口 。两个

    2024年02月14日
    浏览(50)
  • LeetCode264. 丑数 II(相关话题:多重指针动态规划)

    给你一个整数  n  ,请你找出并返回第  n  个  丑数  。 丑数  就是质因子只包含  2 、 3  和  5  的正整数。 示例 1: 示例 2: 提示: 1 = n = 1690 动态规划数组:dp 数组用于存储从第 1 个到第 n 个丑数。dp[0] 初始化为 1,因为第一个丑数定义为 1。 三个指针:p2、p3、p5 分

    2024年01月20日
    浏览(43)
  • Leetcode 313: Super Ugly Number (超级丑数)

    Super Ugly Number Medium A super ugly number is a positive integer whose prime factors are in the array primes. Given an integer n and an array of integers primes, return the nth super ugly number. The nth super ugly number is guaranteed to fit in a 32-bit signed integer. Example 1: Input: n = 12, primes = [2,7,13,19] Output: 32 Explanation: [1,2,4,7,8,13,14

    2024年02月07日
    浏览(28)
  • 算法刷题记录-树(LeetCode)

    思路(DFS 中序遍历) 考虑中序遍历的性质即可 代码 思路(DFS) 对于一个节点是否删除,有如下几种情况: 思路(DFS) 首先,需要通过dfs算法找到从原点到目标点的路径。 p a t h = [ 2 , 3 , 5 , 7 ] path=[2,3,5,7] p a t h = [ 2 , 3 , 5 , 7 ] , k = 2 k=2 k = 2 。其中7为目标点然后考虑对路径的每一节

    2024年02月09日
    浏览(47)
  • 【Leetcode刷题】算法:罗马数字转整数

    定义一个 Solution 类,该类包含一个 romanToInt 方法用于将罗马数字转换为整数。 初始化变量 answer 为 0,用于保存转换后的整数值。 获取输入字符串 s 的长度,并保存在变量 length 中。 创建一个字典 d,将每个罗马数字字符与对应的数值进行映射。 使用 for 循环遍历 s 中的每个

    2024年02月05日
    浏览(92)
  • LeetCode高频算法刷题记录4

    题目链接:https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/ 参考题解:https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/solution/er-cha-shu-de-zui-jin-gong-gong-zu-xian-by-leetc-2/ 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“

    2024年02月06日
    浏览(60)
  • 数据结构算法leetcode刷题练习(1)

    给定一个三角形 triangle ,找出自顶向下的最小路径和。 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标

    2023年04月24日
    浏览(54)
  • 算法刷题记录-双指针/滑动窗口(LeetCode)

    思路 根据题目描述,我们可以知道,如果要将某个单词定义为可扩张(stretchy),需要满足如下两个条件: 所以,我们在实现的时候,可以通过两个指针p1和p2,分别指向s和word,分别统计连续的相同字符数量c1和c2,然后再通过上述的两个条件进行判断,即:如果 则表示该单

    2024年02月09日
    浏览(43)
  • Java算法 leetcode简单刷题记录6

    环和杆: https://leetcode.cn/problems/rings-and-rods/ 统计范围内的元音字符串数: https://leetcode.cn/problems/count-the-number-of-vowel-strings-in-range/ 最长平衡子字符串: https://leetcode.cn/problems/find-the-longest-balanced-substring-of-a-binary-string/ K 个元素的最大和: https://leetcode.cn/problems/maximum-sum-with-exa

    2024年01月24日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包