This is the multi-page printable view of this section. Click here to print.

Return to the regular view of this page.

0200-0249

Solutions to LeetCode Problems 0200-0249.

1 - 0206.反转链表

方法一：链表遍历

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

在遍历解法中, rust Box<ListNode> 由于只用到了所有权的转移，所以实现起来显得较为简洁。

struct Solution;

// Definition for singly-linked list.
#[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 }
    }
}

impl Solution {
    pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut pre = None;
        let mut head = head;
        while let Some(mut p) = head {
            head = p.next;
            p.next = pre;
            pre = Some(p);
        }
        pre
    }
}

方法二：递归链表

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

impl Solution {
    pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        match head {
            None => None,
            Some(mut p) => {
                if p.next.is_none() {
                    return Some(p);
                }
                let next = p.next.take();
                let mut ret = Solution::reverse_list(next);
                let mut q = ret.as_mut().unwrap();
                while q.next.is_some() {
                    q = q.next.as_mut().unwrap();
                }
                q.as_mut().next = Some(p);
                ret
            }
        }
    }
}

2 - 0234.回文链表

一次遍历

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

在写该题目的 rust 解法时发现凭此时的代码水平只能借助数组辅助比较，具体代码见 rust tab。想要尽力实现类似其他语言一样在找到中间节点之后，反转后半部分链表的逻辑，但 rust 不可变性这一原则的存在限制了我的下一步工作。完美的解法让 copilot 来给我演示吧！

// Definition for singly-linked list.
// #[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
//     }
//   }
// }
impl Solution {
    pub fn is_palindrome(head: Option<Box<ListNode>>) -> bool {
        // find middle
        let mut fast = &head;
        let mut slow = &head;
        let mut nums1 = vec![];
        while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
            let nt = &fast.as_ref().unwrap().next;
            fast = &nt.as_ref().unwrap().next;
            nums1.push(slow.as_ref().unwrap().val);
            slow = &slow.as_ref().unwrap().next;
        }
        let mut nums2 = vec![];
        while slow.is_some() {
            nums2.push(slow.as_ref().unwrap().val);
            slow = &slow.as_ref().unwrap().next;
        }
        nums2.reverse();
        for i in 0..nums1.len() {
            if nums1[i] != nums2[i] {
                return false;
            }
        }
        true
    }
}
impl Solution {
    pub fn is_palindrome(head: Option<Box<ListNode>>) -> bool {
        let mut values = Vec::new();
        let mut current = head;
        while let Some(node) = current {
            values.push(node.val);
            current = node.next;
        }
        let mut left = 0;
        let mut right = values.len() - 1;
        while left < right {
            if values[left] != values[right] {
                return false;
            }
            left += 1;
            right -= 1;
        }
        true
    }
}

显然copilot 的代码(第二个rust tab)比我写的好看且简洁，但是空间复杂度并没有降低，仍旧需要调整。

3 - 0238.除自身以外数组的乘积

方法一：左右乘积列表

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

impl Solution {
    pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
        let (mut ans, n) = (Vec::new(), nums.len());
        let (mut left, mut right) = (vec![1; n], vec![1; n]);
        for i in 1..n {
            left[i] = left[i - 1] * nums[i - 1];
        }
        for i in (0..n - 1).rev() {
            right[i] = right[i + 1] * nums[i + 1];
        }
        for i in 0..n {
            ans.push(left[i] * right[i]);
        }
        ans
    }
}

4 - 0239.滑动窗口最大值

方法一：滑动窗口+双端队列

时间复杂度 $O(n)$，空间复杂度 $O(k)$。

impl Solution {
    pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let mut ans = Vec::new();
        let mut deque = std::collections::VecDeque::new();
        for i in 0..nums.len() {
            while !deque.is_empty() && nums[*deque.back().unwrap()] < nums[i] {
                deque.pop_back();
            }
            deque.push_back(i);
            if i >= (k - 1) as usize {
                let elem = nums[*deque.front().unwrap()];
                ans.push(elem);
                if elem == nums[i + 1 - k as usize] {
                    deque.pop_front();
                }
            }
        }
        ans
    }
}

5 - 0240.搜索二维矩阵 II

方法一：Z 字形查找

时间复杂度 $O(m+n)$，空间复杂度 $O(1)$。

impl Solution {
    pub fn search_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
        let (m, n) = (matrix.len(), matrix[0].len());
        let (mut x, mut y) = (0, (n - 1) as i32);
        while x < m && y >= 0 {
            if matrix[x][y as usize] > target {
                y -= 1;
            } else if matrix[x][y as usize] < target {
                x += 1;
            } else {
                return true;
            }
        }
        false
    }
}