LeetCode_二分搜索_中等_2594.修车的最少时间

这篇具有很好参考价值的文章主要介绍了LeetCode_二分搜索_中等_2594.修车的最少时间。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.题目

给你一个整数数组 ranks ,表示一些机械工的 能力值 。ranksi 是第 i 位机械工的能力值。能力值为 r 的机械工可以在 r * n2 分钟内修好 n 辆车。

同时给你一个整数 cars ,表示总共需要修理的汽车数目。请你返回修理所有汽车最少需要多少时间。

注意:所有机械工可以同时修理汽车。

示例 1:
输入:ranks = [4,2,3,1], cars = 10
输出:16
解释:

  • 第一位机械工修 2 辆车,需要 4 * 2 * 2 = 16 分钟。
  • 第二位机械工修 2 辆车,需要 2 * 2 * 2 = 8 分钟。
  • 第三位机械工修 2 辆车,需要 3 * 2 * 2 = 12 分钟。
  • 第四位机械工修 4 辆车,需要 1 * 4 * 4 = 16 分钟。

16 分钟是修理完所有车需要的最少时间。

示例 2:
输入:ranks = [5,1,8], cars = 6
输出:16
解释:

  • 第一位机械工修 1 辆车,需要 5 * 1 * 1 = 5 分钟。
  • 第二位机械工修 4 辆车,需要 1 * 4 * 4 = 16 分钟。
  • 第三位机械工修 1 辆车,需要 8 * 1 * 1 = 8 分钟。

16 分钟时修理完所有车需要的最少时间。

提示:
1 <= ranks.length <= 105
1 <= ranks[i] <= 100
1 <= cars <= 106

2.思路

(1)二分搜索
本题与 875.爱吃香蕉的珂珂 的思路一样,具体代码如下所示。

相关题目:
LeetCode_二分搜索_中等_875.爱吃香蕉的珂珂文章来源地址https://www.toymoban.com/news/detail-699968.html

3.代码实现(Java)

//思路1————二分搜索
class Solution {
    public long repairCars(int[] ranks, int cars) {
        long left = 1;
        long right = (long) ranks[0] * cars * cars;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            if (check(ranks, cars, mid) < cars) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

    //返回在 m 分钟内,所有机械工最多可以修好的车辆数
    public long check(int[] ranks, int cars, long m) {
        long cnt = 0;
        for (int x : ranks) {
            cnt += (long) Math.sqrt(m / x);
        }
        return cnt;
    }
}

到了这里,关于LeetCode_二分搜索_中等_2594.修车的最少时间的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • LeetCode、2300. 咒语和药水的成功对数【中等,排序+二分】

    博主介绍:✌目前全网粉丝2W+,csdn博客专家、Java领域优质创作者,博客之星、阿里云平台优质作者、专注于Java后端技术领域。 涵盖技术内容:Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。 博主所有博客文件目录索引:博客目录索引(持续更新) 视频平台:

    2024年01月20日
    浏览(35)
  • LeetCode、875. 爱吃香蕉的珂珂【中等,最小速度二分】

    博主介绍:✌目前全网粉丝2W+,csdn博客专家、Java领域优质创作者,博客之星、阿里云平台优质作者、专注于Java后端技术领域。 涵盖技术内容:Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。 博主所有博客文件目录索引:博客目录索引(持续更新) 视频平台:

    2024年01月24日
    浏览(54)
  • C++二分算法:得到子序列的最少操作次数

    二分查找算法合集 给你一个数组 target ,包含若干 互不相同 的整数,以及另一个整数数组 arr ,arr 可能 包含重复元素。 每一次操作中,你可以在 arr 的任意位置插入任一整数。比方说,如果 arr = [1,4,1,2] ,那么你可以在中间添加 3 得到 [1,4,3,1,2] 。你可以在数组最开始或最后

    2024年02月05日
    浏览(45)
  • 【LeetCode-中等题】79. 单词搜索

    需要一个标记数组 来标志格子字符是否被使用过了 先找到word 的第一个字符在表格中的位置,再开始递归 递归的结束条件是如果word递归到了最后一个字符了,说明能在矩阵中找到单词 剪枝条件 就是如果已经找到单词了 res = true 了 后面就不需要递归了,还有如果下标越界、

    2024年02月09日
    浏览(37)
  • 【算法】【Python3、动态规划、贪心、二分查找】力扣1671. 得到山形数组的最少删除次数

    1671. 得到山形数组的最少删除次数 给定一个整数数组 nums ,我们定义该数组为山形数组当且仅当: nums 的长度至少为 3。 存在一个下标 i 满足 0 i len(nums) - 1 且: nums[0] nums[1] ... nums[i - 1] nums[i] nums[i] nums[i + 1] ... nums[len(nums) - 1] 现在,给定整数数组 nums ,我们的目标是将其变为

    2024年01月18日
    浏览(52)
  • 【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值

    《博主简介》 小伙伴们好,我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。 ✌ 更多学习资源,可关注公-仲-hao:【阿旭算法与机器学习】,共同学习交流~ 👍 感谢小伙伴 们点赞、关注! class   Solution :      def   mySqrt ( self ,  x :   int )   -   int :       

    2024年02月04日
    浏览(63)
  • 【动态规划】【广度优先搜索】LeetCode:2617 网格图中最少访问的格子数

    二分查找算法合集 动态规划汇总 视频算法专题 给你一个下标从 0 开始的 m x n 整数矩阵 grid 。你一开始的位置在 左上角 格子 (0, 0) 。 当你在格子 (i, j) 的时候,你可以移动到以下格子之一: 满足 j k = grid[i][j] + j 的格子 (i, k) (向右移动),或者 满足 i k = grid[i][j] + i 的格子

    2024年02月04日
    浏览(37)
  • LeetCode_前缀树_中等_1268.搜索推荐系统

    给你一个产品数组 products 和一个字符串 searchWord ,products 数组中每个产品都是一个字符串。 请你设计一个推荐系统,在依次输入单词 searchWord 的每一个字母后,推荐 products 数组中前缀与 searchWord 相同的最多三个产品。如果前缀相同的可推荐产品超过三个,请按字典序返回最

    2024年02月16日
    浏览(39)
  • 【LeetCode每日一题】2809. 使数组和小于等于 x 的最少时间

    2024-1-19 2809. 使数组和小于等于 x 的最少时间 思路: 获取两个列表的长度n,并初始化一个二维数组f,用于存储最优解。 定义一个二维数组nums,用于存储输入的两个列表中的元素,并按照第二列元素进行排序。 使用动态规划的方法,通过遍历nums数组,计算最优解。其中,

    2024年01月21日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包