欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java?C++?算法題解leetcode652尋找重復(fù)子樹

 更新時間:2022年09月14日 09:34:56   作者:AnjaVon  
這篇文章主要為大家介紹了Java?C++?算法題解leetcode652尋找重復(fù)子樹示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪

題目要求

思路一:DFS+序列化

  • 設(shè)計一種規(guī)則將所有子樹序列化,保證不同子樹的序列化字符串不同,相同子樹的序列化串相同。
  • 用哈希表存所有的字符串,統(tǒng)計出現(xiàn)次數(shù)即可。
    • 定義map中的關(guān)鍵字(key)為子樹的序列化結(jié)果,值(value)為出現(xiàn)次數(shù)。
  • 此處采用的方式是在DFS遍歷順序下的每個節(jié)點后添加"-",遇到空節(jié)點置當(dāng)前位為空格。

Java

class Solution {
    Map<String, Integer> map = new HashMap<>();
    List<TreeNode> res = new ArrayList<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        DFS(root);
        return res;
    }
    String DFS(TreeNode root) {
        if (root == null)
            return " ";
        StringBuilder sb = new StringBuilder();
        sb.append(root.val).append("-");
        sb.append(DFS(root.left)).append(DFS(root.right));
        String sub = sb.toString(); // 當(dāng)前子樹
        map.put(sub, map.getOrDefault(sub, 0) + 1);
        if (map.get(sub) == 2) // ==保證統(tǒng)計所有且只記錄一次
            res.add(root);
        return sub;
    }
}
  • 時間復(fù)雜度:O(n^2)
  • 空間復(fù)雜度:O(n)

C++

  • 要把節(jié)點值轉(zhuǎn)換為字符串格式……嗚嗚嗚卡了半天才意識到
class Solution {
public:
    unordered_map<string, int> map;
    vector<TreeNode*> res;
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        DFS(root);
        return res;
    }
    string DFS(TreeNode* root) {
        if (root == nullptr)
            return " ";
        string sub = "";
        sub += to_string(root->val); // 轉(zhuǎn)換為字符串?。?!
        sub += "-";
        sub += DFS(root->left);
        sub += DFS(root->right);
        if (map.count(sub))
            map[sub]++;
        else
            map[sub] = 1;
        if (map[sub] == 2) // ==保證統(tǒng)計所有且只記錄一次
            res.emplace_back(root);
        return sub;
    }
};
  • 時間復(fù)雜度:O(n^2)
  • 空間復(fù)雜度:O(n)

Rust

  • 在判定等于222的地方卡了好久,報錯borrow of moved value sub,沒認(rèn)真學(xué)rust導(dǎo)致閉包沒搞好,然后根據(jù)報錯內(nèi)容猜了下,把上面的加了個clone()果然好了。
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::HashMap;
impl Solution {
    pub fn find_duplicate_subtrees(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
        let mut res = Vec::new();
        fn DFS(root: &Option<Rc<RefCell<TreeNode>>>, map: &mut HashMap<String, i32>, res: &mut Vec<Option<Rc<RefCell<TreeNode>>>>) -> String {
            if root.is_none() {
                return " ".to_string();
            }
            let sub = format!("{}-{}{}", root.as_ref().unwrap().borrow().val, DFS(&root.as_ref().unwrap().borrow().left, map, res), DFS(&root.as_ref().unwrap().borrow().right, map, res));
            *map.entry(sub.clone()).or_insert(0) += 1;
            if map[&sub] == 2 { // ==保證統(tǒng)計所有且只記錄一次
                res.push(root.clone());
            }
            sub            
        }
        DFS(&root, &mut HashMap::new(), &mut res);
        res
    }
}
  • 時間復(fù)雜度:O(n^2)
  • 空間復(fù)雜度:O(n)

思路二:DFS+三元組

  • 和上面其實差不多,三元組本質(zhì)上也是一種序列化形式,可以指代唯一的子樹結(jié)構(gòu):
    • 三元組中的內(nèi)容為(根節(jié)點值,左子樹標(biāo)識,右子樹標(biāo)識)(根節(jié)點值, 左子樹標(biāo)識,右子樹標(biāo)識)(根節(jié)點值,左子樹標(biāo)識,右子樹標(biāo)識);
      • 這個標(biāo)識是給每個不同結(jié)構(gòu)的子樹所賦予的唯一值,可用于標(biāo)識其結(jié)構(gòu)。
    • 所以三元組相同則判定子樹結(jié)構(gòu)相同;
    • 該方法使用序號標(biāo)識子樹結(jié)構(gòu),規(guī)避了思路一中越來越長的字符串,也減小了時間復(fù)雜度。
  • 定義哈希表mapmapmap存儲每種結(jié)構(gòu):
    • 關(guān)鍵字為三元組的字符串形式,值為當(dāng)前子樹的標(biāo)識和出現(xiàn)次數(shù)所構(gòu)成的數(shù)對。
    • 其中標(biāo)識用從000開始的整數(shù)flagflagflag表示。

Java

class Solution {
    Map<String, Pair<Integer, Integer>> map = new HashMap<String, Pair<Integer, Integer>>();
    List<TreeNode> res = new ArrayList<>();
    int flag = 0;
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        DFS(root);
        return res;
    }
    public int DFS(TreeNode root) {
        if (root == null)
            return 0;  
        int[] tri = {root.val, DFS(root.left), DFS(root.right)};
        String sub = Arrays.toString(tri); // 當(dāng)前子樹
        if (map.containsKey(sub)) { // 已統(tǒng)計過
            int key = map.get(sub).getKey();
            int cnt = map.get(sub).getValue();
            map.put(sub, new Pair<Integer, Integer>(key, ++cnt));
            if (cnt == 2) // ==保證統(tǒng)計所有且只記錄一次
                res.add(root);
            return key;
        }
        else { // 首次出現(xiàn)
            map.put(sub, new Pair<Integer, Integer>(++flag, 1));
            return flag;
        }
    }
}
  • 時間復(fù)雜度:O(n)
  • 空間復(fù)雜度:O(n)

C++

class Solution {
public:
    unordered_map<string, pair<int, int>> map;
    vector<TreeNode*> res;
    int flag = 0;
    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        DFS(root);
        return res;
    }
    int DFS(TreeNode* root) {
        if (root == nullptr)
            return 0;
        string sub = to_string(root->val) + to_string(DFS(root->left)) + to_string(DFS(root->right)); // 當(dāng)前子樹
        if (auto cur = map.find(sub); cur != map.end()) { // 已統(tǒng)計過
            int key = cur->second.first;
            int cnt = cur->second.second;
            map[sub] = {key, ++cnt};
            if (cnt == 2) // ==保證統(tǒng)計所有且只記錄一次
                res.emplace_back(root);
            return key;
        } 
        else { // 首次出現(xiàn)
            map[sub] = {++flag, 1};
            return flag;
        }
    }
};
  • 時間復(fù)雜度:O(n)
  • 空間復(fù)雜度:O(n)

Rust

  • 三元組不好搞,所以用了兩個二元哈希表替代一個存放三元組和標(biāo)識,另一個存放標(biāo)識與出現(xiàn)次數(shù)。
use std::rc::Rc;
use std::cell::RefCell;
use std::collections::HashMap;
impl Solution {
    pub fn find_duplicate_subtrees(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
        let mut res = Vec::new();
        fn DFS(root: &Option<Rc<RefCell<TreeNode>>>, sub_flag: &mut HashMap<String, i32>, flag_cnt: &mut HashMap<i32, i32>, res: &mut Vec<Option<Rc<RefCell<TreeNode>>>>, flag: &mut i32) -> i32 {
            if root.is_none() {
                return 0;
            }
            let (lflag, rflag) = (DFS(&root.as_ref().unwrap().borrow().left, sub_flag, flag_cnt, res, flag), DFS(&root.as_ref().unwrap().borrow().right, sub_flag, flag_cnt, res, flag));
            let sub = format!("{}{}{}", root.as_ref().unwrap().borrow().val, lflag, rflag);
            if sub_flag.contains_key(&sub) { // 已統(tǒng)計過
                let key = sub_flag[&sub];
                let cnt = flag_cnt[&key] + 1;
                flag_cnt.insert(key, cnt);
                if cnt == 2 { // ==保證統(tǒng)計所有且只記錄一次
                    res.push(root.clone());
                }
                key
            }
            else { // 首次出現(xiàn)
                *flag += 1;
                sub_flag.insert(sub, *flag);
                flag_cnt.insert(*flag, 1);
                *flag
            }
        }
        DFS(&root, &mut HashMap::new(), &mut HashMap::new(), &mut res, &mut 0);
        res
    }
}
  • 時間復(fù)雜度:O(n)
  • 空間復(fù)雜度:O(n)

總結(jié)

兩種方法本質(zhì)上都是基于哈希表,記錄重復(fù)的子樹結(jié)構(gòu)并統(tǒng)計個數(shù),在超過111時進行記錄,不過思路二更巧妙地將冗長的字符串變?yōu)槌?shù)級的標(biāo)識符。

以上就是Java C++ 算法題解leetcode652尋找重復(fù)子樹的詳細內(nèi)容,更多關(guān)于Java C++ 尋找重復(fù)子樹的資料請關(guān)注腳本之家其它相關(guān)文章!

相關(guān)文章

  • 詳解C語言中const關(guān)鍵字的用法

    詳解C語言中const關(guān)鍵字的用法

    這篇文章主要對C語言中const關(guān)鍵字的用法進行了詳細的分析介紹,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2015-08-08
  • C語言動態(tài)內(nèi)存泄露常見問題內(nèi)存分配改進方法詳解

    C語言動態(tài)內(nèi)存泄露常見問題內(nèi)存分配改進方法詳解

    今天遇見了一道有意思的內(nèi)存泄露題目,特地分享給大家,相信屏幕前的你學(xué)習(xí)完一定有所收獲,預(yù)祝讀者學(xué)習(xí)愉快,多多進步早日升職加薪
    2021-10-10
  • 判斷指定的進程或程序是否存在方法小結(jié)(vc等)

    判斷指定的進程或程序是否存在方法小結(jié)(vc等)

    VC判斷進程是否存在?比如我想知道記事本是否運行,要用到哪些函數(shù)等實例,需要的朋友可以參考下
    2013-01-01
  • VS Code 中安裝運行、編寫C語言程序的詳細教程

    VS Code 中安裝運行、編寫C語言程序的詳細教程

    這篇文章主要介紹了VS Code 中安裝運行、編寫C語言程序的詳細教程,本文通過圖文并茂的形式給大家介紹的非常詳細,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2023-03-03
  • C語言數(shù)組快速入門詳細講解

    C語言數(shù)組快速入門詳細講解

    數(shù)組是一組有序的數(shù)據(jù)的集合,數(shù)組中元素類型相同,由數(shù)組名和下標(biāo)唯一地確定,數(shù)組中數(shù)據(jù)不僅數(shù)據(jù)類型相同,而且在計算機內(nèi)存里連續(xù)存放,地址編號最低的存儲單元存放數(shù)組的起始元素,地址編號最高的存儲單元存放數(shù)組的最后一個元素
    2022-05-05
  • 詳解C++中vector的理解以及模擬實現(xiàn)

    詳解C++中vector的理解以及模擬實現(xiàn)

    vector是表示可變大小數(shù)組的序列容器。這篇文章主要為大家詳細介紹了vector的理解以及模擬實現(xiàn),文中的示例代碼講解詳細,感興趣的可以了解一下
    2023-03-03
  • c++ class中成員與分配內(nèi)存的問題詳解

    c++ class中成員與分配內(nèi)存的問題詳解

    很多人都知道C++類是由結(jié)構(gòu)體發(fā)展得來的,所以他們的成員變量(C語言的結(jié)構(gòu)體只有成員變量)的內(nèi)存分配機制是一樣的,下面這篇文章主要給大家介紹了關(guān)于c++ class中成員與分配內(nèi)存問題的相關(guān)資料,需要的朋友可以參考下
    2021-10-10
  • C語言版停車位管理系統(tǒng)

    C語言版停車位管理系統(tǒng)

    這篇文章主要為大家詳細介紹了C語言版停車位管理系統(tǒng),文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-03-03
  • C/C++經(jīng)典算法之約瑟夫問題詳解

    C/C++經(jīng)典算法之約瑟夫問題詳解

    這篇文章主要給大家介紹了關(guān)于C/C++經(jīng)典算法之約瑟夫問題的相關(guān)資料,約瑟夫環(huán)問題是一道經(jīng)典的數(shù)據(jù)結(jié)構(gòu)的題目,本文介紹了解決約瑟夫問題的三種方法,需要的朋友可以參考下
    2021-07-07
  • C++求1到n中1出現(xiàn)的次數(shù)以及數(shù)的二進制表示中1的個數(shù)

    C++求1到n中1出現(xiàn)的次數(shù)以及數(shù)的二進制表示中1的個數(shù)

    這篇文章主要介紹了C++求1到n中1出現(xiàn)的次數(shù)以及數(shù)的二進制表示中1的個數(shù),兩道基礎(chǔ)的算法題目,文中也給出了解題思路,需要的朋友可以參考下
    2016-02-02

最新評論