From b3d06fff749d20b0a756b7a40e39f51ae48ffb17 Mon Sep 17 00:00:00 2001 From: 杨宇千 Date: Fri, 20 Sep 2019 19:23:00 +0800 Subject: import(solutions): ... --- works/solutions/.gitignore | 3 +++ 1 file changed, 3 insertions(+) create mode 100644 works/solutions/.gitignore (limited to 'works/solutions/.gitignore') diff --git a/works/solutions/.gitignore b/works/solutions/.gitignore new file mode 100644 index 0000000..6936990 --- /dev/null +++ b/works/solutions/.gitignore @@ -0,0 +1,3 @@ +/target +**/*.rs.bk +Cargo.lock -- cgit v1.2.3 From fa7b2234e710c5b6406d7cbb40b5b4e134b5e254 Mon Sep 17 00:00:00 2001 From: crupest Date: Fri, 20 Sep 2019 20:11:27 +0800 Subject: import(solutions): ... --- works/solutions/.gitignore | 2 ++ works/solutions/src/add_two_numbers.rs | 24 ++++++++++++------------ 2 files changed, 14 insertions(+), 12 deletions(-) (limited to 'works/solutions/.gitignore') diff --git a/works/solutions/.gitignore b/works/solutions/.gitignore index 6936990..f03942d 100644 --- a/works/solutions/.gitignore +++ b/works/solutions/.gitignore @@ -1,3 +1,5 @@ /target **/*.rs.bk Cargo.lock + +.vscode diff --git a/works/solutions/src/add_two_numbers.rs b/works/solutions/src/add_two_numbers.rs index 3e3122a..d2ca858 100644 --- a/works/solutions/src/add_two_numbers.rs +++ b/works/solutions/src/add_two_numbers.rs @@ -20,30 +20,29 @@ use std::ptr::NonNull; struct List { head: Option>, - tail: NonNull>>, + tail: Option>>, } impl List { fn new() -> List { - let mut result = List { + List { head: None, - tail: NonNull::dangling(), - }; - result.tail = NonNull::from(&mut result.head); - return result; + tail: None, + } } fn append(&mut self, val: i32) { let node = Some(Box::new(ListNode::new(val))); unsafe { - match self.tail.as_mut() { + match self.tail { None => { self.head = node; - self.tail = NonNull::from(&mut self.head); + self.tail = Some(NonNull::from(self.head.as_mut().unwrap())); } - Some(t) => { - t.next = node; - self.tail = NonNull::from(&mut t.next); + Some(mut t) => { + let last_node = t.as_mut(); + last_node.next = node; + self.tail = Some(NonNull::from(last_node.next.as_mut().unwrap())); } } } @@ -149,7 +148,8 @@ mod test { #[test] fn test() { assert_eq!( - Solution::add_two_numbers(vec![2, 4, 3].into_list(), vec![5, 6, 4].into_list()).into_vec(), + Solution::add_two_numbers(vec![2, 4, 3].into_list(), vec![5, 6, 4].into_list()) + .into_vec(), vec![7, 0, 8] ); assert_eq!( -- cgit v1.2.3 From 5b3584fcc79c87f87edebbf08f2f9c144f298eed Mon Sep 17 00:00:00 2001 From: crupest Date: Thu, 7 May 2020 22:37:39 +0800 Subject: import(solutions): Move rust codes into sub dir. --- works/solutions/.gitignore | 5 - works/solutions/Cargo.toml | 9 -- works/solutions/rust/.gitignore | 5 + works/solutions/rust/Cargo.toml | 9 ++ works/solutions/rust/src/add_two_numbers.rs | 160 +++++++++++++++++++++ .../rust/src/find_median_sorted_arrays.rs | 101 +++++++++++++ .../rust/src/length_of_longest_substring.rs | 47 ++++++ works/solutions/rust/src/lib.rs | 7 + works/solutions/rust/src/longest_palindrome.rs | 98 +++++++++++++ works/solutions/rust/src/two_sum.rs | 24 ++++ works/solutions/src/add_two_numbers.rs | 160 --------------------- works/solutions/src/find_median_sorted_arrays.rs | 101 ------------- works/solutions/src/length_of_longest_substring.rs | 47 ------ works/solutions/src/lib.rs | 7 - works/solutions/src/longest_palindrome.rs | 98 ------------- works/solutions/src/two_sum.rs | 24 ---- 16 files changed, 451 insertions(+), 451 deletions(-) delete mode 100644 works/solutions/.gitignore delete mode 100644 works/solutions/Cargo.toml create mode 100644 works/solutions/rust/.gitignore create mode 100644 works/solutions/rust/Cargo.toml create mode 100644 works/solutions/rust/src/add_two_numbers.rs create mode 100644 works/solutions/rust/src/find_median_sorted_arrays.rs create mode 100644 works/solutions/rust/src/length_of_longest_substring.rs create mode 100644 works/solutions/rust/src/lib.rs create mode 100644 works/solutions/rust/src/longest_palindrome.rs create mode 100644 works/solutions/rust/src/two_sum.rs delete mode 100644 works/solutions/src/add_two_numbers.rs delete mode 100644 works/solutions/src/find_median_sorted_arrays.rs delete mode 100644 works/solutions/src/length_of_longest_substring.rs delete mode 100644 works/solutions/src/lib.rs delete mode 100644 works/solutions/src/longest_palindrome.rs delete mode 100644 works/solutions/src/two_sum.rs (limited to 'works/solutions/.gitignore') diff --git a/works/solutions/.gitignore b/works/solutions/.gitignore deleted file mode 100644 index f03942d..0000000 --- a/works/solutions/.gitignore +++ /dev/null @@ -1,5 +0,0 @@ -/target -**/*.rs.bk -Cargo.lock - -.vscode diff --git a/works/solutions/Cargo.toml b/works/solutions/Cargo.toml deleted file mode 100644 index 1073387..0000000 --- a/works/solutions/Cargo.toml +++ /dev/null @@ -1,9 +0,0 @@ -[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/rust/.gitignore b/works/solutions/rust/.gitignore new file mode 100644 index 0000000..f03942d --- /dev/null +++ b/works/solutions/rust/.gitignore @@ -0,0 +1,5 @@ +/target +**/*.rs.bk +Cargo.lock + +.vscode diff --git a/works/solutions/rust/Cargo.toml b/works/solutions/rust/Cargo.toml new file mode 100644 index 0000000..1073387 --- /dev/null +++ b/works/solutions/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/rust/src/add_two_numbers.rs b/works/solutions/rust/src/add_two_numbers.rs new file mode 100644 index 0000000..d2ca858 --- /dev/null +++ b/works/solutions/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/rust/src/find_median_sorted_arrays.rs b/works/solutions/rust/src/find_median_sorted_arrays.rs new file mode 100644 index 0000000..bbc73f9 --- /dev/null +++ b/works/solutions/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/rust/src/length_of_longest_substring.rs b/works/solutions/rust/src/length_of_longest_substring.rs new file mode 100644 index 0000000..cbd5e14 --- /dev/null +++ b/works/solutions/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/rust/src/lib.rs b/works/solutions/rust/src/lib.rs new file mode 100644 index 0000000..b2f3416 --- /dev/null +++ b/works/solutions/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/rust/src/longest_palindrome.rs b/works/solutions/rust/src/longest_palindrome.rs new file mode 100644 index 0000000..659ffe0 --- /dev/null +++ b/works/solutions/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/rust/src/two_sum.rs b/works/solutions/rust/src/two_sum.rs new file mode 100644 index 0000000..9f400aa --- /dev/null +++ b/works/solutions/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 diff --git a/works/solutions/src/add_two_numbers.rs b/works/solutions/src/add_two_numbers.rs deleted file mode 100644 index d2ca858..0000000 --- a/works/solutions/src/add_two_numbers.rs +++ /dev/null @@ -1,160 +0,0 @@ -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/src/find_median_sorted_arrays.rs b/works/solutions/src/find_median_sorted_arrays.rs deleted file mode 100644 index bbc73f9..0000000 --- a/works/solutions/src/find_median_sorted_arrays.rs +++ /dev/null @@ -1,101 +0,0 @@ -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/src/length_of_longest_substring.rs b/works/solutions/src/length_of_longest_substring.rs deleted file mode 100644 index cbd5e14..0000000 --- a/works/solutions/src/length_of_longest_substring.rs +++ /dev/null @@ -1,47 +0,0 @@ -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/src/lib.rs b/works/solutions/src/lib.rs deleted file mode 100644 index b2f3416..0000000 --- a/works/solutions/src/lib.rs +++ /dev/null @@ -1,7 +0,0 @@ -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/src/longest_palindrome.rs b/works/solutions/src/longest_palindrome.rs deleted file mode 100644 index 659ffe0..0000000 --- a/works/solutions/src/longest_palindrome.rs +++ /dev/null @@ -1,98 +0,0 @@ -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/src/two_sum.rs b/works/solutions/src/two_sum.rs deleted file mode 100644 index 9f400aa..0000000 --- a/works/solutions/src/two_sum.rs +++ /dev/null @@ -1,24 +0,0 @@ -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 From a3a2519a087f710c8820d94584648aaba75528d7 Mon Sep 17 00:00:00 2001 From: crupest Date: Thu, 7 May 2020 23:17:16 +0800 Subject: import(solutions): Add problem 6 . --- works/solutions/.gitignore | 1 + works/solutions/cpp/.gitignore | 1 + works/solutions/cpp/6.cpp | 56 ++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 58 insertions(+) create mode 100644 works/solutions/.gitignore create mode 100644 works/solutions/cpp/.gitignore create mode 100644 works/solutions/cpp/6.cpp (limited to 'works/solutions/.gitignore') diff --git a/works/solutions/.gitignore b/works/solutions/.gitignore new file mode 100644 index 0000000..600d2d3 --- /dev/null +++ b/works/solutions/.gitignore @@ -0,0 +1 @@ +.vscode \ No newline at end of file diff --git a/works/solutions/cpp/.gitignore b/works/solutions/cpp/.gitignore new file mode 100644 index 0000000..adb36c8 --- /dev/null +++ b/works/solutions/cpp/.gitignore @@ -0,0 +1 @@ +*.exe \ No newline at end of file diff --git a/works/solutions/cpp/6.cpp b/works/solutions/cpp/6.cpp new file mode 100644 index 0000000..f1d947c --- /dev/null +++ b/works/solutions/cpp/6.cpp @@ -0,0 +1,56 @@ +#include +#include + +using std::string; + +class Solution +{ +public: + string convert(string s, int numRows) + { + if (numRows == 1) + return s; + + const auto length = s.size(); + const int count_per_group = numRows * 2 - 2; + string result; + result.reserve(length); + for (int row = 0; row < numRows; row++) + { + if (row == 0) + { + for (int p = 0; p < length; p += count_per_group) + result += s[p]; + } + else if (row == numRows - 1) + { + for (int p = row; p < length; p += count_per_group) + result += s[p]; + } + else + { + bool former = true; + const auto former_gap = count_per_group - row * 2; + const auto latter_gap = count_per_group - former_gap; + for (int p = row; p < length; p += (former ? former_gap : latter_gap), former = !former) + result += s[p]; + } + } + return result; + } +}; + +int main() +{ + Solution s; + + auto result1 = s.convert("PAYPALISHIRING", 3); + auto result2 = s.convert("PAYPALISHIRING", 4); + std::cout + << s.convert("A", 1) << '\n' + << result1 << '\n' + << "PAHNAPLSIIGYIR\n" + << result2 << '\n' + << "PINALSIGYAHRPI\n"; + return 0; +} \ No newline at end of file -- cgit v1.2.3 From 839f18ec81d82af016e042674aec1ce2912ae84e Mon Sep 17 00:00:00 2001 From: crupest Date: Tue, 23 Feb 2021 21:27:58 +0800 Subject: import(solutions): Add acwing problem 2 (pack problem). --- works/solutions/.gitignore | 4 +++- works/solutions/acwing/2-2.cpp | 29 +++++++++++++++++++++++++++++ works/solutions/acwing/2.cpp | 30 ++++++++++++++++++++++++++++++ 3 files changed, 62 insertions(+), 1 deletion(-) create mode 100644 works/solutions/acwing/2-2.cpp create mode 100644 works/solutions/acwing/2.cpp (limited to 'works/solutions/.gitignore') diff --git a/works/solutions/.gitignore b/works/solutions/.gitignore index 600d2d3..f676862 100644 --- a/works/solutions/.gitignore +++ b/works/solutions/.gitignore @@ -1 +1,3 @@ -.vscode \ No newline at end of file +.vscode +*.exe +*.pdb diff --git a/works/solutions/acwing/2-2.cpp b/works/solutions/acwing/2-2.cpp new file mode 100644 index 0000000..de812f4 --- /dev/null +++ b/works/solutions/acwing/2-2.cpp @@ -0,0 +1,29 @@ +#include +#include + +int N, V; +int v[1001]; +int w[1001]; +int states[1001]; + +int main() { + std::cin >> N >> V; + + for (int i = 1; i <= N; i++) { + std::cin >> v[i] >> w[i]; + } + + for (int i = 1; i <= N; i++) { + for (int j = V; j >= 0; j--) { + if (j >= v[i]) { + states[j] = std::max(states[j], states[j - v[i]] + w[i]); + } else { + states[j] = states[j]; + } + } + } + + std::cout << states[V]; + + return 0; +} diff --git a/works/solutions/acwing/2.cpp b/works/solutions/acwing/2.cpp new file mode 100644 index 0000000..1a75c19 --- /dev/null +++ b/works/solutions/acwing/2.cpp @@ -0,0 +1,30 @@ +#include +#include + +int N, V; +int v[1001]; +int w[1001]; +int states[1001][1001]; + +int main() { + std::cin >> N >> V; + + for (int i = 1; i <= N; i++) { + std::cin >> v[i] >> w[i]; + } + + for (int i = 1; i <= N; i++) { + for (int j = V; j >= 0; j--) { + if (j >= v[i]) { + states[i][j] = + std::max(states[i - 1][j], states[i - 1][j - v[i]] + w[i]); + } else { + states[i][j] = states[i - 1][j]; + } + } + } + + std::cout << states[N][V]; + + return 0; +} -- cgit v1.2.3 From 5242b780d8c6aee430bc4a655679ddd5814016b9 Mon Sep 17 00:00:00 2001 From: crupest Date: Sat, 6 Mar 2021 16:56:43 +0800 Subject: import(solutions): Add acwing 1219. --- works/solutions/.gitignore | 1 + works/solutions/acwing/1219.cpp | 26 ++++++++++++++++++++++++++ 2 files changed, 27 insertions(+) create mode 100644 works/solutions/acwing/1219.cpp (limited to 'works/solutions/.gitignore') diff --git a/works/solutions/.gitignore b/works/solutions/.gitignore index f676862..fd9075a 100644 --- a/works/solutions/.gitignore +++ b/works/solutions/.gitignore @@ -1,3 +1,4 @@ .vscode *.exe *.pdb +*.ilk diff --git a/works/solutions/acwing/1219.cpp b/works/solutions/acwing/1219.cpp new file mode 100644 index 0000000..9538e94 --- /dev/null +++ b/works/solutions/acwing/1219.cpp @@ -0,0 +1,26 @@ +#include +#include + +int w, m, n; + +int row(int x) { return (x - 1) / w; } + +int col(int x, int r) { + int result = (x - 1) % w; + if (r % 2) { + result = w - 1 - result; + } + return result; +} + +int main() { + std::cin >> w >> m >> n; + int m_r = row(m); + int m_c = col(m, m_r); + int n_r = row(n); + int n_c = col(n, n_r); + + std::cout << std::abs(m_r - n_r) + std::abs(m_c - n_c); + + return 0; +} -- cgit v1.2.3 From b0cb34e532c7b94d04cda246d2080bafd86aad38 Mon Sep 17 00:00:00 2001 From: crupest Date: Tue, 30 Mar 2021 20:09:44 +0800 Subject: import(solutions): Add acwing 2069. --- works/solutions/.gitignore | 3 ++ works/solutions/acwing/2069.cpp | 82 +++++++++++++++++++++++++++++++++++++++++ 2 files changed, 85 insertions(+) create mode 100644 works/solutions/acwing/2069.cpp (limited to 'works/solutions/.gitignore') diff --git a/works/solutions/.gitignore b/works/solutions/.gitignore index fd9075a..951dd99 100644 --- a/works/solutions/.gitignore +++ b/works/solutions/.gitignore @@ -2,3 +2,6 @@ *.exe *.pdb *.ilk +*.obj +*.exp +*.lib diff --git a/works/solutions/acwing/2069.cpp b/works/solutions/acwing/2069.cpp new file mode 100644 index 0000000..fbfa6d2 --- /dev/null +++ b/works/solutions/acwing/2069.cpp @@ -0,0 +1,82 @@ +#include +#include + +struct Node { + int m = 0; + Node *set; + Node *left = nullptr; + Node *right = nullptr; + + Node() : set(this) {} + + void SetParent(Node *parent, bool l) { + set = parent; + l ? parent->left = this : parent->right = this; + } + + Node *GetSetRepresentative() { + Node *r = this; + while (r->set != r) { + r = r->set; + } + set = r; + return set; + } + + bool has_dfs = false; + + void Dfs() { + if (has_dfs) + return; + has_dfs = true; + if (left != nullptr) + left->Dfs(m); + if (right != nullptr) + right->Dfs(m); + } + + void Dfs(int c) { + m += c; + if (left != nullptr) + left->Dfs(m); + if (right != nullptr) + right->Dfs(m); + } +}; + +Node nodes[10010]; + +int main() { + std::ios_base::sync_with_stdio(false); + std::cin.tie(nullptr); + + int n, m; + + std::cin >> n >> m; + + for (int i = 0; i < m; i++) { + int operation, a, b; + std::cin >> operation >> a >> b; + + if (operation == 1) { + auto ra = nodes[a].GetSetRepresentative(), + rb = nodes[b].GetSetRepresentative(); + + if (ra != rb) { + auto node = new Node; + ra->SetParent(node, true); + rb->SetParent(node, false); + } + } else { + nodes[a].GetSetRepresentative()->m += b; + } + } + + for (int i = 1; i <= n; i++) { + auto &node = nodes[i]; + node.GetSetRepresentative()->Dfs(); + std::cout << node.m << ' '; + } + + return 0; +} -- cgit v1.2.3 From 1f9626144c4856d0a7d93b125175879d5a6685d4 Mon Sep 17 00:00:00 2001 From: crupest Date: Sun, 26 Sep 2021 12:50:45 +0800 Subject: import(solutions): ... --- works/solutions/.gitignore | 2 ++ works/solutions/leetcode/cpp/371.cpp | 25 +++++++++++++++++++++++++ works/solutions/leetcode/lccup/2021/1.cpp | 27 +++++++++++++++++++++++++++ works/solutions/leetcode/week/260/1.cpp | 21 +++++++++++++++++++++ works/solutions/leetcode/week/260/2.cpp | 29 +++++++++++++++++++++++++++++ 5 files changed, 104 insertions(+) create mode 100644 works/solutions/leetcode/cpp/371.cpp create mode 100644 works/solutions/leetcode/lccup/2021/1.cpp create mode 100644 works/solutions/leetcode/week/260/1.cpp create mode 100644 works/solutions/leetcode/week/260/2.cpp (limited to 'works/solutions/.gitignore') diff --git a/works/solutions/.gitignore b/works/solutions/.gitignore index 951dd99..aab2f3b 100644 --- a/works/solutions/.gitignore +++ b/works/solutions/.gitignore @@ -5,3 +5,5 @@ *.obj *.exp *.lib + +.DS_Store diff --git a/works/solutions/leetcode/cpp/371.cpp b/works/solutions/leetcode/cpp/371.cpp new file mode 100644 index 0000000..3a7bc8b --- /dev/null +++ b/works/solutions/leetcode/cpp/371.cpp @@ -0,0 +1,25 @@ + +class Solution { +public: + int getSum(int a, int b) { + unsigned x = a, y = b; + + unsigned carry = 0; + + unsigned result = 0; + + for (int i = 0; i < sizeof(int) * 8; i++) { + unsigned mask = 1 << i; + + unsigned n = x & mask ? 1 : 0, m = y & mask ? 1 : 0; + + if (n ^ m ^ carry) { + result |= mask; + } + + carry = n & m || n & carry || m & carry; + } + + return static_cast(result); + } +}; diff --git a/works/solutions/leetcode/lccup/2021/1.cpp b/works/solutions/leetcode/lccup/2021/1.cpp new file mode 100644 index 0000000..550da04 --- /dev/null +++ b/works/solutions/leetcode/lccup/2021/1.cpp @@ -0,0 +1,27 @@ +struct TreeNode { + int val; + TreeNode *left; + TreeNode *right; + TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} +}; + +class Solution { +public: + int visited[1001] {0}; + int result = 0; + + void DFS(TreeNode* r) { + if (!visited[r->val]) { + result += 1; + visited[r->val] = 1; + } + + if (r->left) DFS(r->left); + if (r->right) DFS(r->right); + } + + int numColor(TreeNode* root) { + DFS(root); + return result; + } +}; \ No newline at end of file diff --git a/works/solutions/leetcode/week/260/1.cpp b/works/solutions/leetcode/week/260/1.cpp new file mode 100644 index 0000000..4d6c78d --- /dev/null +++ b/works/solutions/leetcode/week/260/1.cpp @@ -0,0 +1,21 @@ +#include + +using std::vector; + +class Solution { +public: + int maximumDifference(vector& nums) { + int result = -1; + + for (int i = 1; i < nums.size(); i++) { + for (int j = 0; j < i; j++) { + int diff = nums[i] - nums[j]; + if (diff > result) { + result = diff; + } + } + } + + return result == 0 ? -1 : result; + } +}; \ No newline at end of file diff --git a/works/solutions/leetcode/week/260/2.cpp b/works/solutions/leetcode/week/260/2.cpp new file mode 100644 index 0000000..86c4cf2 --- /dev/null +++ b/works/solutions/leetcode/week/260/2.cpp @@ -0,0 +1,29 @@ +#include + +using std::vector; + +#include +#include +#include + +class Solution { +public: + long long gridGame(vector> &grid) { + int s = grid.front().size(); + std::vector row0(grid[0].cbegin(), grid[0].cend()); + std::vector row1(grid[1].cbegin(), grid[1].cend()); + std::vector ps0, ps1; + + std::partial_sum(row0.cbegin(), row0.cend(), std::back_inserter(ps0)); + std::partial_sum(row1.cbegin(), row1.cend(), std::back_inserter(ps1)); + + long long r = std::numeric_limits::max(); + + for (int i = 0; i < s; i++) { + long long c = std::max(ps0.back() - ps0[i], i ? ps1[i - 1] : 0); + r = std::min(r, c); + } + + return r; + } +}; \ No newline at end of file -- cgit v1.2.3