Car Fleet

Car FleetN carsaregoingtothesamedestinationalongaonelaneroad. Thedestinationis target milesaway.Eachcar i hasaconstantspeed speed[i] (inmilesperhour),andinitialposition position[i] m…

大家好,又见面了,我是你们的朋友全栈君。

N cars are going to the same destination along a one lane road.  The destination is target miles away.

Each car i has a constant speed speed[i] (in miles per hour), and initial position position[i] miles towards the target along the road.

A car can never pass another car ahead of it, but it can catch up to it, and drive bumper to bumper at the same speed.

The distance between these two cars is ignored – they are assumed to have the same position.

car fleet is some non-empty set of cars driving at the same position and same speed.  Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.

How many car fleets will arrive at the destination?

 

Example 1:

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
The cars starting at 10 and 8 become a fleet, meeting each other at 12.
The car starting at 0 doesn't catch up to any other car, so it is a fleet by itself.
The cars starting at 5 and 3 become a fleet, meeting each other at 6.
Note that no other cars meet these fleets before the destination, so the answer is 3.

Note:

  1. 0 <= N <= 10 ^ 4
  2. 0 < target <= 10 ^ 6
  3. 0 < speed[i] <= 10 ^ 6
  4. 0 <= position[i] < target
  5. All initial positions are different.

 

题目理解:

给定一系列车辆的位置和速度的集合,若后来车辆赶上前面的车辆,则合成为一个车队,问最终会形成多少个车队

解题思路:

首先按位置从近到远排列所有车辆,然后计算每一辆车到达终点的时间,如果后来的车辆行驶时间小于前面的车辆,那么说明它会追上前面的车辆并形成一个车队,若后来的车行驶时间大于前面的车辆,那么它将不会和前面的车辆形成车队,而会被它后面的车辆追上形成车队。根据以上分析,只需要计算行驶时间非递减的数目就行

代码如下:

class Solution {
	class Node implements Comparable<Node>{
		double position;
		int speed;
		public Node(int t, int s) {
			position = t;
			speed = s;
		}
		@Override
		public int compareTo(Node a) {
			// TODO Auto-generated method stub
			return (int)(a.position - this.position);
		}
	}
	
    public int carFleet(int target, int[] position, int[] speed) {
        int res = 0;
        double front;
        int len = position.length;
        if(len == 0)
        	return 0;
        List<Node> list = new ArrayList<Node>();
        for(int i = 0; i < len; i++) {
        	list.add(new Node(position[i], speed[i]));
        }
        Collections.sort(list);
        Node it = list.get(0);
        front = (target - it.position) / it.speed;
        for(int i = 1; i < len; i++) {
        	it = list.get(i);
        	double time = (target - it.position) / it.speed;
        	if(time > front) {
        		res++;
        		front = time;
        	}
        }
        return res + 1;
    }
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/131587.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • java语言和C语言的区别

    java语言和C语言的区别简单的说就是两种不同的语言.但是它们之间既有联系又有区别

    2022年7月8日
    22
  • 虚拟机开启就会蓝屏的解决方法是_虚拟机无限蓝屏

    虚拟机开启就会蓝屏的解决方法是_虚拟机无限蓝屏VMware与win10(专业版)不兼容的问题前两天系统出了点问题,然后重置了系统,结果今天装VMware的时候发现一开虚拟机就蓝屏了。一、首先打开控制面板,找到启动或关闭Windows功能二、打开win+R,输入gpedit.msc三、打开控制面板>程序>查看已安装的更新,卸载最近的更新。总结前两天系统出了点问题,然后重置了系统,结果今天装VMware的时候发现一开虚拟机就蓝屏了。找了好些方法,重启了十几次电脑,后面才弄好提示:以下是本篇文章正文内容,下面案例可供参考一、首先打开控制

    2025年9月6日
    4
  • python语言变量命名规则[通俗易懂]

    python语言变量命名规则[通俗易懂]Python语言变量命名规则变量名只能包含字母、数字和下划线。(推荐学习:0基础入门python)变量名可以字母或下划线开头,但不能以数字开头。例如,可将变量命名为message_1,但不能将其命名为1_message。变量名不能包含空格,但可使用下划线来分隔其中的单词。例如,变量名greeting_message可行,但变量名greetingmessage会引发错误。不要将Pytho…

    2022年6月14日
    35
  • 安全帽识别算法

    安全帽识别算法应用背景:安全帽作为一种最常见和实用的个人防护用具,能够有效地防止和减轻外来危险源对头部的伤害。但在现场操作过程中,安全帽的佩戴很容易人为忽略,引发了不少人身伤害事故。为了保证工作人员都能在作业中佩戴安全帽,保障作业人员安全,安全帽识别算法系统应运而生。关键字:安全帽识别算法安全帽识别算法技术原理安全帽识别算法采用最新AI人工智能深度学习技术,基于计算机智能视频物体识别算法,且通过规模化的安全帽数据识别训练,赋予监控系统智能识别能力,从而准确判断识别场景内的作业人员是否佩戴安全帽,若检.

    2022年5月12日
    59
  • sql存储过程简单例题_sql存储过程实例详解

    sql存储过程简单例题_sql存储过程实例详解1、创建存储过程P1,查询每个学生的修课门数,要求列出学生学号、姓名及修课门数。createprocP1asselectStudent.StudentID,StudentName,count(CourseID)选修门数fromStudentjoinGradeonGrade.StudentID=Student.StudentIDgroupbyStudent.StudentID,StudentNamego2、创建存储过程P2,查询学生的学号、姓名、课程名、成绩

    2022年8月30日
    3
  • Python 实现PID控制一阶惯性系统[通俗易懂]

    Python 实现PID控制一阶惯性系统[通俗易懂]1.PID.py#PID控制一阶惯性系统测试程序#*****************************************************************##增量式PID系统##*************************************…

    2022年10月4日
    5

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号