rsleetcode/
easy.rs

1use super::utils::*;
2use std::cell::RefCell;
3use std::rc::Rc;
4
5/// # 1. Two Sum
6/// Given an array of integers `nums` and an integer `target`, return indices of the two numbers such that they add up to `target`.
7///
8/// You may assume that each input would have **exactly one solution**, and you may not use the same element twice.
9///
10/// You can return the answer in any order.
11///
12/// #### Example 1:
13/// > **Input:** ```nums = [2,7,11,15], target = 9```
14///
15/// > **Output:** ```[0,1]```
16///
17/// > **Explanation:** ```Because nums[0] + nums[1] == 9, we return [0, 1].```
18/// #### Example 2:
19/// > **Input:** ```nums = [3,2,4], target = 6```
20///
21/// > **Output:** ```[1,2]```
22/// #### Example 3:
23/// > **Input:** ```nums = [3,3], target = 6```
24///
25/// > **Output:** ```[0,1]```
26///
27/// #### Constraints:
28/// - <code>2 <= nums.length <= 10<sup>4</sup></code>
29/// - <code>-10<sup>9</sup> <= nums\[i\] <= 10<sup>9</sup></code>
30/// - <code>-10<sup>9</sup> <= target <= 10<sup>9</sup></code>
31/// - **Only one valid answer exists.**
32pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
33    let mut nums: Vec<(usize, i32)> = nums.into_iter().enumerate().collect::<Vec<(usize, i32)>>();
34    nums.sort_unstable_by_key(|&(_, v)| v);
35    for (i, (k, v)) in nums.iter().enumerate() {
36        match nums[i + 1..].binary_search_by_key(&(target - *v), |&(_, b)| b) {
37            Ok(j) => {
38                return vec![*k as i32, nums[j + i + 1].0 as i32];
39            }
40            Err(_) => {}
41        }
42    }
43    unreachable!();
44}
45
46/// 9. Palindrome Number
47/// Given an integer x, return true if x is a palindrome, and false otherwise.
48pub fn palindrome_number(x: i32) -> bool {
49    if x < 0 {
50        return false;
51    }
52    let mut tmp = x;
53    let mut s: i32 = 0;
54    while tmp != 0 {
55        s = s * 10 + tmp % 10;
56        tmp /= 10;
57    }
58    x == s
59}
60
61pub fn roman_to_integer(s: String) -> i32 {
62    s.chars().rfold(0, |acc, c| {
63        acc + match c {
64            'I' if acc >= 5 => -1,
65            'I' => 1,
66            'V' => 5,
67            'X' if acc >= 50 => -10,
68            'X' => 10,
69            'L' => 50,
70            'C' if acc >= 500 => -100,
71            'C' => 100,
72            'D' => 500,
73            'M' => 1000,
74            _ => 0,
75        }
76    })
77}
78
79pub fn longest_common_prefix(strs: Vec<String>) -> String {
80    strs.into_iter()
81        .reduce(|acc, cur| {
82            acc.chars()
83                .zip(cur.chars())
84                .take_while(|(a, c)| a == c)
85                .map(|(c, _)| c)
86                .collect()
87        })
88        .unwrap()
89}
90
91pub fn valid_parentheses(s: String) -> bool {
92    let mut stack = Vec::new();
93    for i in s.chars() {
94        match i {
95            '{' => stack.push('}'),
96            '(' => stack.push(')'),
97            '[' => stack.push(']'),
98            '}' | ')' | ']' if Some(i) != stack.pop() => return false,
99            _ => (),
100        }
101    }
102    return stack.is_empty();
103}
104
105pub fn merge_two_sorted_lists(
106    list1: Option<Box<ListNode>>,
107    list2: Option<Box<ListNode>>,
108) -> Option<Box<ListNode>> {
109    match (list1, list2) {
110        (None, None) => None,
111        (Some(n), None) | (None, Some(n)) => Some(n),
112        (Some(list1), Some(list2)) => {
113            if list1.val >= list2.val {
114                Some(Box::new(ListNode {
115                    val: list2.val,
116                    next: merge_two_sorted_lists(Some(list1), list2.next),
117                }))
118            } else {
119                Some(Box::new(ListNode {
120                    val: list1.val,
121                    next: merge_two_sorted_lists(list1.next, Some(list2)),
122                }))
123            }
124        }
125    }
126}
127
128pub fn remove_duplicates_from_sorted_array(nums: &mut Vec<i32>) -> i32 {
129    nums.dedup();
130    nums.len() as i32
131}
132
133pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
134    nums.retain(|&x| x != val);
135    return nums.len() as i32;
136}
137
138pub fn find_the_index_of_the_first_occurrence_in_a_string(haystack: String, needle: String) -> i32 {
139    haystack.find(&needle).map_or(-1, |index| index as i32)
140}
141
142pub fn search_insert_position(nums: Vec<i32>, target: i32) -> i32 {
143    nums.partition_point(|&num| num < target) as i32
144}
145
146pub fn length_of_last_word(s: String) -> i32 {
147    s.trim_end()
148        .bytes()
149        .rev()
150        .take_while(|&b| b != b' ')
151        .count() as i32
152}
153
154pub fn plus_one(digits: Vec<i32>) -> Vec<i32> {
155    let mut digits = digits;
156    for v in digits.iter_mut().rev() {
157        let sum = *v + 1;
158        *v = sum % 10;
159        if sum < 10 {
160            return digits;
161        }
162    }
163    [&vec![1], &digits[..]].concat()
164}
165
166pub fn add_binary(a: String, b: String) -> String {
167    let mut a = &a;
168    let mut b = &b;
169    if a.len() < b.len() {
170        std::mem::swap(&mut a, &mut b);
171    }
172
173    let res = a
174        .as_bytes()
175        .rchunks(127)
176        .zip(
177            b.as_bytes()
178                .rchunks(127)
179                .chain(std::iter::repeat(&[b'0'; 127][..])),
180        )
181        .fold((String::new(), 0), |s, (a, b)| {
182            let sum = unsafe {
183                s.1 + u128::from_str_radix(std::str::from_utf8_unchecked(a), 2).unwrap_or(0)
184                    + u128::from_str_radix(std::str::from_utf8_unchecked(b), 2).unwrap_or(0)
185            };
186            (
187                format!("{:0127b}", sum & 0x7fffffffffffffffffffffffffffffff) + &s.0,
188                sum >> 127,
189            )
190        });
191
192    if res.1 == 1 {
193        "1".to_string() + &res.0
194    } else {
195        let str = res.0.trim_start_matches("0").to_string();
196        if str.len() > 0 {
197            str
198        } else {
199            "0".to_string()
200        }
201    }
202}
203
204pub fn sqrt_x(x: i32) -> i32 {
205    if x < 2 {
206        return x;
207    }
208
209    let mut n = x / 2;
210
211    loop {
212        let y = (n + x / n) / 2;
213        if y >= n {
214            return n;
215        }
216        n = y;
217    }
218}
219
220pub fn climbing_stairs(n: i32) -> i32 {
221    (0..n).fold((1, 0), |(res, prev), _| (res + prev, res)).0
222}
223
224pub fn remove_duplicates_from_sorted_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
225    head.map(|mut ln| {
226        let mut cur = ln.as_mut();
227        while let Some(next) = cur.next.as_mut() {
228            if cur.val == next.val {
229                cur.next = next.next.take();
230            } else {
231                cur = cur.next.as_mut().unwrap();
232            }
233        }
234        ln
235    })
236}
237
238pub fn merge_sorted_array(nums1: &mut Vec<i32>, m: i32, nums2: &mut Vec<i32>, n: i32) {
239    let (mut m, mut n) = (m as usize, n as usize);
240    while n > 0 {
241        if m > 0 && nums1[m - 1] > nums2[n - 1] {
242            nums1[m + n - 1] = nums1[m - 1];
243            m -= 1;
244        } else {
245            nums1[m + n - 1] = nums2[n - 1];
246            n -= 1;
247        }
248    }
249}
250
251pub fn binary_tree_inorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
252    let mut curr = root;
253    let mut stack = Vec::<Rc<RefCell<TreeNode>>>::new();
254    let mut res = vec![];
255
256    while curr.is_some() || !stack.is_empty() {
257        while let Some(node_rc) = curr {
258            let left = node_rc.borrow_mut().left.take();
259            stack.push(node_rc);
260            curr = left;
261        }
262
263        let node_rc = stack.pop().unwrap();
264        let mut node_ref = node_rc.borrow_mut();
265        res.push(node_ref.val);
266        curr = node_ref.right.take();
267    }
268    res
269}
270
271pub fn same_tree(p: Option<Rc<RefCell<TreeNode>>>, q: Option<Rc<RefCell<TreeNode>>>) -> bool {
272    p == q
273}
274
275pub fn symmetric_tree(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
276    if root.is_none() {
277        return true;
278    }
279    let b = root.as_ref().unwrap().borrow();
280    let mut v = vec![(b.left.clone(), b.right.clone())];
281    while let Some(tuple) = v.pop() {
282        match tuple {
283            (None, None) => (),
284            (Some(n1), Some(n2)) => {
285                let b1 = n1.borrow();
286                let b2 = n2.borrow();
287                if b1.val != b2.val {
288                    return false;
289                }
290                v.push((b1.left.clone(), b2.right.clone()));
291                v.push((b1.right.clone(), b2.left.clone()));
292            }
293            _ => return false,
294        }
295    }
296    true
297}
298
299pub fn maximum_depth_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
300    if root.is_none() {
301        return 0;
302    }
303
304    let mut s = vec![(root.unwrap(), 1)];
305    let mut max_depth = 0;
306    while let Some((rc, depth)) = s.pop() {
307        max_depth = max_depth.max(depth);
308
309        let mut rc_mut = rc.borrow_mut();
310        if let Some(left) = rc_mut.left.take() {
311            s.push((left, depth + 1));
312        }
313        if let Some(right) = rc_mut.right.take() {
314            s.push((right, depth + 1));
315        }
316    }
317    max_depth
318}
319
320pub fn convert_sorted_array_to_binary_search_tree(nums: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
321    let n = nums.len();
322
323    match n {
324        0 => None,
325        _ => {
326            let m = n / 2;
327            let mut node = TreeNode::new(nums[m]);
328            node.left = convert_sorted_array_to_binary_search_tree(nums[..m].to_vec());
329            node.right = convert_sorted_array_to_binary_search_tree(nums[m + 1..].to_vec());
330
331            Some(Rc::new(RefCell::new(node)))
332        }
333    }
334}
335
336pub fn balanced_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> bool {
337    let mut dstack = Vec::new();
338    let mut stack = Vec::new();
339    stack.push((1 as i32, 0 as i32, false, false, root));
340    while let Some((depth, left_depth, seen_left, seen_right, node)) = stack.pop() {
341        if let Some(nval) = node.clone() {
342            if !seen_left {
343                stack.push((depth, left_depth, true, false, node.clone()));
344                stack.push((
345                    depth + 1,
346                    left_depth,
347                    false,
348                    false,
349                    nval.borrow().left.clone(),
350                ));
351            } else if !seen_right {
352                stack.push((depth, dstack.pop().unwrap(), true, true, node.clone()));
353                stack.push((
354                    depth + 1,
355                    left_depth,
356                    false,
357                    false,
358                    nval.borrow().right.clone(),
359                ));
360            } else {
361                let ldepth = left_depth;
362                let rdepth = dstack.pop().unwrap();
363                if 1 < (ldepth - rdepth).abs() {
364                    return false;
365                }
366                dstack.push(ldepth.max(rdepth));
367            }
368        } else {
369            dstack.push(depth - 1);
370        }
371    }
372    return true;
373}
374
375pub fn minimum_depth_of_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
376    match root {
377        Some(node) => {
378            let left = minimum_depth_of_binary_tree(node.as_ref().borrow().left.clone());
379            let right = minimum_depth_of_binary_tree(node.as_ref().borrow().right.clone());
380            if left == 0 || right == 0 {
381                return left.max(right) + 1;
382            }
383            left.min(right) + 1
384        }
385        None => 0,
386    }
387}
388
389pub fn path_sum(root: Option<Rc<RefCell<TreeNode>>>, target_sum: i32) -> bool {
390    root.map_or(false, |root| match &*root.borrow() {
391        &TreeNode {
392            val,
393            left: None,
394            right: None,
395        } => val == target_sum,
396        &TreeNode {
397            val,
398            ref left,
399            ref right,
400        } => path_sum(left.clone(), target_sum - val) || path_sum(right.clone(), target_sum - val),
401    })
402}
403
404pub fn pascals_triangle(num_rows: i32) -> Vec<Vec<i32>> {
405    todo!();
406}
407
408pub fn pascals_triangle_ii(row_index: i32) -> Vec<i32> {
409    todo!();
410}
411
412pub fn best_time_to_buy_and_sell_stock(prices: Vec<i32>) -> i32 {
413    todo!();
414}
415
416pub fn valid_palindrome(s: String) -> bool {
417    todo!();
418}
419
420pub fn single_number(nums: Vec<i32>) -> i32 {
421    todo!();
422}
423
424// Linked List Cycle - not possible with current ListNode definition
425
426pub fn binary_tree_preorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
427    todo!();
428}
429
430pub fn binary_tree_postorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
431    todo!();
432}
433
434// Read N Characters Given Read4 - paywalled
435
436// Intersection of Two Linked Lists - not possible with current ListNode definition
437
438// Missing Ranges - paywalled
439
440pub fn excel_sheet_column_title(column_number: i32) -> String {
441    todo!();
442}
443
444pub fn majority_element(nums: Vec<i32>) -> i32 {
445    todo!();
446}
447
448// Two Sum III Data Structure Design - paywalled
449
450pub fn excel_sheet_column_number(column_title: String) -> i32 {
451    todo!();
452}
453
454pub fn reverse_bits(x: u32) -> u32 {
455    todo!();
456}
457
458pub fn number_of_1_bits(n: i32) -> i32 {
459    todo!();
460}
461
462pub fn happy_number(n: i32) -> bool {
463    todo!();
464}
465
466pub fn remove_linked_list_elements(head: Option<Box<ListNode>>, val: i32) -> Option<Box<ListNode>> {
467    todo!();
468}
469
470pub fn isomorphic_strings(s: String, t: String) -> bool {
471    todo!();
472}
473
474pub fn reverse_linked_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
475    todo!();
476}
477
478pub fn contains_duplicate(nums: Vec<i32>) -> bool {
479    todo!();
480}
481
482pub fn contains_duplicate_ii(nums: Vec<i32>, k: i32) -> bool {
483    todo!();
484}
485
486pub fn count_complete_tree_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
487    todo!();
488}
489
490// Implement Stack using Queues - not applicable
491
492pub fn invert_binary_tree(root: Option<Rc<RefCell<TreeNode>>>) -> Option<Rc<RefCell<TreeNode>>> {
493    todo!();
494}
495
496pub fn summary_ranges(nums: Vec<i32>) -> Vec<String> {
497    todo!();
498}
499
500pub fn power_of_two(n: i32) -> bool {
501    todo!();
502}
503
504// Implement Queue using Stacks - not applicable
505
506pub fn palindrome_linked_list(head: Option<Box<ListNode>>) -> bool {
507    todo!();
508}
509
510pub fn valid_anagram(s: String, t: String) -> bool {
511    todo!();
512}
513
514// Shortest Word Distance - paywalled
515
516// Strobogrammatic Number - paywalled
517
518// Meeting Rooms - paywalled
rsleetcode/easy.rs

rsleetcode/
easy.rs
