wy的leetcode刷题记录_Day37

wy的leetcode刷题记录_Day37

声明

本文章的所有题目信息都来源于leetcode
如有侵权请联系我删掉

1684. 统计一致字符串的数目

今天的每日一题是：1684. 统计一致字符串的数目

题目介绍

给你一个由不同字符组成的字符串 allowed 和一个字符串数组 words 。如果一个字符串的每一个字符都在 allowed 中，就称这个字符串是 一致字符串 。

请你返回 words 数组中 一致字符串 的数目。

示例 1：
输入：allowed = “ab”, words = [“ad”,“bd”,“aaab”,“baa”,“badab”]
输出：2
解释：字符串 “aaab” 和 “baa” 都是一致字符串，因为它们只包含字符 ‘a’ 和 ‘b’ 。

示例 2：
输入：allowed = “abc”, words = [“a”,“b”,“c”,“ab”,“ac”,“bc”,“abc”]
输出：7
解释：所有字符串都是一致的。 。

思路

简单的模拟题。
方法一：使用Set，将allowed中的字符加入Set，这个Set我们称之为允许集，然后遍历words中的每一个word，然后判断每个word中的每个字符是否存在于允许集中，如果有一个字符不存在那么这个word就不符合。
方法二：位运算：因为知道字母只有26个，所以我们使用一个32位的整数mask来代表允许集，其中0-25位分别表示a到z，哪一位为1说明允许集中存在那一位。然后使用另一个32位整数mask1来表示words中每一个word的字母出现情况，如果如果这俩个允许集的并集比原来的mask大的话就说明mask1中存在了不存在于允许集mask中的字母。

代码

class Solution {
public:
    int countConsistentStrings(string allowed, vector<string>& words) {
        int ans=0;
        int n=allowed.size();
        int m=words.size();

        unordered_set<char> Set;

        for(char temp:allowed)
        {
            Set.insert(temp);
        }

        for(int i=0;i<m;i++)
        {
            int word_size=words[i].size();
            bool flag=true;
            for(int j=0;j<word_size;j++)
            {
                if(Set.count(words[i][j])==0)
                {    
                    flag=false;
                    break;
                }  
            }
            if(flag)
                ans++;
        }
        return ans;
    }
};
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
32

class Solution {
public:
    int countConsistentStrings(string allowed, vector<string>& words) {
        int mask=0;
        int ans=0;
        for(char c :allowed)
            mask|=1<<(c-'a');
        
        for(auto word:words)
        {
            int mask1=0;
            for(char c:word)
            {
                mask1|=1<<(c-'a');
            }
            if((mask|mask1)==mask)
                ans++;
        }
        return ans;
 
 
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

收获

捋顺思路，随便做题！会用STL,简单百倍。位运算，YYDS！

101. 对称二叉树

101. 对称二叉树

题目介绍

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

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

示例 2：

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

思路

读完题意，认为这还是一道遍历题，只需要判断根节点的左子树和右子树是否镜像对称，我们对左子树采用后序遍历左右中的顺序，然后对右子树采用不一样的“后序遍历”右左中的顺序，然后判断遍历时是否相等即可，可以使用递归也可以递推。递推的话使用队列或者栈都可以。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root==nullptr)
            return true;
        return compare(root->left,root->right);
    }

    bool compare(TreeNode* left,TreeNode* right)
    {
        if(left==nullptr&&right==nullptr)
            return true;
        else if(!left&&right)
            return false;
        else if(left&&!right)
            return false;
        else if(left->val!=right->val)
            return false;
        
        bool outside=compare(left->left,right->right);
        bool inside=compare(left->right,right->left);
        bool flag=outside&inside;
        return flag;

    }
};
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
32
33
34
35
36
37

class Solution {
public:
 bool isSymmetric(TreeNode* root) {
    if (root == NULL) return true;
    queue<TreeNode*> que;
    que.push(root->left); // 将左⼦树头结点加⼊队列
    que.push(root->right); // 将右⼦树头结点加⼊队列
    while (!que.empty()) { // 接下来就要判断这这两个树是否相互翻转
        TreeNode* leftNode = que.front(); que.pop();
        TreeNode* rightNode = que.front(); que.pop();
        if (!leftNode && !rightNode) { // 左节点为空、右节点为空，此时说明是对称的
            continue;
        }
        // 左右⼀个节点不为空，或者都不为空但数值不相同，返回false
        if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
            return false;
        }
        que.push(leftNode->left); // 加⼊左节点左孩⼦
        que.push(rightNode->right); // 加⼊右节点右孩⼦
        que.push(leftNode->right); // 加⼊左节点右孩⼦
        que.push(rightNode->left); // 加⼊右节点左孩⼦
    }
    return true;
    }
};
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

只需要将队列改成栈就可以了

class Solution {
public:
 bool isSymmetric(TreeNode* root) {
    if (root == NULL) return true;
    stack<TreeNode*> st; // 这⾥改成了栈
    st.push(root->left);
    st.push(root->right);
    while (!st.empty()) {
        TreeNode* leftNode = st.top(); st.pop();
        TreeNode* rightNode = st.top(); st.pop();
        if (!leftNode && !rightNode) 
        {
            continue;
        }
        if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) 
        {
            return false;
        }
        st.push(leftNode->left);
        st.push(rightNode->right);
        st.push(leftNode->right);
        st.push(rightNode->left);
    }
    return true;
    }
};
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

收获

巩固了二叉树的遍历方式