Java C++題解leetcode817連結串列元件範例

2022-10-14 14:01:13

題目要求

思路：模擬

Java

class Solution {
    public int numComponents(ListNode head, int[] nums) {
        int res = 0;
        Set<Integer> set = new HashSet<>();
        for (int x : nums)
            set.add(x); // 轉存nums
        while (head != null) {
            if (set.contains(head.val)) {
                while (head != null && set.contains(head.val))
                    head = head.next;
                res++;
            }
            else {
                head = head.next;
            }
        }
        return res;
    }
}

時間複雜度：O(n)，遍歷整個連結串列
空間複雜度：O(n)，轉存nums

C++

class Solution {
public:
    int numComponents(ListNode* head, vector<int>& nums) {
        int res = 0;
        unordered_set<int> set(nums.begin(), nums.end()); // 轉存nums
        while (head) {
            if (set.count(head->val)) {
                while (head && set.count(head->val))
                    head = head->next;
                res++;
            }
            else {
                head = head->next;
            }
        }
        return res;
    }
};

時間複雜度：O(n)，遍歷整個連結串列
空間複雜度：O(n)，轉存nums

Rust

use std::collections::HashSet;
impl Solution {
    pub fn num_components(mut head: Option<Box<ListNode>>, nums: Vec<i32>) -> i32 {
        let mut head = head.as_ref();
        let mut res = 0;
        let mut status = false; // 是否處於同一個元件
        while let Some(node) = head {
            if nums.contains(&node.val) {
                if !status {
                    res += 1;
                    status = true;
                }
            } else {
                status = false;
            }
            head = node.next.as_ref();
        }
        res
    }
}

時間複雜度：O(n)，遍歷整個連結串列
空間複雜度：O(n)，轉存nums

總結

簡單模擬題，沒想到轉存用雜湊表的內建函數，還想著要排序方便查詢……對於消耗空間的方法總是不太敏感。

以上就是Java C++題解leetcode817連結串列元件範例的詳細內容，更多關於Java C++題解連結串列元件的資料請關注it145.com其它相關文章！

Java C++題解leetcode817連結串列元件範例

目錄

題目要求

思路：模擬

Java

C++

Rust

總結

熱門文章