From 7fab14e58848e10fce29cb913c5ac8e947f34ab2 Mon Sep 17 00:00:00 2001 From: crupest Date: Fri, 20 Sep 2019 19:23:00 +0800 Subject: import(solutions): ... --- works/solutions/src/add_two_numbers.rs | 160 +++++++++++++++++++++ works/solutions/src/length_of_longest_substring.rs | 49 +++++++ works/solutions/src/lib.rs | 5 + works/solutions/src/two_sum.rs | 24 ++++ 4 files changed, 238 insertions(+) create mode 100644 works/solutions/src/add_two_numbers.rs create mode 100644 works/solutions/src/length_of_longest_substring.rs create mode 100644 works/solutions/src/lib.rs create mode 100644 works/solutions/src/two_sum.rs (limited to 'works/solutions/src') diff --git a/works/solutions/src/add_two_numbers.rs b/works/solutions/src/add_two_numbers.rs new file mode 100644 index 0000000..3e3122a --- /dev/null +++ b/works/solutions/src/add_two_numbers.rs @@ -0,0 +1,160 @@ +use super::Solution; + +/******************** provided code ********************/ +#[derive(PartialEq, Eq, Clone, Debug)] +pub struct ListNode { + pub val: i32, + pub next: Option>, +} + +impl ListNode { + #[inline] + fn new(val: i32) -> Self { + ListNode { next: None, val } + } +} + +/******************** my code ********************/ + +use std::ptr::NonNull; + +struct List { + head: Option>, + tail: NonNull>>, +} + +impl List { + fn new() -> List { + let mut result = List { + head: None, + tail: NonNull::dangling(), + }; + result.tail = NonNull::from(&mut result.head); + return result; + } + + fn append(&mut self, val: i32) { + let node = Some(Box::new(ListNode::new(val))); + unsafe { + match self.tail.as_mut() { + None => { + self.head = node; + self.tail = NonNull::from(&mut self.head); + } + Some(t) => { + t.next = node; + self.tail = NonNull::from(&mut t.next); + } + } + } + } + + fn to_result(self) -> Option> { + self.head + } +} + +impl Solution { + pub fn add_two_numbers( + l1: Option>, + l2: Option>, + ) -> Option> { + let mut l1 = l1; + let mut l2 = l2; + let mut result = List::new(); + let mut carry = false; + + loop { + match l1 { + None => { + while let Some(v) = l2 { + let digit = v.val + if carry { 1 } else { 0 }; + carry = digit > 9; + let digit = digit % 10; + result.append(digit); + l2 = v.next; + } + break; + } + Some(v1) => match l2 { + None => { + let digit = v1.val + if carry { 1 } else { 0 }; + carry = digit > 9; + let digit = digit % 10; + result.append(digit); + l1 = v1.next; + while let Some(v) = l1 { + let digit = v.val + if carry { 1 } else { 0 }; + carry = digit > 9; + let digit = digit % 10; + result.append(digit); + l1 = v.next; + } + break; + } + Some(v2) => { + let digit = v1.val + v2.val + if carry { 1 } else { 0 }; + carry = digit > 9; + let digit = digit % 10; + result.append(digit); + l1 = v1.next; + l2 = v2.next; + } + }, + } + } + + if carry { + result.append(1); + } + + return result.to_result(); + } +} + +#[cfg(test)] +mod test { + use super::{List, ListNode, Solution}; + + trait IntoList { + fn into_list(self) -> Option>; + } + + trait IntoVec { + fn into_vec(self) -> Vec; + } + + impl IntoList for Vec { + fn into_list(self) -> Option> { + let mut list = List::new(); + for i in self { + list.append(i); + } + list.to_result() + } + } + + impl IntoVec for Option> { + fn into_vec(self) -> Vec { + let mut result = Vec::new(); + let mut node = self; + while let Some(v) = node { + result.push(v.val); + node = v.next; + } + result + } + } + + #[test] + fn test() { + assert_eq!( + Solution::add_two_numbers(vec![2, 4, 3].into_list(), vec![5, 6, 4].into_list()).into_vec(), + vec![7, 0, 8] + ); + assert_eq!( + Solution::add_two_numbers(vec![9, 9, 9].into_list(), vec![1].into_list()).into_vec(), + vec![0, 0, 0, 1] + ); + } +} diff --git a/works/solutions/src/length_of_longest_substring.rs b/works/solutions/src/length_of_longest_substring.rs new file mode 100644 index 0000000..cebcc72 --- /dev/null +++ b/works/solutions/src/length_of_longest_substring.rs @@ -0,0 +1,49 @@ +use super::Solution; + +use std::collections::HashMap; + +impl Solution { + pub fn length_of_longest_substring(s: String) -> i32 { + let mut map = HashMap::new(); + let mut last_index = 0; + let mut result = 0; + let bytes = s.as_bytes(); + for (i, c) in bytes.iter().enumerate() { + match map.get(&c) { + Some(vi) if *vi >= last_index => { + last_index = *vi + 1; + map.insert(c, i); + } + _ => { + map.insert(c, i); + let length = i - last_index + 1; + if length > result { + result = length; + } + } + } + } + result as i32 + } +} + +#[cfg(test)] +mod tests { + use super::Solution; + + #[test] + fn test() { + assert_eq!( + Solution::length_of_longest_substring("abcabcbb".to_string()), + 3 + ); + assert_eq!( + Solution::length_of_longest_substring("bbbbb".to_string()), + 1 + ); + assert_eq!( + Solution::length_of_longest_substring("pwwkew".to_string()), + 3 + ); + } +} diff --git a/works/solutions/src/lib.rs b/works/solutions/src/lib.rs new file mode 100644 index 0000000..2bbe624 --- /dev/null +++ b/works/solutions/src/lib.rs @@ -0,0 +1,5 @@ +pub mod two_sum; +pub mod add_two_numbers; +pub mod length_of_longest_substring; + +pub struct Solution; diff --git a/works/solutions/src/two_sum.rs b/works/solutions/src/two_sum.rs new file mode 100644 index 0000000..9f400aa --- /dev/null +++ b/works/solutions/src/two_sum.rs @@ -0,0 +1,24 @@ +use super::Solution; + +impl Solution { + pub fn two_sum(nums: Vec, target: i32) -> Vec { + for (i, v1) in nums.iter().enumerate() { + for (j, v2) in nums.iter().enumerate().skip(i + 1) { + if v1 + v2 == target { + return vec![i as i32, j as i32]; + } + } + } + panic!(); + } +} + +#[cfg(test)] +mod tests { + use super::Solution; + + #[test] + pub fn test() { + assert_eq!(Solution::two_sum(vec![2, 7, 11, 15], 9), vec![0, 1]) + } +} \ No newline at end of file -- cgit v1.2.3