leetcode 算法笔记 —— 简单题

简单题

1、两数之和

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut mp = HashMap::new();
        for i in 0..nums.len() {
            let num = nums[i];
            if let Some(x) = mp.get(&(target - num)) {
                return vec![*x, i as i32];
            } else {
                mp.insert(num, i as i32);
            }
        }
        vec![]
    }
}

考察 Map 的使用

2、回文数

impl Solution {
    pub fn is_palindrome(x: i32) -> bool {
        if x < 0 || (x != 0 && x % 10 == 0) {
            return false;
        }
        //通过不断取余与短除，算出来回文的左右两个数字，再比较
        let mut x = x;
        let mut y = 0;
        while x > y {
            y = y * 10 + x % 10;
            x = x / 10;
        }
        x == y || x == y / 10
    }
}

考察数字的取余与短除

3、罗马数字转整数

impl Solution {
    pub fn roman_to_int(s: String) -> i32 {
        //遍历，累加，存储上一个字符
        s.chars().fold((0, ' '), |acc, x| {
            match (acc.1, x) {
               ('I', 'V') => (acc.0 + 3, 'V'),
                ('I', 'X') => (acc.0 + 8, 'X'),
                ('X', 'L') => (acc.0 + 30, 'L'),
                ('X', 'C') => (acc.0 + 80, 'C'),
                ('C', 'D') => (acc.0 + 300, 'D'),
                ('C', 'M') => (acc.0 + 800, 'M'),
                (_, 'I') => (acc.0 + 1, 'I'),
                (_, 'V') => (acc.0 + 5, 'V'),
                (_, 'X') => (acc.0 + 10, 'X'),
                (_, 'L') => (acc.0 + 50, 'L'),
                (_, 'C') => (acc.0 + 100, 'C'),
                (_, 'D') => (acc.0 + 500, 'D'),
                (_, 'M') => (acc.0 + 1000, 'M'),
                (_, _) => unreachable!(),
            }
        }).0
    }
}

考察 fold 遍历与多初始值（元组）的应用

4、最长公共前缀

impl Solution {
    pub fn longest_common_prefix(strs: Vec<String>) -> String {
        // 每次比较都是跟之前的一个比较，直到全部比较完毕，并且公共前缀是越比较越短的，因此只需要保留前一个的数据即可。
        // 2 个字符串的比较，可以用 zip + take_while 方法
        strs.split_first().map(|(first, rest)| {
            // 开始时，first即为最长的可能前缀，让它与所有其他字符串比较
            rest.into_iter().fold(first.as_str(), |acc, s| {
                // 从acc中取出
                &acc[
                    // 从0到s（即下一个字符串）
                    0..s.bytes()
                        // 与acc（即当前的最长前缀）
                        .zip(acc.bytes())
                        // 相同的前缀
                        .take_while(|(x, y)| x == y)
                        // 的长度
                        .count()
                    ] // 作为新的acc继续迭代
            })
                // 将结果转换为string
                .to_string()
        })
            // 若无，返回空字符串
            .unwrap_or(String::new())
    }
}

考察fold 遍历 与 zip、take_while 的应用

5、有效的括号

impl Solution {
    pub fn is_valid(s: String) -> bool {
        let mut stack: Vec<char> = vec!['a'];
        for c in s.chars() {
            match c {
                '(' | '[' | '{' => stack.push(c),
                ')' => {if stack.pop().unwrap() != '(' {return false}},
                ']' => {if stack.pop().unwrap() != '[' {return false}},
                '}' => {if stack.pop().unwrap() != '{' {return false}},
                _ => (),
            }
        }
        stack.len() == 1
    }
}

考察栈的应用

6、合并两个有序列表

#[derive(Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode {
            next: None,
            val,
        }
    }
}

impl Solution {
    pub fn merge_two_lists(list1: Option<Box<ListNode>>, list2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        match (list1, list2) {
            (Some(n1), Some(n2)) =>
                if n1.val < n2.val {
                    Some(Box::new(ListNode { val: n1.val, next: Self::merge_two_lists(n1.next, Some(n2)) }))
                } else {
                    Some(Box::new(ListNode { val: n2.val, next: Self::merge_two_lists(Some(n1), n2.next) }))
                }
            (Some(n1), None) => Some(n1),
            (None, Some(n2)) => Some(n2),
            _ => None
        }
    }
}

考察二叉树结构+递归的应用

7、删除有序数组的重复项

impl Solution {
    //因为是单调递增的，那么相等的元素是挨着的，只要判断该元素是否与他前一个元素是否相等就可以知道该元素是否出现过啦。
    pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
        let mut i = 1;
        for j in 1..nums.len() {
            if nums[j] != nums[j - 1] {
                nums[i] = nums[j];
                i += 1;
            }
        }
        i as i32
    }
}

考察双指针算法

8、移除元素

impl Solution {
    pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 {
        //双指针法
        // nums.retain(|&x| x != val);
        // nums.len() as i32
        let mut i = 0;
        for j in 0..nums.len() {
            if nums[j] != val {
                nums[i] = nums[j];
                i += 1;
            }
        }
        i as i32
    }
}

考察双指针法

9、搜索插入位置

impl Solution {
    pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {
        // nums.binary_search(&target).unwrap_or_else(|x|x) as i32
        let mut l: usize = 0;
        let mut r: usize = nums.len();
        while l < r {
            let m = (l + r) / 2;
            if target == nums[m] {
                return m as i32;
            } else if nums[m] > target {
                // r = m -1 可能导致 r 为负数。
                r = m;
            } else {
                // 如果令 l = m，由于 (l + r) /2 是向下取整，如果取得 m = l，这会导致死循环。而 m 已经排除，故另令 l = m + 1。
                // 如果目标值在 m 与 m+1 之间，按题目要求取 m+1，亦符合要求。
                l = m + 1;
            }
        }
        l as i32
    }
}

考察二分法