学习卧谈会之LeetCode(8)
- 2019 年 10 月 6 日
- 笔记
卧谈会之LeetCode(8)
0.说在前面
1.正则表达式匹配
2.思路
3.实现
4.参考资料
5.作者的话
0.说在前面
点击公众号右下角合作转载->联系我，即可加入我的个人微信，共同探讨交流，以及入交流群(记得备注入群)！
最近公众号增加了一些读者，所以在正式开始本文之前，想好好的唠叨一下。
关注过一段时间的读者知道，在这里写的文章，是个人学习python的一些历程，包括python爬虫，机器学习，LeetCode等。个人比较感兴趣的是知识图谱，正致力于将机器学习运用到KG当中。在这里我们可以共同分享，共同交流，共同学习！
【刷题】
公众号建立初衷来源于老表学弟，在这里也非常感谢各位大佬给予的指导，之前跟老表学弟一起搞了个LeetCode交流小分队，每次法LeetCode的文章顺序是他先出，然后我再来补充，正是这一步步的交流，也才使得我的LeetCode更新到现在的第8篇。
借用老表的一句话：我们为面试而生，期待各位的加入！
【爬虫】
我今年上半年毕业，做的毕设是有关知识图谱的，说起这个知识图谱，可能在座的各位有可能不太清楚，这里稍微解释一下，所谓知识图谱可以理解为知识卡片，能够关联实体之间的联系，那么在对数据挖掘方面及可视化方面非常有助！如能将机器学习与知识图谱相结合，也是一个不错的实现方法，比如利用机器学习或者数学模型去推测不同实体之间的联系，那么对于非常庞大的实体来说，可以提升工作效率！
从知识图谱中，学起了Python，在2017年学过python基础，于是2018年毕设主要是重拾python基础，进一步进阶。
特别是一些map,set这些高级语法，非常有用，也建议各位去学习一下。除此之外，大家听过一个名词，叫做关系型数据库，那么我问各位：什么是非关系型数据库。
这里就引申了一个概念，就是NoSql，NoSQL(NoSQL = Not Only SQL )，意即"不仅仅是SQL"，在有关KG(知识图谱)的研究当中，用的是Neo4J图数据库，那么又如何可视化出来呢，数据又从哪来的，与我们的题目爬虫又有什么关系呢？
爬虫，可以说是一种工具，在这里，我主要是从6月份以后才开始学Python爬虫相关，之前都是零碎的杂学，从抓取学校的成绩，并发送等Demo入手，到现在多个网站爬虫及可视化，这一阶段，最重要的，我觉得有两点来分享一下：
- 第一：逻辑思路
- 第二：代码量
逻辑思路，决定了你在爬虫方面，如何高效的去对特定的问题求解，比如网站的反爬虫。
代码量，决定了你coding的速度，也决定了你实现思路的逻辑性。
最后，爬虫这一块，也非常感谢有痴海，老表等各位大佬的资源与分享！
【机器学习】
首先对自己的机器学习定个位，我觉得我现在是初级菜鸟。
在前面就说想将KG与ML结合起来，两个难点，必须逐一攻破！
从最先考研期间，吴恩达出来的机器学习课程，看了5-10集，因为英文不好而放弃，到现在重拾！
从机器学习到机器学习基石，是理论上的一步提升，同时配上李航统计学习方法，简直是把利器！
从机器学习实战到打比赛，是理论的实践化，从最先可视化用的Pyecharts到现在用的Seaborn，再到学会如何做特征提取，如何做数据预处理，再到最后的模型融合等
最后，感谢有吴恩达，刘老师等各位的大佬的分享以及各位公众号读者的支持与反馈！
【知识图谱】
从5月份学的Python Web到暑假的node.js，再到d3.js，这是前端知识能力的提升，同时也是对KG的一步实战性操作。
从RDF到Neo4J，这是数据处理的一步提升。
从机器学习预测到知识图谱，这是数据扩展的一步提升。
最后，感谢OpenKG等组织，以及各位读者的支持与反馈！
【Last But Not Least】
以上是我想对各位说的，也是我想跟各位交流的一些心得体会等，也希望各位支持与反馈。
随后，本文将带大家一起刷一道LeetCode上难度较高的一道题，一起来实战吧！
1.正则表达式匹配
【问题】
给定一个字符串 (s) 和一个字符模式 (p)。实现支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符。 '*' 匹配零个或多个前面的元素。
匹配应该覆盖整个字符串 (s) ，而不是部分字符串。
说明:
s可能为空，且只包含从a-z的小写字母。p可能为空，且只包含从a-z的小写字母，以及字符.和*。
示例 1:
输入: s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:
输入: s = "aa" p = "a*" 输出: true 解释: '*' 代表可匹配零个或多个前面的元素, 即可以匹配 'a' 。因此, 重复 'a' 一次, 字符串可变为 "aa"。
2.思路
本题难度系数非常高，这里采用DP思路，也就是动态规划思路。
下面放出之前写的两篇有关DP思路的文章，随后写一篇总结DP的！
我们一起先来回顾一下DP算法的基本思想，在每次问题求解过程中，可以将问题分解成很多个子问题，对于子问题，如果前面已经实现了，那么在当前情况下，就不需要重复已经操作的步骤，直接调用！
对于这道题的算法过程如下：
在模式串p中，当遇到.时，则取矩阵的左上方数据；
当遇到*时，又分为两种情况，第一种是p中前一位不等于s中当前字符，则取矩阵上2位，第二种是p中前一位等于s中当前字符，则取上2位或上1位，或左1位；
其他情况，若p与s的当前字符相等，则取左上。
对于上面这几句话，听起来跟天书一样，下面通过手稿来一起分析！
首先我们建立一个二维矩阵M，大家注意到下面图中用虚线框起来的是矩阵M，内部则是矩阵内部，对于矩阵的左上角大家注意一下，这里对应的行与列，我画了两个圆圈，其余的在图中有描述！
矩阵初始化图
我们先来处理一下矩阵的特殊情况，当第0行时，也就是s不一定为空串，而p为空串，那么此时，只有一种情况匹配，那就是当两者全为空串，在这种情况下，两者匹配成功，设为True，用T来代表！其余为False，用F代表！
还有另外一个特殊列那就是第0列，这里就比较特殊了，左上角(s与p均为0不管)，上述已经设为T，我们来分析一下其余的特殊情况，此时的s为空串，而p为空串，则为T，当p为a*时候，此时*若匹配0次，那么此时便会匹配成功，也就是将a*删除掉，便会回归到前面处理的左上角情况，这里就用到了DP最核心的思想，这里明白了，那么本题基本上没多大问题了！
上述两者特殊情况处理后，那么我们来处理一下内层矩阵，对于内层矩阵的处理办法，则是上面说的算法过程！
上2位，上1位，左1位，则是矩阵中，当前位置是否设置为T or F，根据其p或s移动位置，回溯到前面已经计算好的值，根据旧值，来计算新值！
这里特别把上述算法过程中，最复杂的解释一下：
当p此时为*时，该怎么操作？
举个例子：
下面分别是p中*匹配0次，匹配1次，匹配多次成功的情况！
s p ab ab.* abc abc* abcc abc*
对于第一种情况，匹配0次，我们需要做的就是只需要将.*删除了，将p字符向前推2位，只要判断操作后的p字符与s当前字符是否相等，若相等，则模式匹配成功，否则不成功！也就是上述算法中的向上2位。
对于第二种情况，则是只需要将*删除即可！那么只需要将p字符向前推1位，再去判断操作后的p字符与s当前字符是否相等，若相等，则模式匹配成功，否则不成功！也就是上述算法中的向上1位。
对于第三种情况，则是对s做操作，我们先删除一个c，会发现此时s=abc,p=abc*，发现了什么！！！是不是又回到第二种情况，对没错，这就是DP思想！
矩阵完整图
3.实现
python实现及解释如下代码：
class Solution: def isMatch(self, s, p): """ :type s: str :type p: str :rtype: bool """ # 定义矩阵的宽与高 M_W = len(s)+1 M_H = len(p)+1 # 矩阵第0行设置数据 # 注意矩阵的index为p或s加1 # 当p字符串为空(这种情况下，矩阵高为1) if M_H == 1: # 当s字符串为空,则匹配成功 if M_W==1: return True # 否则匹配失败 else: return False Matrix = [[False]*M_W for i in range(M_H)] Matrix[0][0]=True # 矩阵第0列设置数据 # 由于矩阵的左上角为(0,0),相当于在每一行，每一列，多增了一位index,与p,s对比要减一 for i in range(M_H-1): if p[i]=='*': # 矩阵的行与列相比于p,s又要加1，当碰到*，则回溯p退回2位 Matrix[i+1][0]=Matrix[i-1][0] for i in range(1,M_H): for j in range(1,M_W): if p[i-1]=='.': # 碰到. 则根据左上角 Matrix[i][j]=Matrix[i-1][j-1] elif p[i-1]=='*': if p[i-2]!=s[j-1] and p[i-2]!='.': # 取上两位值 Matrix[i][j]=Matrix[i-2][j] else: Matrix[i][j]=Matrix[i-2][j] or Matrix[i-1][j] or Matrix[i][j-1] else: Matrix[i][j]=Matrix[i-1][j-1] and p[i-1]==s[j-1] return Matrix[-1][-1]
4.参考资料
https://blog.csdn.net/hk2291976/article/details/51165010
5.作者的话
最后，您如果觉得本公众号对您有帮助，欢迎您多多支持，转发，谢谢！
