From 185ef9fcb0e59f13e9ee0ccb261693cdaddebab0 Mon Sep 17 00:00:00 2001 From: crupest Date: Tue, 23 Feb 2021 21:07:19 +0800 Subject: import(solutions): Move leetcode solutions to subdir. --- works/solutions/leetcode/rust/.gitignore | 5 + works/solutions/leetcode/rust/Cargo.toml | 9 ++ .../solutions/leetcode/rust/src/add_two_numbers.rs | 160 +++++++++++++++++++++ .../leetcode/rust/src/find_median_sorted_arrays.rs | 101 +++++++++++++ .../rust/src/length_of_longest_substring.rs | 47 ++++++ works/solutions/leetcode/rust/src/lib.rs | 7 + .../leetcode/rust/src/longest_palindrome.rs | 98 +++++++++++++ works/solutions/leetcode/rust/src/two_sum.rs | 24 ++++ 8 files changed, 451 insertions(+) create mode 100644 works/solutions/leetcode/rust/.gitignore create mode 100644 works/solutions/leetcode/rust/Cargo.toml create mode 100644 works/solutions/leetcode/rust/src/add_two_numbers.rs create mode 100644 works/solutions/leetcode/rust/src/find_median_sorted_arrays.rs create mode 100644 works/solutions/leetcode/rust/src/length_of_longest_substring.rs create mode 100644 works/solutions/leetcode/rust/src/lib.rs create mode 100644 works/solutions/leetcode/rust/src/longest_palindrome.rs create mode 100644 works/solutions/leetcode/rust/src/two_sum.rs (limited to 'works/solutions/leetcode/rust') diff --git a/works/solutions/leetcode/rust/.gitignore b/works/solutions/leetcode/rust/.gitignore new file mode 100644 index 0000000..8accfa8 --- /dev/null +++ b/works/solutions/leetcode/rust/.gitignore @@ -0,0 +1,5 @@ +/target +**/*.rs.bk +Cargo.lock + +.vscode diff --git a/works/solutions/leetcode/rust/Cargo.toml b/works/solutions/leetcode/rust/Cargo.toml new file mode 100644 index 0000000..a87486e --- /dev/null +++ b/works/solutions/leetcode/rust/Cargo.toml @@ -0,0 +1,9 @@ +[package] +name = "crupest-leetcode" +version = "0.1.0" +authors = ["杨宇千 "] +edition = "2018" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] diff --git a/works/solutions/leetcode/rust/src/add_two_numbers.rs b/works/solutions/leetcode/rust/src/add_two_numbers.rs new file mode 100644 index 0000000..d2ca858 --- /dev/null +++ b/works/solutions/leetcode/rust/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: Option>>, +} + +impl List { + fn new() -> List { + List { + head: None, + tail: None, + } + } + + fn append(&mut self, val: i32) { + let node = Some(Box::new(ListNode::new(val))); + unsafe { + match self.tail { + None => { + self.head = node; + self.tail = Some(NonNull::from(self.head.as_mut().unwrap())); + } + Some(mut t) => { + let last_node = t.as_mut(); + last_node.next = node; + self.tail = Some(NonNull::from(last_node.next.as_mut().unwrap())); + } + } + } + } + + 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/leetcode/rust/src/find_median_sorted_arrays.rs b/works/solutions/leetcode/rust/src/find_median_sorted_arrays.rs new file mode 100644 index 0000000..bbc73f9 --- /dev/null +++ b/works/solutions/leetcode/rust/src/find_median_sorted_arrays.rs @@ -0,0 +1,101 @@ +use super::Solution; + +impl Solution { + pub fn find_median_sorted_arrays(nums1: Vec, nums2: Vec) -> f64 { + let (len_a, len_b) = (nums1.len(), nums2.len()); + let (a, len_a, b, len_b) = if len_a <= len_b { + (nums1, len_a, nums2, len_b) + } else { + (nums2, len_b, nums1, len_a) + }; + let index_sum = (a.len() + b.len() + 1) / 2; + let (mut i_min, mut i_max) = (0, len_a); + + while i_min != i_max { + let i = (i_min + i_max) / 2; + let j = index_sum - i; + if j != 0 && a[i] < b[j - 1] { + i_min = i + 1; + } else { + i_max = i; + } + } + + let i = i_min; + let j = index_sum - i; + + let mut v = vec![]; + if i != 0 { + v.push(a[i - 1]); + } + if j != 0 { + v.push(b[j - 1]); + } + if i != len_a { + v.push(a[i]); + } + if j != len_b { + v.push(b[j]); + } + v.sort_unstable(); + + if (len_a + len_b) % 2 == 0 { + match v.len() { + 2 => (v[0] as f64 + v[1] as f64) / 2.0, + 3 => { + if i == 0 { + (v[0] as f64 + v[1] as f64) / 2.0 + } else { + (v[1] as f64 + v[2] as f64) / 2.0 + } + } + 4 => (v[1] as f64 + v[2] as f64) / 2.0, + _ => panic!(), + } + } else { + match v.len() { + 1 | 2 => v[0] as f64, + 3 => { + if i == 0 { + v[0] as f64 + } else { + v[1] as f64 + } + } + 4 => v[1] as f64, + _ => panic!(), + } + } + } +} + +#[cfg(test)] +mod tests { + use super::Solution; + + #[test] + fn test() { + assert_eq!(Solution::find_median_sorted_arrays(vec![3], vec![]), 3.0); + assert_eq!(Solution::find_median_sorted_arrays(vec![3], vec![4]), 3.5); + assert_eq!( + Solution::find_median_sorted_arrays(vec![3, 4, 5], vec![1, 2, 6]), + 3.5 + ); + assert_eq!( + Solution::find_median_sorted_arrays(vec![3, 4], vec![1, 2, 6]), + 3.0 + ); + assert_eq!( + Solution::find_median_sorted_arrays(vec![1], vec![2, 3, 4]), + 2.5 + ); + assert_eq!( + Solution::find_median_sorted_arrays(vec![4], vec![1, 2, 3, 5]), + 3.0 + ); + assert_eq!( + Solution::find_median_sorted_arrays(vec![1, 2, 3], vec![4, 5, 6]), + 3.5 + ); + } +} diff --git a/works/solutions/leetcode/rust/src/length_of_longest_substring.rs b/works/solutions/leetcode/rust/src/length_of_longest_substring.rs new file mode 100644 index 0000000..cbd5e14 --- /dev/null +++ b/works/solutions/leetcode/rust/src/length_of_longest_substring.rs @@ -0,0 +1,47 @@ +use super::Solution; + +impl Solution { + pub fn length_of_longest_substring(s: String) -> i32 { + let mut map: [i32; std::u8::MAX as usize] = [-1; std::u8::MAX as usize]; + let mut last_index: i32 = 0; + let mut result: i32 = 0; + let bytes = s.as_bytes(); + for (i, c) in bytes.iter().enumerate() { + let i = i as i32; + let c = *c as usize; + let li = map[c]; + if li >= last_index { + last_index = li + 1; + map[c] = i; + } else { + map[c] = i; + let length = i - last_index + 1; + if length > result { + result = length; + } + } + } + result + } +} + +#[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/leetcode/rust/src/lib.rs b/works/solutions/leetcode/rust/src/lib.rs new file mode 100644 index 0000000..fc2e8b4 --- /dev/null +++ b/works/solutions/leetcode/rust/src/lib.rs @@ -0,0 +1,7 @@ +pub mod two_sum; +pub mod add_two_numbers; +pub mod length_of_longest_substring; +pub mod find_median_sorted_arrays; +pub mod longest_palindrome; + +pub struct Solution; diff --git a/works/solutions/leetcode/rust/src/longest_palindrome.rs b/works/solutions/leetcode/rust/src/longest_palindrome.rs new file mode 100644 index 0000000..659ffe0 --- /dev/null +++ b/works/solutions/leetcode/rust/src/longest_palindrome.rs @@ -0,0 +1,98 @@ +use super::Solution; + +impl Solution { + pub fn longest_palindrome(s: String) -> String { + let bytes = s.as_bytes(); + let len = bytes.len(); + + return match len { + 0 => "".to_string(), + 1 => s, + _ => { + let mut max_length = 1; + let mut result = &bytes[0..1]; + + for i in 1..len { + let mut left_iter = bytes[..i].iter().enumerate().rev(); + let mut odd_right_iter = bytes.iter().enumerate().skip(i + 1); + let mut even_right_iter = bytes.iter().enumerate().skip(i); + let mut count_odd = true; + let mut count_even = true; + while count_odd || count_even { + match left_iter.next() { + Some((index_left, left)) => { + if count_odd { + match odd_right_iter.next() { + Some((index_right, right)) => { + if right == left { + let length = index_right - index_left + 1; + if length > max_length { + max_length = length; + result = &bytes[index_left..index_right + 1]; + } + } else { + count_odd = false; + } + } + None => count_odd = false, + } + } + if count_even { + match even_right_iter.next() { + Some((index_right, right)) => { + if right == left { + let length = index_right - index_left + 1; + if length > max_length { + max_length = length; + result = &bytes[index_left..index_right + 1]; + } + } else { + count_even = false; + } + } + None => count_even = false, + } + } + } + None => break, + } + } + } + String::from_utf8(Vec::from(result)).unwrap() + } + }; + } +} + +#[cfg(test)] +mod tests { + use super::Solution; + + #[test] + fn test() { + assert_eq!( + Solution::longest_palindrome("bb".to_string()), + "bb".to_string() + ); + assert_eq!( + Solution::longest_palindrome("abb".to_string()), + "bb".to_string() + ); + assert_eq!( + Solution::longest_palindrome("abbc".to_string()), + "bb".to_string() + ); + assert_eq!( + Solution::longest_palindrome("abccb".to_string()), + "bccb".to_string() + ); + assert_eq!( + Solution::longest_palindrome("abcdcbd".to_string()), + "bcdcb".to_string() + ); + assert_eq!( + Solution::longest_palindrome("aaaabaaa".to_string()), + "aaabaaa".to_string() + ); + } +} diff --git a/works/solutions/leetcode/rust/src/two_sum.rs b/works/solutions/leetcode/rust/src/two_sum.rs new file mode 100644 index 0000000..9f400aa --- /dev/null +++ b/works/solutions/leetcode/rust/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