dsa_rust/maw/
maw_01.rs

1/*!
2This is a sandbox crate for chapter 1 of Data Structures and Algorithm Analysis in Java by Mark Allen Weiss
3*/
4
5pub fn recursion(n: i32) {
6    // Defines base case
7    if n >= 10 {
8        // Recursive call to self
9        recursion(n / 10);
10    }
11    // Prints the digit
12    println!("{}", n % 10)
13}
14
15/** My (iterative) version of a binary search implementation;
16 * Takes a sorted array and a key and returns either Some(index) or None */
17pub fn binary_search(a: &[i32], key: i32) -> Option<i32> {
18    use std::cmp::Ordering;
19
20    // Sets initial position of the search boundaries
21    let mut left = 0;
22    let mut right = a.len() - 1;
23
24    // Loops until the search boundaries overlap;
25    // If the loop doesn't find the key, the function
26    // returns None
27    while left <= right {
28        let mid = (left + right) / 2;
29        match a[mid].cmp(&key) {
30            Ordering::Equal => return Some(mid as i32),
31            Ordering::Greater => right = mid - 1,
32            Ordering::Less => left = mid + 1,
33        }
34        //if a[mid] == key {
35        //    return Some(mid as i32);
36        //} else if a[mid] > key {
37        //    right = mid - 1;
38        //} else {
39        //    left = mid + 1;
40        //}
41        //match key {
42        //    val if val == a[mid] => Some(mid as i32),
43        //    _ => Some(0)
44        //};
45        println!("Guess index: {}", &mid);
46    }
47    None
48}
49
50#[test]
51pub fn binary_search_test() {
52    // The target 73 exists at the 37th index
53    let target = 73;
54    let array: [i32; 39] = [
55        1, 4, 5, 6, 10, 12, 16, 21, 23, 24, 25, 27, 31, 32, 33, 35, 37, 39, 40, 41, 42, 43, 45, 47,
56        49, 50, 51, 52, 54, 56, 57, 60, 61, 67, 70, 71, 72, 73, 74,
57    ];
58    let result = binary_search(&array, target).unwrap_or_default();
59    assert_eq!(result, 37)
60}
61
62use std::collections::HashMap;
63
64fn longest_unique_substring(s: &str) -> usize {
65    let mut map = HashMap::new(); // As HashMap<char, i32>
66    let mut left = 0;
67    let mut max_len = 0;
68
69    let chars: Vec<char> = s.chars().collect();
70
71    for right in 0..chars.len() {
72        *map.entry(chars[right]).or_insert(0) += 1;
73
74        while map[&chars[right]] > 1 {
75            *map.get_mut(&chars[left]).unwrap() -= 1;
76            left += 1;
77        }
78
79        max_len = max_len.max(right - left + 1);
80    }
81
82    max_len
83}
84
85fn longest_unique_substring_print(s: &str) -> usize {
86    let mut map = HashMap::new();
87    let mut left = 0;
88    let mut max_len = 0;
89    let mut best_range = (0, 0); // To store (start, end)
90
91    let chars: Vec<char> = s.chars().collect();
92
93    for right in 0..chars.len() {
94        *map.entry(chars[right]).or_insert(0) += 1;
95
96        while map[&chars[right]] > 1 {
97            *map.get_mut(&chars[left]).unwrap() -= 1;
98            left += 1;
99        }
100
101        let current_len = right - left + 1;
102        if current_len > max_len {
103            max_len = current_len;
104            best_range = (left, right);
105        }
106    }
107
108    // Print the substring using the captured indices
109    let result: String = chars[best_range.0..=best_range.1].iter().collect();
110    println!("Longest substring found: \"{result}\" (length {max_len})");
111
112    max_len
113}
114
115#[test]
116fn longest_unique_substring_test() {
117    let s = "this is a llama test.";
118    assert_eq!(longest_unique_substring(s), 6);
119    longest_unique_substring_print(s);
120    //panic!()
121}
dsa_rust/maw/maw_01.rs

dsa_rust/maw/
maw_01.rs
