rsleetcode/
medium.rs

1use super::utils::*;
2
3/// https://leetcode.com/problems/add-two-numbers/
4pub fn add_two_numbers(
5    l1: Option<Box<ListNode>>,
6    l2: Option<Box<ListNode>>,
7) -> Option<Box<ListNode>> {
8    match (l1, l2) {
9        (None, None) => None,
10        (Some(n), None) | (None, Some(n)) => Some(n),
11        (Some(n1), Some(n2)) => {
12            let sum = n1.val + n2.val;
13            if sum < 10 {
14                Some(Box::new(ListNode {
15                    val: sum,
16                    next: add_two_numbers(n1.next, n2.next),
17                }))
18            } else {
19                let carry = Some(Box::new(ListNode::new(1)));
20                Some(Box::new(ListNode {
21                    val: sum - 10,
22                    next: add_two_numbers(add_two_numbers(carry, n1.next), n2.next),
23                }))
24            }
25        }
26    }
27}
28
29/// https://leetcode.com/problems/longest-substring-without-repeating-characters/
30pub fn longest_substring_without_repeating_characters(s: String) -> i32 {
31    let mut max_len: usize = 0;
32    let mut pos: [usize; 128] = [0; 128];
33    let mut start: usize = 0;
34
35    for (end, ch) in s.chars().enumerate() {
36        start = start.max(pos[ch as usize]);
37        max_len = max_len.max(end - start + 1);
38        pos[ch as usize] = end + 1;
39    }
40    return max_len as i32;
41}
42
43/// https://leetcode.com/problems/longest-palindromic-substring/
44pub fn longest_palindromic_substring(s: String) -> String {
45    fn is_palidrome(s: &[u8]) -> bool {
46        s.iter().zip(s.iter().rev()).all(|(l, r)| l == r)
47    }
48
49    for size in (1..=s.len()).rev() {
50        match s
51            .as_bytes()
52            .windows(size)
53            .find(|substr| is_palidrome(substr))
54        {
55            Some(pal) => return String::from_utf8(pal.to_vec()).unwrap(),
56            None => continue,
57        }
58    }
59    "".to_string()
60}
61
62/// https://leetcode.com/problems/zigzag-conversion/
63pub fn zigzag_conversion(s: String, num_rows: i32) -> String {
64    let mut zigzags: Vec<_> = (0..num_rows)
65        .chain((1..num_rows - 1).rev())
66        .cycle()
67        .zip(s.chars())
68        .collect();
69    zigzags.sort_by_key(|&(row, _)| row);
70    zigzags.into_iter().map(|(_, c)| c).collect()
71}
72
73/// https://leetcode.com/problems/reverse-integer/
74pub fn reverse_integer(x: i32) -> i32 {
75    let mut res: i32 = 0;
76    let mut cur: i32 = x;
77
78    while cur != 0 {
79        match res.checked_mul(10) {
80            None => return 0,
81            Some(tmp) => match tmp.checked_add(cur % 10) {
82                None => return 0,
83                Some(fine) => {
84                    res = fine;
85                }
86            },
87        }
88        cur = cur / 10;
89    }
90    res
91}
92
93/// https://leetcode.com/problems/string-to-integer-atoi/
94pub fn string_to_integer_atoi(s: String) -> i32 {
95    let s = s.trim_start();
96    let (s, sign) = match s.strip_prefix('-') {
97        Some(s) => (s, -1),
98        None => (s.strip_prefix('+').unwrap_or(s), 1),
99    };
100    s.chars()
101        .map(|c| c.to_digit(10))
102        .take_while(Option::is_some)
103        .flatten()
104        .fold(0, |acc, digit| {
105            acc.saturating_mul(10).saturating_add(sign * digit as i32)
106        })
107}
108
109/// https://leetcode.com/problems/container-with-most-water/
110pub fn container_with_most_water(height: Vec<i32>) -> i32 {
111    let mut result = 0;
112    let mut iter = height.iter().enumerate();
113    let mut p1 = iter.next();
114    let mut p2 = iter.next_back();
115    while let (Some((i, h1)), Some((j, h2))) = (p1, p2) {
116        result = result.max(h1.min(h2) * (j - i) as i32);
117        if h1 < h2 {
118            p1 = iter.next();
119        } else {
120            p2 = iter.next_back();
121        }
122    }
123    result
124}
125
126/// https://leetcode.com/problems/integer-to-roman/
127pub fn integer_to_roman(num: i32) -> String {
128    const ONES: [&str; 10] = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"];
129    const TENS: [&str; 10] = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"];
130    const CENT: [&str; 10] = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"];
131    const MILS: [&str; 4] = ["", "M", "MM", "MMM"];
132
133    format!(
134        "{}{}{}{}",
135        MILS[(num / 1000 % 10) as usize],
136        CENT[(num / 100 % 10) as usize],
137        TENS[(num / 10 % 10) as usize],
138        ONES[(num % 10) as usize]
139    )
140}
141
142/// https://leetcode.com/problems/3sum/
143pub fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
144    let max = nums.len();
145    let mut wnums = nums.clone();
146    wnums.sort();
147    let mut result: Vec<Vec<i32>> = Vec::new();
148    for i in 0..max {
149        if i > 0 && wnums[i] == wnums[i - 1] {
150            continue;
151        }
152        let mut j = i + 1;
153        let mut k = max - 1;
154        while j < k {
155            let sum = wnums[i] + wnums[j] + wnums[k];
156            if sum == 0 {
157                result.push(vec![wnums[i], wnums[j], wnums[k]]);
158                j += 1;
159                k -= 1;
160                while j < k && wnums[j] == wnums[j - 1] {
161                    j += 1
162                }
163                while j < k && wnums[k] == wnums[k + 1] {
164                    k -= 1
165                }
166            } else {
167                if sum < 0 {
168                    j += 1
169                } else {
170                    k -= 1
171                }
172            }
173        }
174    }
175    result
176}
177
178/// https://leetcode.com/problems/3sum-closest/
179pub fn three_sum_closest(nums: Vec<i32>, target: i32) -> i32 {
180    let mut arr: Vec<i32> = nums.clone();
181    arr.sort();
182    let n: usize = arr.len();
183    let mut min_diff: i32 = i32::MAX;
184    let mut min_sum: i32 = i32::MAX;
185    for i in 0..n - 2 {
186        let mut j = i + 1;
187        let mut k = n - 1;
188        while k > j {
189            let _sum = arr[i] + arr[j] + arr[k];
190            let _diff = _sum - target;
191            if _diff == 0 {
192                return _sum;
193            } else if _diff < 0 {
194                if min_diff > { -_diff } {
195                    min_diff = -_diff;
196                    min_sum = _sum;
197                }
198                j += 1;
199            } else {
200                if min_diff > _diff {
201                    min_diff = _diff;
202                    min_sum = _sum;
203                }
204                k -= 1;
205            }
206        }
207    }
208    min_sum
209}
rsleetcode/medium.rs

rsleetcode/
medium.rs
