11.9 leetcode打卡

94.二叉樹的中序遍歷

原題鏈接：94. 二叉樹的中序遍歷

題目描述

給定一個二叉樹的根節點 root ，返回 它的 中序 遍歷 。

輸入：root = [1,null,2,3] 輸出：[1,3,2]

代碼實現

class Solution {vector<int> ans; public:vector<int> inorderTraversal(TreeNode* root) {if(!root){ return ans; }inorderTraversal(root->left);ans.push_back(root->val);inorderTraversal(root->right);return ans;} };

102.二叉樹的層序遍歷

原題鏈接：102. 二叉樹的層序遍歷

題目描述

給你二叉樹的根節點 root ，返回其節點值的 層序遍歷 。 （即逐層地，從左到右訪問所有節點）。

輸入：root = [3,9,20,null,null,15,7] 輸出：[[3],[9,20],[15,7]]

代碼實現

class Solution { public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> ans;if(!root){ return ans; }queue<TreeNode *> queue;queue.push(root);while(!queue.empty()){vector<int> tmp;int len = queue.size();for(int i = 0; i < len; ++ i){ //記錄每一層有多少個節點 每一次隊列中只存一層的節點TreeNode *cur = queue.front(); queue.pop();tmp.push_back(cur->val); //依次將該層的節點添加至集合中if(cur->left){ queue.push(cur->left); }if(cur->right){ queue.push(cur->right); }}ans.push_back(tmp); //將每層的結果添加至結果集中}return ans;} };

76.最小覆蓋子串

原題鏈接：76. 最小覆蓋子串

題目描述

給你一個字符串 s 、一個字符串 t 。返回 s 中涵蓋 t 所有字符的最小子串。如果 s 中不存在涵蓋 t 所有字符的子串，則返回空字符串 "" 。

輸入：s = "ADOBECODEBANC", t = "ABC" 輸出："BANC"

解題思路

哈希表+滑動窗口

1.記錄字符串t中每個字符的詞頻(哈希表|以便于后續的判斷)

2.以左指針或右指針為判斷條件 left < sLen - tLen || right < sLen

3.右指針所指字符在字符串s所對應表中的詞頻+1 判斷右指針所指字符在s中的個數是否小于等于在t中的個數 并記錄個數count

4.判斷左指針所指字符在s中的個數是否多余在t中的個數

若多余則一直讓左指針右移（因為所求為最小子串故而讓每個字符的在s中和在t中的對應數量盡可能的相差較小

5.判斷已滿足條件的字符個數count是否與t的長度相等 若相等則比較記錄每次包含該count的窗口(從left開始到right結束的子串)

代碼實現

class Solution { public:string minWindow(string s, string t) {string res;int sLen = s.length(), tLen = t.length();if(sLen < tLen){ return res; }unordered_map<char, int> tmap;unordered_map<char, int> smap;for(char& ch : t){ tmap[ch] ++; }int left = 0, count = 0;for(int right = 0; right < sLen; ++ right){smap[s[right]] ++;if(smap[s[right]] <= tmap[s[right]]) count ++;while(smap[s[left]] > tmap[s[left]]){smap[s[left]]--;left ++;}if(count == tLen){if(res.empty()){res = s.substr(left, right - left + 1);}else if(res.length() > right - left + 1){res = s.substr(left, right - left + 1);}}}return res;} };

總結

以上是生活随笔為你收集整理的11.9 leetcode打卡的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。