leetcode 6.15-6.21

2020-06-20

771 宝石与石头
513 找树左下角的值

10. 正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1:

输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/regular-expression-matching
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

看了题解应该用动态规划，直接用python的正则表达做了，这题算附加吧，当学习re用法。

AC代码：

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        ret = re.match(p, s)
        if ret != None:
            return (ret.span() == (0, len(s)))
        else:
            return False
          
  # 从评论里看到的更简洁的写法
  return True if re.compile(p).fullmatch(s) else False
	return re.match(p + '$', s)

菜鸟：https://www.runoob.com/python/python-reg-expressions.html

CSDN：https://blog.csdn.net/chenmozhe22/article/details/80601971

re.match返回的是从头开始匹配的结果，结果可以用group提取，span返回一个标记匹配结果的二元组。

771. 宝石与石头

给定字符串J 代表石头中宝石的类型，和字符串 S代表你拥有的石头。 S 中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。

J 中的字母不重复，J 和 S中的所有字符都是字母。字母区分大小写，因此”a”和”A”是不同类型的石头。

示例 1:

输入: J = “aA”, S = “aAAbbbb”
输出: 3
示例 2:

输入: J = “z”, S = “ZZ”
输出: 0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jewels-and-stones
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

AC代码：

方法一：暴力，双层循环

方法二：哈希

class Solution(object):
    def numJewelsInStones(self, J, S):
        # ret = 0
        # for ch in S:
        #     if ch in J:
        #         ret += 1
        # return ret
        dic = {}
        for rock in S:
            dic[rock] = dic.get(rock, 0) + 1
        ret = 0
        for rock in J:
            ret += dic.get(rock, 0)
        return ret

513. 找树左下角的值

给定一个二叉树，在树的最后一行找到最左边的值。

示例 1:

输入:

    2
   / \
  1   3

输出:
1

示例 2:

输入:

输出:
7

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-bottom-left-tree-value
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

参考分层打印二叉树，层序遍历，返回最后一层的第一个元素。

AC代码：

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        std::queue<TreeNode*> q;
        q.push(root);
        std::vector<int> ret;
        while(!q.empty()) {
            int cur_size = q.size();
            ret.clear();
            for(int i = 0; i < cur_size; i++) {
                auto p = q.front();
                q.pop();
                ret.push_back(p->val);
                if(p->left)  q.push(p->left);
                if(p->right) q.push(p->right);
            }
        }
        return ret[0];
    }
};