V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
zzzrf
V2EX  ›  Java

Roblox 面试题:亮起时间最长的灯

  •  
  •   zzzrf · 15 天前 · 226 次点击

    描述

    有一排 26 个彩灯,编号从 0 到 25,现在给出了一系列控制指令来控制这些彩灯的开关。

    一开始这些彩灯都是关闭的,然后指令将逐条发出。

    在每条指令 operation[i]中含有两个整数 operation[i][0], operation[i][1]。

    在接收到一条指令时,标号为 operation[i][0] 的彩灯会亮起,直到第 operation[i][1] 秒的时候熄灭。

    当灯熄灭后,下一条指令将会发出。

    其中第一条指令将在第 0 秒的时候发出,并被立刻执行。

    你的任务是找到哪个彩灯单次亮起的时间最长。

    1≤n≤1051≤n≤105

    0≤keyTimes[i][0]≤25(0≤i<n)0≤keyTimes[i][0]≤25(0≤i<n)

    0≤keyTimes[i][1]≤108(0≤i<n)0≤keyTimes[i][1]≤108(0≤i<n)

    保证至少有一个按键.

    保证 keyTimes 是按照 keyTimes[i][1] 升序排序的.

    [在线评测地址]

    样例 1

    输入:
    [[0,2],[1,5],[0,9],[2,15]]
    输出:
    'c'
    说明:
    operation = `[[0, 2], [1, 5], [0, 9], [2, 15]]`
    在第 0 秒的时候,接收到指令`[0, 2]`,此时标号为 0 的灯亮起,第 2 秒的时候熄灭。此时 0 号灯 的单次亮起时间为`2-0 = 2` 秒。
    在第 2 秒的时候,接收到指令`[1, 5]`,此时标号为 1 的灯亮起,第 5 秒的时候熄灭。此时 1 号灯 的单次亮起时间为 `5-2 = 3` 秒。
    在第 5 秒的时候,接收到指令`[0, 9]`,此时标号为 0 的灯亮起,第 9 秒的时候熄灭。此时 0 号灯 的单次亮起时间为 `9-5 = 4` 秒。
    在第 9 秒的时候,接收到指令`[2, 15]`,此时标号为 2 的灯亮起,第 15 秒的时候熄灭。此时 2 号灯 的单次亮起时间为 `15-9 = 6` 秒。
    所以单次亮起的最长时间为 `max(2, 3, 4, 6) = 6` 秒,是标号为 `2` 的彩灯。
    
    **你需要返回一个小写英文字母代表这个编号。`如 'a' 代表 0,'b' 代表 1,'c' 代表 2 ... 'z' 代表 25 。`**
    所以你的答案应该是`'c'`
    

    算法:模拟

    解题思路:

    模拟路灯开关的过程,并记录最长的灯亮的时间,以及当前亮起时间最长的灯。

    复杂度分析:

    时间复杂度:O(n) n 为数组的长度。 空间复杂度:O ( 1 )

    代码:

    public class Solution {
        /**
         * @param operation: A list of operations.
         * @return: The lamp has the longest liighting time.
         */
        public char longestLightingTime(List<List<Integer>> operation) {
            int maxTime = operation.get(0).get(1);
            char answer = (char)('a' + operation.get(0).get(0));
            int n = operation.size();
    
            for (int i = 0; i < n - 1; i++) {
                List<Integer> next = operation.get(i + 1);
                List<Integer> current = operation.get(i);
                int time = next.get(1) - current.get(1);
                if (time > maxTime) {
                    maxTime = time;
                    answer = (char)(next.get(0) + 'a');
                }
            }
            return answer;
        }
    }
    

    [更多题解参考]

    目前尚无回复
    关于   ·   帮助文档   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3501 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 19ms · UTC 07:49 · PVG 15:49 · LAX 00:49 · JFK 03:49
    ♥ Do have faith in what you're doing.