681. Next Closest Time

leetcode medium

#array#csharp#hash-table#leetcode#medium#string#tree

Task

Дано время, представленное в формате "ЧЧ:ММ". Сформируйте ближайшее следующее время, используя текущие цифры. Количество раз, которое можно использовать цифру, не ограничено.

Можно предположить, что заданная строка всегда корректна. Например, "01:34", "12:09" являются корректными. "1:34", "12:9" являются некорректными.

Пример:

Input: time = "19:34"

Output: "19:39"

Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later.

It is not 19:33, because this occurs 23 hours and 59 minutes later.

C# solution

matched/original

public class Solution {
    public string NextClosestTime(string time) {
        int cur = 60 * int.Parse(time.Substring(0, 2));
        cur += int.Parse(time.Substring(3));
        HashSet<int> allowed = new HashSet<int>();
        foreach (char c in time) if (c != ':') {
            allowed.Add(c - '0');
        }
        while (true) {
            cur = (cur + 1) % (24 * 60);
            int[] digits = new int[] { cur / 60 / 10, cur / 60 % 10, cur % 60 / 10, cur % 60 % 10 };
            bool isValid = true;
            foreach (int d in digits) {
                if (!allowed.Contains(d)) {
                    isValid = false;
                    break;
                }
            }
            if (isValid) {
                return string.Format("{0:D2}:{1:D2}", cur / 60, cur % 60);
            }
        }
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string NextClosestTime(string time) {
        int cur = 60 * int.Parse(time.Substring(0, 2));
        cur += int.Parse(time.Substring(3));
        HashSet<int> allowed = new HashSet<int>();
        foreach (char c in time) if (c != ':') {
            allowed.push_back(c - '0');
        }
        while (true) {
            cur = (cur + 1) % (24 * 60);
            vector<int>& digits = new int[] { cur / 60 / 10, cur / 60 % 10, cur % 60 / 10, cur % 60 % 10 };
            bool isValid = true;
            foreach (int d in digits) {
                if (!allowed.Contains(d)) {
                    isValid = false;
                    break;
                }
            }
            if (isValid) {
                return string.Format("{0:D2}:{1:D2}", cur / 60, cur % 60);
            }
        }
    }
}

Java solution

matched/original

class Solution {
    public String nextClosestTime(String time) {
        int cur = 60 * Integer.parseInt(time.substring(0, 2));
        cur += Integer.parseInt(time.substring(3));
        Set<Integer> allowed = new HashSet<>();
        for (char c : time.toCharArray()) {
            if (c != ':') {
                allowed.add(c - '0');
            }
        }

        while (true) {
            cur = (cur + 1) % (24 * 60);
            int[] digits = new int[]{cur / 60 / 10, cur / 60 % 10, cur % 60 / 10, cur % 60 % 10};
            search:
            {
                for (int d : digits) {
                    if (!allowed.contains(d)) {
                        break search;
                    }
                }
                return String.format("%02d:%02d", cur / 60, cur % 60);
            }
        }
    }
}

JavaScript solution

matched/original

class Solution {
    nextClosestTime(time) {
        let cur = 60 * parseInt(time.substring(0, 2)) + parseInt(time.substring(3));
        const allowed = new Set();
        for (const c of time) if (c !== ':') {
            allowed.add(Number(c));
        }

        while (true) {
            cur = (cur + 1) % (24 * 60);
            const digits = [Math.floor(cur / 60 / 10), Math.floor(cur / 60 % 10), Math.floor(cur % 60 / 10), Math.floor(cur % 60 % 10)];
            if (digits.every(d => allowed.has(d))) {
                return `${String(cur / 60).padStart(2, '0')}:${String(cur % 60).padStart(2, '0')}`;
            }
        }
    }
}

Python solution

matched/original

class Solution:
    def nextClosestTime(self, time: str) -> str:
        cur = 60 * int(time[:2]) + int(time[3:])
        allowed = {int(c) for c in time if c != ':'}

        while True:
            cur = (cur + 1) % (24 * 60)
            digits = [cur // 60 // 10, cur // 60 % 10, cur % 60 // 10, cur % 60 % 10]
            if all(d in allowed for d in digits):
                return f"{cur // 60:02d}:{cur % 60:02d}"

Go solution

matched/original

package main

import (
    "fmt"
    "strconv"
    "strings"
)

func nextClosestTime(time string) string {
    cur := 60*atoi(time[:2]) + atoi(time[3:])
    allowed := make(map[int]bool)
    for _, c := range time {
        if c != ':' {
            allowed[int(c-'0')] = true
        }
    }

    for {
        cur = (cur + 1) % (24 * 60)
        digits := []int{cur / 60 / 10, cur / 60 % 10, cur % 60 / 10, cur % 60 % 10}
        valid := true
        for _, d := range digits {
            if !allowed[d] {
                valid = false
                break
            }
        }
        if valid {
            return fmt.Sprintf("%02d:%02d", cur/60, cur%60)
        }
    }
}

func atoi(s string) int {
    i, _ := strconv.Atoi(s)
    return i
}

func main() {
    fmt.Println(nextClosestTime("19:34"))
}

Explanation

Algorithm

Симулируйте ход часов, увеличивая время на одну минуту. Каждый раз, когда время увеличивается, если все цифры допустимы, верните текущее время.

Представьте время как целое число t в диапазоне 0 <= t < 24 * 60. Тогда часы равны t / 60, минуты равны t % 60.

Найдите каждую цифру часов и минут: часы / 10, часы % 10 и т.д.

😎