move

16 files changed, 524 insertions, 0 deletions

diff --git a/rust/Cargo.lock b/rust/Cargo.lock
new file mode 100644
index 0000000..d5eb8a3
--- /dev/null
+++ b/rust/Cargo.lock
@@ -0,0 +1,7 @@
+# This file is automatically @generated by Cargo.
+# It is not intended for manual editing.
+version = 3
+
+[[package]]
+name = "leetcode"
+version = "0.1.0"
diff --git a/rust/Cargo.toml b/rust/Cargo.toml
new file mode 100644
index 0000000..dedfbd3
--- /dev/null
+++ b/rust/Cargo.toml
@@ -0,0 +1,6 @@
+[package]
+name = "leetcode"
+version = "0.1.0"
+edition = "2021"
+
+[dependencies]
diff --git a/rust/src/bin/p0001.rs b/rust/src/bin/p0001.rs
new file mode 100644
index 0000000..70128c9
--- /dev/null
+++ b/rust/src/bin/p0001.rs
@@ -0,0 +1,25 @@
+use std::collections::HashMap;
+
+struct Solution {}
+impl Solution {
+    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
+        let mut num_map : HashMap<i32, usize> = HashMap::new();
+
+        let mut i:usize = 0;
+        loop {
+            let index = target - nums[i];
+            match num_map.get(&index) {
+                Some(j) => break vec![i as i32, *j as i32],
+                None => {
+                    num_map.insert(nums[i], i);
+                    i = i + 1;
+                    continue;
+                }
+            }
+        }
+    }
+}
+
+fn main() {
+    println!("{:?}", Solution::two_sum(vec![2, 7, 11, 15], 9));
+}
\ No newline at end of file
diff --git a/rust/src/bin/p0002.rs b/rust/src/bin/p0002.rs
new file mode 100644
index 0000000..d8acf94
--- /dev/null
+++ b/rust/src/bin/p0002.rs
@@ -0,0 +1,49 @@
+use leetcode::list::*;
+
+struct Solution {}
+
+impl Solution {
+    pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
+        let mut result: Option<Box<ListNode>> = None;
+        let mut cur1 = &l1;
+        let mut cur2 = &l2;
+        let mut carry: i32 = 0;
+        {
+            let mut cur_res = &mut result;
+            loop {
+                if *cur1 == None && *cur2 == None && carry == 0 {
+                    break;
+                } else {
+                    let n1 = match cur1 {
+                        Some(node) => {
+                            cur1 = &cur1.as_ref().unwrap().next;
+                            node.val
+                        },
+                        None => 0
+                    };
+                    let n2 = match cur2 {
+                        Some(node) => {
+                            cur2 = &cur2.as_ref().unwrap().next;
+                            node.val
+                        },
+                        None => 0
+                    };
+                    let n = (n1 + n2 + carry) % 10;
+                    carry = if (n1 + n2 + carry) >= 10 { 1 } else { 0 };
+                    *cur_res = Some(Box::new(ListNode::new(n)));
+                    cur_res = &mut cur_res.as_mut().unwrap().next;
+                    continue;
+                }
+            }
+        }
+        result
+    }
+}
+
+fn test(l1: Vec<i32>, l2: Vec<i32>) -> Vec<i32> {
+    list2vector(Solution::add_two_numbers(vector2list(l1), vector2list(l2)))
+}
+
+fn main() {
+    println!("{:?}", test(vec![1,2,3], vec![4,5,6]));
+}
diff --git a/rust/src/bin/p0003.rs b/rust/src/bin/p0003.rs
new file mode 100644
index 0000000..7293c13
--- /dev/null
+++ b/rust/src/bin/p0003.rs
@@ -0,0 +1,34 @@
+struct Solution {}
+
+impl Solution {
+    pub fn length_of_longest_substring(s: String) -> i32 {
+        let mut set: [u8;256] = [0;256];
+        let mut i1: usize = 0;
+        let mut i2: usize = 0;
+        let mut max: i32 = 0;
+        loop {
+            if i1 >= s.len() { break; }
+            if set[s.as_bytes()[i1] as usize] == 0 {
+                set[s.as_bytes()[i1] as usize] = 1;
+                i1 = i1 + 1;
+                if i1 as i32 - i2 as i32 > max { max = i1 as i32 - i2 as i32 }
+                continue;
+            } else {
+                loop {
+                    set[s.as_bytes()[i2]  as usize] = 0;
+                    i2 = i2 + 1;
+                    if set[s.as_bytes()[i1] as usize] == 0 {
+                        break;
+                    } else {
+                        continue;
+                    }
+                }
+            }
+        }
+        max
+    }
+}
+
+fn main() {
+    println!("{:?}", Solution::length_of_longest_substring("abcabcbb".to_string()));
+}
\ No newline at end of file
diff --git a/rust/src/bin/p0004.rs b/rust/src/bin/p0004.rs
new file mode 100644
index 0000000..2925500
--- /dev/null
+++ b/rust/src/bin/p0004.rs
@@ -0,0 +1,96 @@
+use std::cmp::{min, max};
+
+impl Solution {
+    fn vec_get(v: &Vec<i32>, n: i32) -> i32 {
+        if n < 0 {
+            return i32::MIN;
+        }
+        if n >= v.len() as i32 {
+            return i32::MAX;
+        }
+        return v[n as usize];
+    }
+    pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
+        let mut n1 = &nums1;
+        let mut n2 = &nums2;
+        if n1.len() < n2.len() {
+            n1 = &nums2;
+            n2 = &nums1;
+        }
+
+        if n2.len() == 0 || n1[n1.len()-1] <= n2[0] {
+            if (n1.len() + n2.len()) % 2 == 0 {
+                let mid_index = (n1.len() + n2.len()) / 2;
+                let right: i32;
+                if mid_index == n1.len() {
+                    right = n2[0];
+                } else {
+                    right = n1[mid_index];
+                }
+                return (n1[mid_index - 1] + right) as f64 / 2.0;
+            } else {
+                let mid_index = (n1.len() + n2.len()) / 2;
+                return n1[mid_index] as f64;
+            }
+        }
+        if n2[n2.len()-1] <= n1[0] {
+            if (n1.len() + n2.len()) % 2 == 0 {
+                let mid_index = (n1.len() + n2.len()) / 2 - n2.len();
+                let left: i32;
+                if mid_index <= 0 {
+                    left = n2[n2.len() - 1];
+                } else {
+                    left = n1[mid_index - 1];
+                }
+                return (left + n1[mid_index]) as f64 / 2.0;
+            } else {
+                let mid_index = (n1.len() + n2.len()) / 2 - n2.len();
+                return n1[mid_index] as f64;
+            }
+        }
+
+        let mut left: i32 = 0;
+        let mut right: i32 = n1.len() as i32 - 1;
+        let mut mid: i32 = 0;
+        let mut mid2: i32 = 0;
+        loop {
+            if left > right { break; }
+            println!("left: {}, right: {}", left, right);
+            mid = (left + right) / 2;
+            mid2 = (n1.len() + n2.len()) as i32 / 2 - (1 + mid) - 1;
+            if mid2 < -1 {
+                right = mid - 1;
+                continue;
+            }
+            if mid2 >= n2.len() as i32 {
+                left = mid + 1;
+                continue;
+            }
+            if n1[mid as usize] > Self::vec_get(n2, mid2 + 1) {
+                right = mid - 1;
+                continue;
+            }
+            if n1[mid as usize + 1] < Self::vec_get(n2, mid2) {
+                left = mid + 1;
+                continue;
+            }
+            break;
+        }
+        if (n1.len() + n2.len()) % 2 == 0 {
+            (max(n1[mid as usize], Self::vec_get(n2, mid2))
+                + min(n1[mid as usize + 1], Self::vec_get(n2, mid2 + 1))) as f64  / 2.0
+        } else {
+            min(n1[mid as usize +1], Self::vec_get(n2, mid2 + 1)) as f64
+        }
+    }
+}
+
+struct Solution {}
+fn main() {
+    println!("{}", Solution::find_median_sorted_arrays(vec![1,2,3], vec![4,5,6]));
+    println!("{}", Solution::find_median_sorted_arrays(vec![4,5,6], vec![1,2,3]));
+    println!("{}", Solution::find_median_sorted_arrays(vec![1,2,3], vec![5,6]));
+    println!("{}", Solution::find_median_sorted_arrays(vec![4,5,6], vec![1,2]));
+    println!("{}", Solution::find_median_sorted_arrays(vec![1,3,5], vec![2,4,6]));
+    println!("{}", Solution::find_median_sorted_arrays(vec![3], vec![1,2,4,5]));
+}
\ No newline at end of file
diff --git a/rust/src/bin/p0005.rs b/rust/src/bin/p0005.rs
new file mode 100644
index 0000000..01b368d
--- /dev/null
+++ b/rust/src/bin/p0005.rs
@@ -0,0 +1,67 @@
+impl Solution {
+    fn check_odd(s: &String, i: i32) -> (i32, i32, i32) {
+        let mut r = 0;
+        loop {
+            let next = r + 1;
+            if i - next < 0
+                    || i + next >= s.len() as i32
+                    || s.as_bytes()[(i-next) as usize] != s.as_bytes()[(i+next) as usize] {
+                break;
+            }
+            r = next;
+        }
+        let len = 2 * r + 1;
+        let start = i - r;
+        let end = i + r;
+        (len, start, end)
+    }
+
+    fn check_even(s: &String, i: i32) -> (i32, i32, i32) {
+        let mut r = 0;
+        loop {
+            let next = r + 1;
+            if i - next + 1 < 0
+                || i + next >= s.len() as i32
+                || s.as_bytes()[(i-next+1) as usize] != s.as_bytes()[(i+next) as usize] {
+                break;
+            }
+            r = next;
+        }
+        let len = 2 * r;
+        let start = i - r + 1;
+        let end = i + r;
+        (len, start, end)
+    }
+
+    fn check_palindrome_len(s: &String, i: i32) -> (i32, i32, i32) {
+        let (len1, start1, end1) = Self::check_odd(s, i);
+        let (len2, start2, end2) = Self::check_even(s, i);
+        if len2 > len1 {
+            (len2, start2, end2)
+        } else {
+            (len1, start1, end1)
+        }
+    }
+
+    pub fn longest_palindrome(s: String) -> String {
+        let mut maxpalinlen = -1;
+        let mut start: i32 = 0;
+        let mut end: i32 = 0;
+        for i in 0..s.len() {
+            let (palin_len, pstart, pend) = Self::check_palindrome_len(&s, i as i32);
+            if palin_len > maxpalinlen {
+                maxpalinlen = palin_len;
+                start = pstart;
+                end = pend;
+            }
+        }
+        s[start as usize ..(end + 1) as usize].to_string()
+    }
+}
+
+struct Solution {}
+
+fn main () {
+    println!("{}", Solution::longest_palindrome("babad".to_string()));
+    println!("{}", Solution::longest_palindrome("cbbd".to_string()));
+}
diff --git a/rust/src/bin/p0006.rs b/rust/src/bin/p0006.rs
new file mode 100644
index 0000000..92e4b6f
--- /dev/null
+++ b/rust/src/bin/p0006.rs
@@ -0,0 +1,40 @@
+impl Solution {
+    pub fn convert(s: String, num_rows: i32) -> String {
+        if num_rows <= 1 {
+            return s;
+        }
+        let mut x = 0;
+        let mut y = 0;
+        let mut path: Vec<(i32,i32)> = vec!();
+        let mut is_down = true;
+        for _ in 0..s.len() {
+            path.push((x, y));
+            if is_down {
+                y = y + 1;
+                if y == num_rows - 1 {
+                    is_down = false;
+                }
+            } else {
+                y = y - 1;
+                x = x + 1;
+                if y == 0 {
+                    is_down = true;
+                }
+            }
+        }
+        let mut lines: Vec<String> = vec!();
+        for _ in 0..num_rows {
+            lines.push("".to_string());
+        }
+        for i in 0..s.len() {
+            let (_,y) = path[i];
+            lines[y as usize].push(s.as_bytes()[i] as char);
+        }
+        lines.join("")
+    }
+}
+
+struct Solution {}
+fn main() {
+    println!("{}", Solution::convert("PAYPALISHIRING".to_string(), 3));
+}
\ No newline at end of file
diff --git a/rust/src/bin/p0009.rs b/rust/src/bin/p0009.rs
new file mode 100644
index 0000000..4ecb473
--- /dev/null
+++ b/rust/src/bin/p0009.rs
@@ -0,0 +1,13 @@
+impl Solution {
+    pub fn is_palindrome(x: i32) -> bool {
+        if x < 0 {
+            return false;
+        }
+        let s = x.to_string();
+        let rs: String = s.chars().rev().collect();
+        return s == rs;
+    }
+}
+
+struct Solution {}
+fn main() {}
\ No newline at end of file
diff --git a/rust/src/bin/p0013.rs b/rust/src/bin/p0013.rs
new file mode 100644
index 0000000..b5f8a62
--- /dev/null
+++ b/rust/src/bin/p0013.rs
@@ -0,0 +1,33 @@
+impl Solution {
+    fn char_to_int(c: char) -> i32 {
+        match c {
+            'I' => 1,
+            'V' => 5,
+            'X' => 10,
+            'L' => 50,
+            'C' => 100,
+            'D' => 500,
+            'M' => 1000,
+            _ => 0,
+        }
+    }
+    pub fn roman_to_int(s: String) -> i32 {
+        let mut sum = 0;
+        for i in 0..s.len() {
+            if i < s.len() - 1 {
+                if Self::char_to_int(s.as_bytes()[i as usize] as char)
+                        < Self::char_to_int(s.as_bytes()[i+1 as usize] as char) {
+                    sum = sum - Self::char_to_int(s.as_bytes()[i as usize] as char);
+                    continue;
+                }
+            }
+            sum = sum + Self::char_to_int(s.as_bytes()[i as usize] as char);
+        }
+        sum
+    }
+}
+
+struct Solution {}
+fn main() {
+    println!("{}", Solution::roman_to_int("MCMXCIV".to_string()));
+}
\ No newline at end of file
diff --git a/rust/src/bin/p0014.rs b/rust/src/bin/p0014.rs
new file mode 100644
index 0000000..e85ef8f
--- /dev/null
+++ b/rust/src/bin/p0014.rs
@@ -0,0 +1,30 @@
+impl Solution {
+    pub fn longest_common_prefix(strs: Vec<String>) -> String {
+        if strs.is_empty() { return "".to_string(); }
+        let mut l: i32 = -1;
+        let mut brk = false;
+        for i in 0..strs[0].len() {
+            let c = strs[0].as_bytes()[i];
+            for j in 1..strs.len() {
+                if strs[j].len() <= i || strs[j].as_bytes()[i] != c {
+                    brk = true;
+                    break;
+                }
+            }
+            if brk { break; }
+            l = l + 1;
+        }
+        if l < 0 {
+            return "".to_string();
+        }
+        strs[0][0..(l+1) as usize].to_string()
+    }
+}
+
+struct Solution {}
+fn main() {
+    println!("{}", Solution::longest_common_prefix(vec![
+        "fliower".to_string(),
+        "fliow".to_string(),
+        "fliight".to_string()]));
+}
\ No newline at end of file
diff --git a/rust/src/bin/p0021.rs b/rust/src/bin/p0021.rs
new file mode 100644
index 0000000..d0ce9e6
--- /dev/null
+++ b/rust/src/bin/p0021.rs
@@ -0,0 +1,60 @@
+use leetcode::list::*;
+
+impl Solution {
+    pub fn merge_two_lists(list1: Option<Box<ListNode>>, list2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
+        let mut p1 = &list1;
+        let mut p2 = &list2;
+        let mut result: Vec<i32> = vec!();
+        loop {
+            let v1: i32;
+            let v2: i32;
+            match p1 {
+                None => {
+                    match p2 {
+                        None => break,
+                        Some(px) => {
+                            result.push(px.val);
+                            p2 = &px.next;
+                            continue;
+                        }
+                    }
+                },
+                Some(p1) => { v1 = p1.val; },
+            }
+            match p2 {
+                None => {
+                    match p1 {
+                        None => break,
+                        Some(px) => {
+                            result.push(px.val);
+                            p1 = &px.next;
+                            continue;
+                        }
+                    }
+                },
+                Some(p2) => { v2 = p2.val; },
+            }
+            if v1 <= v2 {
+                result.push(v1);
+                p1 = match p1 {
+                    Some(px) => &px.next,
+                    None => p1,
+                };
+            } else {
+                result.push(v2);
+                p2 = match p2 {
+                    Some(px) => &px.next,
+                    None => p2,
+                };
+            }
+        }
+        vector2list(result)
+    }
+}
+
+struct Solution {}
+fn main() {
+    println!("{:?}", list2vector(
+        Solution::merge_two_lists(vector2list(vec!(1,3,5)),
+                                  vector2list(vec!(2,4,6)))));
+}
\ No newline at end of file
diff --git a/rust/src/bin/p0028.rs b/rust/src/bin/p0028.rs
new file mode 100644
index 0000000..c830ac4
--- /dev/null
+++ b/rust/src/bin/p0028.rs
@@ -0,0 +1,20 @@
+impl Solution {
+    pub fn str_str(haystack: String, needle: String) -> i32 {
+        if needle.len() > haystack.len() { return -1; }
+        for i in 0..haystack.len() - needle.len()+1 {
+            let mut failed = false;
+            for j in 0..needle.len() {
+                if haystack.as_bytes()[i+j] != needle.as_bytes()[j] {
+                    failed = true;
+                    break;
+                }
+            }
+            if !failed { return i as i32; }
+        }
+        -1
+    }
+}
+struct Solution { }
+fn main() {
+    println!("{}", Solution::str_str("abaaa".to_string(), "abb".to_string()));
+}
\ No newline at end of file
diff --git a/rust/src/lib.rs b/rust/src/lib.rs
new file mode 100644
index 0000000..651aed7
--- /dev/null
+++ b/rust/src/lib.rs
@@ -0,0 +1 @@
+pub mod list;
\ No newline at end of file
diff --git a/rust/src/list.rs b/rust/src/list.rs
new file mode 100644
index 0000000..d033cfe
--- /dev/null
+++ b/rust/src/list.rs
@@ -0,0 +1,40 @@
+#[derive(PartialEq, Eq, Clone, Debug)]
+pub struct ListNode {
+    pub val: i32,
+    pub next: Option<Box<ListNode>>
+}
+//
+impl ListNode {
+    #[inline]
+    pub fn new(val: i32) -> Self {
+        ListNode {
+            next: None,
+            val
+        }
+    }
+}
+
+pub fn vector2list(vec: Vec<i32>) -> Option<Box<ListNode>> {
+    let mut result: Option<Box<ListNode>> = None;
+    for i in 0..vec.len() {
+        let mut new_result = Some(Box::new(ListNode::new(vec[vec.len() - i - 1])));
+        new_result.as_mut().unwrap().next = result;
+        result = new_result;
+    }
+    result
+}
+
+pub fn list2vector(lst: Option<Box<ListNode>>) -> Vec<i32> {
+    let mut result: Vec<i32> = Vec::new();
+    let mut cur = &lst;
+    loop {
+        match cur {
+            None => break,
+            Some(node) => {
+                result.push(node.val);
+                cur = &node.next;
+            },
+        }
+    }
+    result
+}
\ No newline at end of file
diff --git a/rust/src/main.rs b/rust/src/main.rs
new file mode 100644
index 0000000..e7a11a9
--- /dev/null
+++ b/rust/src/main.rs
@@ -0,0 +1,3 @@
+fn main() {
+    println!("Hello, world!");
+}