學習卧談會之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.作者的話
最後，您如果覺得本公眾號對您有幫助，歡迎您多多支持，轉發，謝謝！
