diff options
Diffstat (limited to 'store/works/solutions/leetcode/rust')
8 files changed, 451 insertions, 0 deletions
diff --git a/store/works/solutions/leetcode/rust/.gitignore b/store/works/solutions/leetcode/rust/.gitignore new file mode 100644 index 0000000..8accfa8 --- /dev/null +++ b/store/works/solutions/leetcode/rust/.gitignore @@ -0,0 +1,5 @@ +/target
+**/*.rs.bk
+Cargo.lock
+
+.vscode
diff --git a/store/works/solutions/leetcode/rust/Cargo.toml b/store/works/solutions/leetcode/rust/Cargo.toml new file mode 100644 index 0000000..a87486e --- /dev/null +++ b/store/works/solutions/leetcode/rust/Cargo.toml @@ -0,0 +1,9 @@ +[package]
+name = "crupest-leetcode"
+version = "0.1.0"
+authors = ["杨宇千 <crupest@outlook.com>"]
+edition = "2018"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
diff --git a/store/works/solutions/leetcode/rust/src/add_two_numbers.rs b/store/works/solutions/leetcode/rust/src/add_two_numbers.rs new file mode 100644 index 0000000..d2ca858 --- /dev/null +++ b/store/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<Box<ListNode>>,
+}
+
+impl ListNode {
+ #[inline]
+ fn new(val: i32) -> Self {
+ ListNode { next: None, val }
+ }
+}
+
+/******************** my code ********************/
+
+use std::ptr::NonNull;
+
+struct List {
+ head: Option<Box<ListNode>>,
+ tail: Option<NonNull<Box<ListNode>>>,
+}
+
+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<Box<ListNode>> {
+ self.head
+ }
+}
+
+impl Solution {
+ pub fn add_two_numbers(
+ l1: Option<Box<ListNode>>,
+ l2: Option<Box<ListNode>>,
+ ) -> Option<Box<ListNode>> {
+ 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<Box<ListNode>>;
+ }
+
+ trait IntoVec {
+ fn into_vec(self) -> Vec<i32>;
+ }
+
+ impl IntoList for Vec<i32> {
+ fn into_list(self) -> Option<Box<ListNode>> {
+ let mut list = List::new();
+ for i in self {
+ list.append(i);
+ }
+ list.to_result()
+ }
+ }
+
+ impl IntoVec for Option<Box<ListNode>> {
+ fn into_vec(self) -> Vec<i32> {
+ 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/store/works/solutions/leetcode/rust/src/find_median_sorted_arrays.rs b/store/works/solutions/leetcode/rust/src/find_median_sorted_arrays.rs new file mode 100644 index 0000000..bbc73f9 --- /dev/null +++ b/store/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<i32>, nums2: Vec<i32>) -> 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/store/works/solutions/leetcode/rust/src/length_of_longest_substring.rs b/store/works/solutions/leetcode/rust/src/length_of_longest_substring.rs new file mode 100644 index 0000000..cbd5e14 --- /dev/null +++ b/store/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/store/works/solutions/leetcode/rust/src/lib.rs b/store/works/solutions/leetcode/rust/src/lib.rs new file mode 100644 index 0000000..fc2e8b4 --- /dev/null +++ b/store/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/store/works/solutions/leetcode/rust/src/longest_palindrome.rs b/store/works/solutions/leetcode/rust/src/longest_palindrome.rs new file mode 100644 index 0000000..659ffe0 --- /dev/null +++ b/store/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/store/works/solutions/leetcode/rust/src/two_sum.rs b/store/works/solutions/leetcode/rust/src/two_sum.rs new file mode 100644 index 0000000..9f400aa --- /dev/null +++ b/store/works/solutions/leetcode/rust/src/two_sum.rs @@ -0,0 +1,24 @@ +use super::Solution;
+
+impl Solution {
+ pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
+ 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 |