LeetCode DAY 6 (9-10)

日常更新冒泡…

9. 回文数（简单）

题目描述

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

示例1:

输入: 121
输出: true

示例2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例3:

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。

代码

解法1：转为字符串处理

利用python的切片功能一行代码即可解决。

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        return str(x) == str(x)[::-1]

解法2：不利用字符串

翻转整个数值，官方题解有说反转一半，以防溢出，但是溢出不就不是回文数了，因此我觉得不需要考虑溢出。

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if x < 0:
            return False
        ans = 0
        pri = x
        while x != 0:
            ans = x%10 + ans*10
            x //= 10
        if ans == pri:
            return True
        else:
            return False

---

10. 正则表达式匹配（困难）

题目描述

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

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖整个字符串s的，而不是部分字符串。

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

示例1:

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

示例2:

输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。

示例3:

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

代码

解法1：暴力递归

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        if len(p) == 0:
            return not s
        # 出现'.'的情况
        first = bool(s) and p[0] in (s[0], '.')
        # 出现'*'的情况
        if len(p)>1 and p[1]=='*':
            return self.isMatch(s, p[2:]) or (first and self.isMatch(s[1:], p))
        else:
            return first and self.isMatch(s[1:], p[1:])

• 当出现'.'的时候，因为它匹配任意字符，因此只要额外判断p[i]是否等于'.'即可；
• 对于出现'*'时，因为它匹配0个到任意个星号前面的字符，所以我们需要对它进行不同的处理，虽然他能匹配0～n个字符，但是对于递归而言，只有两种情况：0个和1个。

解法2: 递归优化

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        # 定义一个字典作为备忘录
        memo = dict()
        def dp(i, j):
        	# 避免重复计算
            if (i,j) in memo: return memo[(i,j)] 
            if j==len(p): return i==len(s)
            first = i<len(s) and p[j] in (s[i], '.')
            if j<len(p)-1 and p[j+1] == '*':
                ans = dp(i,j+2) or first and dp(i+1,j)
            else:
                ans = first and dp(i+1,j+1)
            memo[(i,j)] = ans
            return ans
        return dp(0,0) 

使用两个变量i,j记录当前匹配到的位置，从而避免使用子字符串切片，并且将i,j存入备忘录，避免重复计算。