Day22 正则表达式匹配 + 二进制中1的个数 + 二叉搜索树

TODO:

1. 重做. 正则表达式匹配
2. 注意 二进制中1的个数 方法一
3. 重做 二叉搜索树的最近公共祖先 和 二叉树的最近公共祖先

剑指 Offer 19. 正则表达式匹配(困难)

完全不会做，没想到这道题也可以dp。看题解也没怎么看懂。下次还得做

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size() + 1, n = p.size() + 1;
        vector<vector<bool>> dp(m, vector<bool>(n, false));
        dp[0][0] = true;
        for(int j = 2; j < n; j += 2)
            dp[0][j] = dp[0][j - 2] && p[j - 1] == '*';
        for(int i = 1; i < m; i++) {
            for(int j = 1; j < n; j++) {
                dp[i][j] = p[j - 1] == '*' ?
                    dp[i][j - 2] || dp[i - 1][j] && (s[i - 1] == p[j - 2] || p[j - 2] == '.'):
                    dp[i - 1][j - 1] && (p[j - 1] == '.' || s[i - 1] == p[j - 1]);
            }
        }
        return dp[m - 1][n - 1];
    }
};

剑指 Offer 15. 二进制中1的个数(简单)

方法一 跟着题解学的

题解

image.png

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        while(n){
            res += 1;
            n = n&(n-1);
        }
        return res;
    }
};

方法二 不断判断最后一位

class Solution {
public:
    int hammingWeight(uint32_t n) {
        long long cnt = 0;
        while(n) {
            if(n % 2 == 1) 
                cnt ++;
            n >>= 1;
        }
        return cnt;
    }
};

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先(简单)

之前有道二叉树的最近公共祖先，需要考虑的东西就要稍微多一些。这里是二叉搜索树，就可以利用其左孩子的值 < 根<右的特性。
题解

方法一 递归

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr) return nullptr;
        if(root->val < p->val && root->val < q->val){
            return lowestCommonAncestor(root->right,p,q);
        }else if(root->val > p->val && root->val > q->val){
            return lowestCommonAncestor(root->left,p,q);
        }else{
            return root;
        }
        return nullptr;
        
    }
};

方法二 迭代

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr) return nullptr;
        while(root){
            if(root->val < p->val && root->val < q->val){
                root = root->right;
            }else if(root->val > p->val && root->val > q->val){
                root = root->left;
            }else{
                break;
            }
        }
       
        return root;
        
    }
};