rustgym/leetcode/
_949_largest_time_for_given_digits.rs

1struct Solution;
2
3use std::fmt;
4
5#[derive(Debug, PartialEq, Eq, Clone)]
6struct Time {
7    hour: i32,
8    minute: i32,
9}
10
11impl Time {
12    fn new(hour: i32, minute: i32) -> Self {
13        Time { hour, minute }
14    }
15    fn is_valid(&self) -> bool {
16        self.hour < 24 && self.minute < 60
17    }
18    fn from_digits(a: &[i32]) -> Self {
19        Self::new(a[0] * 10 + a[1], a[2] * 10 + a[3])
20    }
21    fn to_minutes(&self) -> i32 {
22        self.hour * 60 + self.minute
23    }
24    fn to_digits(&self) -> Vec<i32> {
25        vec![
26            self.hour / 10,
27            self.hour % 10,
28            self.minute / 10,
29            self.minute % 10,
30        ]
31    }
32}
33
34impl fmt::Display for Time {
35    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
36        let a = self.to_digits();
37        write!(f, "{}{}:{}{}", a[0], a[1], a[2], a[3])
38    }
39}
40
41use std::cmp::Ordering;
42
43impl PartialOrd for Time {
44    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
45        Some(self.to_minutes().cmp(&other.to_minutes()))
46    }
47}
48
49impl Solution {
50    fn backtrack(a: &mut Vec<i32>, index: usize, max: &mut Option<Time>) {
51        let n = a.len();
52        if index == n {
53            let time = Time::from_digits(a);
54            if time.is_valid() {
55                if let Some(max_time) = max {
56                    if time > *max_time {
57                        *max = Some(time)
58                    }
59                } else {
60                    *max = Some(time)
61                }
62            }
63        } else {
64            for i in index..n {
65                a.swap(index, i);
66                Self::backtrack(a, index + 1, max);
67                a.swap(index, i);
68            }
69        }
70    }
71    fn largest_time_from_digits(mut a: Vec<i32>) -> String {
72        let mut max: Option<Time> = None;
73        Self::backtrack(&mut a, 0, &mut max);
74        if let Some(max_time) = max {
75            max_time.to_string()
76        } else {
77            "".to_string()
78        }
79    }
80}
81
82#[test]
83fn test() {
84    let a = vec![1, 2, 3, 4];
85    let res = "23:41".to_string();
86    assert_eq!(Solution::largest_time_from_digits(a), res);
87    let a = vec![5, 5, 5, 5];
88    let res = "".to_string();
89    assert_eq!(Solution::largest_time_from_digits(a), res);
90    let a = vec![0, 0, 0, 0];
91    let res = "00:00".to_string();
92    assert_eq!(Solution::largest_time_from_digits(a), res);
93}
rustgym/leetcode/_949_largest_time_for_given_digits.rs

rustgym/leetcode/
_949_largest_time_for_given_digits.rs
