wy的leetcode刷题记录_Day49

wy的leetcode刷题记录_Day49

声明

本文章的所有题目信息都来源于leetcode
如有侵权请联系我删掉!
时间：2022-11-22

前言

正式回归，不会像之前赶进度那样敷衍了…今天有一道hard题，感觉是可以模拟出来的，最后看题解用了二分搜索。

878. 第 N 个神奇数字

今天的每日一题是：878. 第 N 个神奇数字

题目介绍

一个正整数如果能被 a 或 b 整除，那么它是神奇的。

给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 1000000000+ 7 取模 后的值。

示例 1：
输入：n = 1, a = 2, b = 3
输出：2

示例 2：
输入：n = 4, a = 2, b = 3
输出：6

思路

方法一：暴力解法：写一个死循环然后从1开始一个一个给判断，直到满足条件的数有n个，然后退出循环返回答案，当然绝对超时了。。。
方法二：二分搜索：首先我们直到符合条件的数一定是a的倍数和b的倍数，但是其中一定有重复的部分我们要将重复的部分给拿掉，也就是n=x/a+x/b+x/c，其中c是a和b的最小公倍数，x是符合条件的那个数，解释一下x/a表示直到x能被a整除的数的个数。（这里x/a可能为小数的），而本题也是从小往大的数的有序搜索符合二分的定义，接下来我们就要寻找一个边界，首先我们的左边界肯定是0，而右边界我们就用n*min(a,b)来表示，仔细想一想如果ba那么在这个范围内肯定是由大于n个满足条件的数，如果b>na那么就刚刚好有n个满足条件的数。接下来就跟二分搜索一样了。
暴力解法：

class Solution {
public:
    int nthMagicalNumber(int n, int a, int b) {
        int mod=1000000007;
        int ans=0;
        for(int i=1;;i++)
        {

            if(i%a==0||i%b==0)
                n--;
            if(n==0)
            {
                ans=i;
                break;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二分搜索：

class Solution {
public:
    const int MOD = 1e9 + 7;
    int nthMagicalNumber(int n, int a, int b) {
        long long l = min(a, b);
        long long r = (long long) n * min(a, b);
        int c = lcm(a, b);
        while (l <= r) {
            long long mid = (l + r) / 2;
            long long cnt = mid / a + mid / b - mid / c;
            if (cnt >= n) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return (r + 1) % MOD;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

收获

先根据暴力解法的缺点，然后通过算法来解决这些缺点。