leetcode

Leetcode problem solutions
git clone https://git.sinitax.com/sinitax/leetcode
Log | Files | Refs | sfeed.txt

0386-lexicographical-numbers.rs (1338B)

      1/// 386. Lexicographical Numbers (Medium)
      2///
      3/// Given an integer n, return all the numbers in the range [1, n] sorted in
      4/// lexicographical order.
      5///
      6/// You must write an algorithm that runs in O(n) time and uses O(1) extra
      7/// space.
      8///
      9/// *Example 1:*
     10///
     11///   *Input:* n = 13
     12///   *Output:* [1,10,11,12,13,2,3,4,5,6,7,8,9]
     13///
     14/// *Example 2:*
     15///
     16///   *Input:* n = 2
     17///   *Output:* [1,2]
     18///
     19/// *Constraints:*
     20///
     21///   * 1 <= n <= 5 * 104
     22///
     23use leetcode::arg;
     24
     25struct Solution {}
     26
     27impl Solution {
     28    fn radd(vec: &mut Vec<i32>, c: i32, n: i32) {
     29        vec.push(c);
     30        for d in 0..=9 {
     31            let p = c * 10 + d;
     32            if p > n {
     33                break;
     34            }
     35            Self::radd(vec, p, n);
     36        }
     37    }
     38
     39    pub fn lexical_order(n: i32) -> Vec<i32> {
     40        let mut vec = Vec::new();
     41        for d in 1..=std::cmp::min(9, n) {
     42            Self::radd(&mut vec, d, n);
     43        }
     44        vec
     45    }
     46}
     47
     48pub fn main() {
     49    println!("{:?}", Solution::lexical_order(arg(1).parse().unwrap()));
     50}
     51
     52#[cfg(test)]
     53mod tests {
     54    use crate::Solution;
     55    use leetcode::vi;
     56
     57    #[test]
     58    fn examples() {
     59        assert_eq!(
     60            Solution::lexical_order(13),
     61            vi("[1,10,11,12,13,2,3,4,5,6,7,8,9]")
     62        );
     63        assert_eq!(Solution::lexical_order(2), vi("[1,2]"));
     64    }
     65}