11.9 leetcode打卡

11.9 leetcode打卡

94.二叉树的中序遍历

原题链接：94. 二叉树的中序遍历

题目描述

给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

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

代码实现

class Solution {
    vector ans;
public:
    vector inorderTraversal(TreeNode* root) {
        if(!root){ return ans; }
        inorderTraversal(root->left);
        ans.push_back(root->val);
        inorderTraversal(root->right);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11

102.二叉树的层序遍历

原题链接：102. 二叉树的层序遍历

题目描述

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
1
2

代码实现

class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        vector> ans;
        if(!root){ return ans; }
        queue queue;
        queue.push(root);
        while(!queue.empty()){
            vector 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

76.最小覆盖子串

原题链接：76. 最小覆盖子串

题目描述

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
1
2

解题思路

哈希表+滑动窗口

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 tmap;
        unordered_map 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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31