Day22 正则表达式匹配 + 二进制中1的个数 + 二叉搜索树
2021-07-05 本文已影响0人
吃掉夏天的怪物
TODO:
- 重做. 正则表达式匹配
- 注意 二进制中1的个数 方法一
- 重做 二叉搜索树的最近公共祖先 和 二叉树的最近公共祖先
剑指 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.pngclass 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;
}
};