标签： 二分查找

LeetCode刷题【475】供暖器

2022 年 6 月 30 日 / / 0 Comments

冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。

在加热器的加热半径范围内的每个房屋都可以获得供暖。

现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。

说明：所有供暖器都遵循你的半径标准，加热的半径也一样。

 

示例 1:

输入: houses = [1,2,3], heaters = [2]
输出: 1
解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。

示例 2:

输入: houses = [1,2,3,4], heaters = [1,4]
输出: 1
解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。

示例 3：

输入：houses = [1,5], heaters = [2]
输出：3

 

提示：

  • 1 <= houses.length, heaters.length <= 3 * 104
  • 1 <= houses[i], heaters[i] <= 109
Related Topics
  • 数组
  • 双指针
  • 二分查找
  • 排序

  • 👍 406
  • 👎 0

    • 简单粗暴点的二分

    代码

    class Solution {
    public int findRadius(int[] houses, int[] heaters) {
        Arrays.sort(heaters);
        int ans = 0;
        for (int house : houses) {
            int l = 0;
            int r = heaters.length-1;
            int tmp = (int) 1e9+1;
            while (l<=r){
                int mid = (l + r)/2;
                //怕遗漏边缘情况不好处理就每次二分的结果都比较下
                tmp = Math.min(tmp, Math.abs(heaters[mid] - house));
                if (heaters[mid] > house){
                    r = mid-1;
                }else if (heaters[mid] < house){
                    l = mid+1;
                }else {
                    break;
                }
            }
            ans = Math.max(ans,tmp);
        }
        return ans;
    }
}

    LeetCode刷题【754】到达终点数字

    2022 年 6 月 30 日 / / 0 Comments

    在一根无限长的数轴上，你站在0的位置。终点在target的位置。

    你可以做一些数量的移动 numMoves :

    • 每次你可以选择向左或向右移动。
    • 第 i 次移动（从  i == 1 开始，到 i == numMoves ），在选择的方向上走 i 步。

    给定整数 target ，返回 到达目标所需的 最小 移动次数(即最小 numMoves ) 。

     

    示例 1:

    输入: target = 2
输出: 3
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 -1 。
第三次移动，从 -1 到 2 。

    示例 2:

    输入: target = 3
输出: 2
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 3 。

     

    提示:

    • -109 <= target <= 109
    • target != 0
    Related Topics
    • 数学
    • 二分查找

  • 👍 180
  • 👎 0

    • 数学分析计算

    如图

    1. 假设从左往右走了k次到达M点刚好越过或者达到target点，即k(k+1)/2 ≥ target
    2. 那么我们即需要再这之前往反方向移动距离为D
    3. 又，因为反向移动了，仍需掉头继续往这个方向移动，即假设我们往反向移动了的距离为x
    4. 那么我们就有了2x = D这样的结果，即反向移动加折回到原点0的距离就是我们原先应当到达M点，因为折返损耗了距离D而只能达到位置target的情况
    5. 即有，x = D/2，那么我们知道D必然需要为一个偶数，因为x必然是一个整数

    举个简单的例子
    target = 8
    那么我们知道 k = 4 的时候，能到达M点位置为10，测试相差距离D为2，即需要往反向移动x = D/2 = 1距离，那么我们就知道应当按照- 1 + 2 + 3 + 4 = 8的方法运行

    代码

    class Solution {
    public int reachNumber(int target) {
        if (target==0)return 0;
        target = Math.abs(target);
        int k = (int) Math.sqrt(2 * target);
        k--;
        while ((1 + ++k) * k / 2 < target){}
        int d = (1 + k) * k / 2 - target;
        while (d%2!=0) {
            d += ++k;
        }
        return k;
    }
}

    LeetCode刷题【878】第 N 个神奇数字

    2022 年 6 月 30 日 / / 0 Comments

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

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

     

    示例 1：

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

    示例 2：

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

     

    提示：

    • 1 <= n <= 109
    • 2 <= a, b <= 4 * 104

     

    Related Topics
    • 数学
    • 二分查找

  • 👍 100
  • 👎 0

    • 二分查找，最大公约数，最小公倍数
    三个必要知识

    gcd(long a, long b)求最大公约数 辗转相除法，
    lcm(long a, long b)求最小公倍数，
    二分查找

    从简单情况说起，设有一个数字i，从1到i过程中能整除a的数字有i/a个
    那么同样的能整除b的数字有i/b个
    能同时整除a和b的数字有i/lcm(a, b)个，lcm(a, b)为a``b的最小公倍数，

    那么我们就可以知道，数字n以下，符合题意的数字有n/a + n/b - n/lcm(a,b)个，需要减去多计数一遍的最小公倍数个数

    那么接下来就是用二分法来找到这个恰好能符合题意的数字

    代码

    class Solution {
    public int nthMagicalNumber(int n, int a, int b) {
        long mod = (long)(1e9 + 7);
        long l = 2;
        long r = (long) n * Math.min(a,b);
        while (l < r){
            long mid = l + ((r-l)>>1);
            if(f(a,b,mid) < n){
                l = mid + 1;
            }else{
                r = mid;
            }
        }
        return (int)(l % mod);
    }

    long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    long lcm(long a, long b) {
        return (a * b) / gcd(a, b);
    }

    long f(long a, long b, long x) {
        return (x / a) + (x / b) - (x / lcm(a, b));
    }
}

    LeetCode刷题【剑指 Offer 57】和为s的两个数字

    2022 年 6 月 29 日 / / 0 Comments

    输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

     

    示例 1：

    输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]

    示例 2：

    输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]

     

    限制：

    • 1 <= nums.length <= 10^5
    • 1 <= nums[i] <= 10^6
    Related Topics
    • 数组
    • 双指针
    • 二分查找

  • 👍 192
  • 👎 0

    • 哈希表，双指针，二分查找

    1. 哈希表
      这个哈希表有点大
      或者直接用HashSet也可以，性能甚至不如这个boolen[],我试过
    class Solution {
    public int[] twoSum(int[] nums, int target) {
        boolean[] hashSet = new boolean[2000000];
        for (int num : nums) {
            if (hashSet[target-num]){
                return new int[]{num,target-num};
            }
            hashSet[num] = true;
        }
        return new int[2];
    }
}
    1. 双指针
      从两边开始往中间找
    class Solution {
    public int[] twoSum(int[] nums, int target) {
        int l = 0;
        int r = nums.length-1;
        while ( l < r){
            int sum = nums[l] + nums[r];
            if(sum == target){
                return new int[]{nums[l],nums[r]};
            }
            if( sum < target){
                l++;
            }else{
                r--;
            }
        }
        return new int[]{nums[l],nums[r]};
    }
}
    1. 二分
    class Solution {
    public int[] twoSum(int[] nums, int target) {
        int i = -1;
        while (++i < nums.length){
            int s = binarySearch(nums,target- nums[i]);
            if (s >= 0 && i != s){
                return new int[]{nums[i],nums[s]};
            }
        }
        return new int[2];
    }

    int binarySearch(int[] nums, int t ){
        int l = 0;
        int r = nums.length;
        while (l < r){
            int mid = l + ((r-l) >> 1);
            if (nums[mid] == t){
                return mid;
            }
            if (nums[mid] > t){
                r = mid;
            }else{
                l = mid+1;
            }
        }
        return -1;
    }
}

    LeetCode刷题【面试题 10.10】数字流的秩

    2022 年 6 月 29 日 / / 0 Comments

    假设你正在读取一串整数。每隔一段时间，你希望能找出数字 x 的秩(小于或等于 x 的值的个数)。请实现数据结构和算法来支持这些操作，也就是说：

    实现 track(int x) 方法，每读入一个数字都会调用该方法；

    实现 getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数。

    注意：本题相对原题稍作改动

    示例:

    输入:
["StreamRank", "getRankOfNumber", "track", "getRankOfNumber"]
[[], [1], [0], [0]]
输出:
[null,0,null,1]

    提示：

    • x <= 50000
    • track 和 getRankOfNumber 方法的调用次数均不超过 2000 次
    Related Topics
    • 设计
    • 树状数组
    • 二分查找
    • 数据流

  • 👍 32
  • 👎 0

    • 树状数组结构直接套模板使用

    在该题中，树状数组对应下标表意为当前下标数字的出现次数

    1. track(int x) 方法，每读入一个数字都会调用该方法, 等价于在给树状数组对应下标数值加1，即当前下标出现次数加1
    2. getRankOfNumber(int x) 方法，返回小于或等于 x 的值的个数，等价于求下标0到当前下标的前缀和，即从0到当前下标的所有数字出现次数之和

    代码

    class StreamRank {

    private FenwickTree fenwickTree;


    public StreamRank() {
        fenwickTree = new FenwickTree(50001);
    }

    public void track(int x) {
        fenwickTree.add(x+1,1);
    }

    public int getRankOfNumber(int x) {
        return fenwickTree.query(x+1);
    }


    class FenwickTree{
        int[] arr;
        public FenwickTree(int num){
            arr = new int[num+1];
        }

        int lowBit(int x){
            return x & ( -x );
        }

        public void add(int idx, int num){
            while (idx < arr.length){
                arr[idx] += num;
                idx += lowBit(idx);
            }
        }

        public int query(int idx){
            int sum = 0;
            while (idx > 0){
                sum += arr[idx];
                idx -= lowBit(idx);
            }
            return sum;
        }
    }
}

    LeetCode刷题【400】第 N 位数字

    2022 年 6 月 29 日 / / 0 Comments

    给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。

     

    示例 1：

    输入：n = 3
输出：3

    示例 2：

    输入：n = 11
输出：0
解释：第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ，它是 10 的一部分。

     

    提示：

    • 1 <= n <= 231 - 1
    Related Topics
    • 数学
    • 二分查找

  • 👍 324
  • 👎 0

    • 同剑指Offer 44 题 数字序列中某一位的数字

    解题思路

    按图分析

    1. 0-9的时候都可以直接返回自己
    2. 10-99一共有90个数字，每个数字两个字符
    3. 100-999一共有900个数字，每个数字三个字符
    4. 1000-9999一共有9000个数字，每个数字四个字符
    5. 后续雷同

    按照这个规律分析，我们只需从头开始，依次从头开始

    1. 减去10个字符
    2. 减去90 * 2 个字符
    3. 减去900 * 3个字符
    4. 减去9000 * 4个字符
    5. 如果不够减了则从这一档的1 x 10^pow开始，

    问题

    1. 运算中间的值
     cur + 9 * powOf10 * ( pow+1 )

    会超过int型上限，所以最简单的处理办法中间的运算过程用了long型数据

    1. 取最后结果的某一位数字也可以用数学方法，不过偷懒了下直接转字符串了

    代码

    class Solution {
    public int findNthDigit(int n) {
        if (n < 10){
            return n;
        }
        long cur = 10;
        long powOf10 = 10;
        long pow = 1;
        while (cur + 9 * powOf10 * ( pow+1 )< n){
            cur += 9 * powOf10 * (pow+1);
            powOf10 *= 10;
            pow++;
        }
        long order = powOf10 + (n-cur) / (pow+1);
        long idx = (n - cur) % (pow+1);
        String orderStr = Long.toString(order);
        return orderStr.charAt((int)idx)-'0';
    }
}

    LeetCode刷题【786】第 K 个最小的素数分数

    2022 年 6 月 29 日 / / 0 Comments

    给你一个按递增顺序排序的数组 arr 和一个整数 k 。数组 arr 由 1 和若干 素数  组成，且其中所有整数互不相同。

    对于每对满足 0 <= i < j < arr.length 的 i 和 j ，可以得到分数 arr[i] / arr[j] 。

    那么第 k 个最小的分数是多少呢?  以长度为 2 的整数数组返回你的答案, 这里 answer[0] == arr[i] 且 answer[1] == arr[j] 。

     

    示例 1：

    输入：arr = [1,2,3,5], k = 3
输出：[2,5]
解释：已构造好的分数,排序后如下所示: 
1/5, 1/3, 2/5, 1/2, 3/5, 2/3
很明显第三个最小的分数是 2/5

    示例 2：

    输入：arr = [1,7], k = 1
输出：[1,7]

     

    提示：

    • 2 <= arr.length <= 1000
    • 1 <= arr[i] <= 3 * 104
    • arr[0] == 1
    • arr[i] 是一个 素数 ，i > 0
    • arr 中的所有数字 互不相同 ，且按 严格递增 排序
    • 1 <= k <= arr.length * (arr.length - 1) / 2
    Related Topics
    • 数组
    • 二分查找
    • 排序
    • 堆（优先队列）

  • 👍 221
  • 👎 0

    • 优先队列两种实现

    首先，直接上来一个优先队列，自定义排序。

    为了实现这个自定义的排序，我们需要记录几个东西

    1. 分子
    2. 分母
    3. 为了便于比较，相除后的小数值也可以事先计算好，比较的时候就直接比较这个数字即可
    4. 把所有的都放进去之后，我们就开始从头部取出K个即可
    5. 最终得到第K个的分子分母即可

    理解起来也相对比较简单

    代码

    class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        PriorityQueue<double[]> queue = new PriorityQueue<>(new Comparator<double[]>() {
            @Override
            public int compare(double[] o1, double[] o2) {
                if (o1[2] >= o2[2]){
                    return 1;
                }
                return -1;
            }
        });
        for (int i : arr) {
            for (int j : arr) {
                queue.offer(new double[]{(double)i,(double)j,((double)i)/j});
            }
        }
        while (--k > 0){
            queue.poll();
        }
        return new int[]{(int)queue.peek()[0],(int)queue.peek()[1]};
    }
}

    写完这个之后思考一下，我们真的需要把所有的值都算一遍全都存进优先队列么？答案是否定的，

    1. 我们可以把数据分别按照分母分成arr[]数组长度个分组，
    2. 分别维护一个指针，指向当前对应的分子，
    3. 这样我们的优先队列只要维护比较arr[]数组长度个值即可，每当从队列头部取出一个对象时，只需把分子位置往后挪动一位，重新放入队列
    4. 如果分子指针位置已经到达了arr[]数组尾部，则不再需要往队列中添加

    代码

    class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (((double)arr[o1[0]])/arr[o1[1]] >= ((double)arr[o2[0]])/arr[o2[1]]){
                    return 1;
                }
                return -1;
            }
        });
        for (int i = 0; i < arr.length; i++) {
            queue.offer(new int[]{0,i});
        }
        while (--k > 0) {
            int[] top = queue.poll();
            if (top[0] < arr.length){
                top[0]++;
                queue.offer(top);
            }
        }
        return new int[]{arr[queue.peek()[0]],arr[queue.peek()[1]]};
    }

}