python 輸入字符串生成所有有效的IP地址(LeetCode 93號題)
這題的官方難度是Medium,點(diǎn)贊1296,反對505,通過率35.4%。從各項(xiàng)指標(biāo)來說看起來有些中規(guī)中矩,實(shí)際上也的確如此。這道題的解法和立意都有些顯得新意不足,但總體來說題目的質(zhì)量還是可以的,值得一做。
題意
給定一個(gè)由數(shù)字組成的字符串,我們希望通過這個(gè)字符串得到所有有效ip地址的組合。對于一個(gè)有效的ip地址而言,它應(yīng)該有4個(gè)數(shù)字組成,每一個(gè)數(shù)字的范圍在0到255之間。
一個(gè)字符串可能可以轉(zhuǎn)化成多個(gè)ip地址,我們需要存儲(chǔ)下來所有可以成立的情況。
樣例
Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
題解
這道題的題意蠻新穎的,將字符串和ip地址結(jié)合在了一起,但是題目的內(nèi)核說實(shí)話有些老生常談了,都是那種將一個(gè)大局面轉(zhuǎn)化成若干個(gè)小局面之和的情況。
我們之前做的全排列問題、八皇后問題等等都是這種,拿八皇后問題舉例,看起來是我們要在棋盤上放置皇后。但實(shí)際上我們最終想要的結(jié)果是放置好了八個(gè)皇后之后的局面,這個(gè)局面是由放置了每一個(gè)皇后之后的小局面組合在一起構(gòu)成的。所以本質(zhì)上也可以看成是小局面組裝成大局面的問題。
說了這么多,其實(shí)只為了說明一點(diǎn),就是遇到這些大局面拆分小局面的問題,我們可以率先考慮搜索算法。搜索算法除了可以理解成在一個(gè)搜索空間或者是一棵搜索樹當(dāng)中尋找到解之外,也可以理解成可以用來尋找一些小局面的組合,讓它們組合起來可以構(gòu)成我們想要的大局面。
套用到這道題上來,很顯然最后我們想要的大局面是合法的IP地址,而構(gòu)成這個(gè)大局面的小局面則是構(gòu)成IP地址的每一個(gè)數(shù)字。
這些都搞明白了之后,代碼就很好寫了:
class Solution: def restoreIpAddresses(self, s: str) -> List[str]: n = len(s) if n < 4 or n > 12: return [] ret = [] def dfs(cur, ips): # 如果遞歸結(jié)束,并且ips當(dāng)中剛好存了4個(gè)ip # 則生成答案 if cur >= n: if len(ips) == 4: ret.append('.'.join(ips[:])) return # 遍歷下一個(gè)ip是幾位 for i in range(cur, min(cur+3, n)): # 如果超過1位但是第一位是0,那么非法 if s[cur] == '0' and i > cur: return # ip必須小于等于255 num = int(s[cur: i+1]) if num > 255: return # 回溯 ips.append(s[cur: i+1]) dfs(i+1, ips) ips.pop() dfs(0, []) return ret
總結(jié)
有些新意但是思路中規(guī)中矩的搜索問題,熟悉dfs和回溯的話不會(huì)很難。
今天的文章到這里就結(jié)束了,如果喜歡本文的話,請來一波素質(zhì)三連,給我一點(diǎn)支持吧(關(guān)注、轉(zhuǎn)發(fā)、點(diǎn)贊)。
以上就是python 輸入字符串生成所有有效的IP地址(LeetCode 93號題)的詳細(xì)內(nèi)容,更多關(guān)于python 生成IP地址的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
python with statement 進(jìn)行文件操作指南
在Python中,with關(guān)鍵字是一個(gè)替你管理實(shí)現(xiàn)上下文協(xié)議對象的好東西。例如:file等。在file的結(jié)束,會(huì)自動(dòng)關(guān)閉該文件句柄。而這正是本文所需要的2014-08-08python 找出list中最大或者最小幾個(gè)數(shù)的索引方法
今天小編就為大家分享一篇python 找出list中最大或者最小幾個(gè)數(shù)的索引方法,具有很好的參考價(jià)值,希望對大家有所幫助。一起跟隨小編過來看看吧2018-10-10Python發(fā)送form-data請求及拼接form-data內(nèi)容的方法
這篇文章主要介紹了Python發(fā)送form-data請求及拼接form-data內(nèi)容的方法,文中采用的是requests的方式發(fā)送multipart/form-data請求,需要的朋友可以參考下2016-03-03Python編程中運(yùn)用閉包時(shí)所需要注意的一些地方
這篇文章主要介紹了Python編程中運(yùn)用閉包時(shí)所需要注意的一些地方,文章來自國內(nèi)知名的Python開發(fā)者felinx的博客,需要的朋友可以參考下2015-05-05Python協(xié)程asyncio模塊的演變及高級用法
網(wǎng)上很多關(guān)于Python協(xié)程asyncio模塊的教程都是基于老版Python的, 本文將以對比方式展示新老Python版本下協(xié)程的寫法有什么不同并總結(jié)了asyncio的一些高級用法, 包括如何獲取協(xié)程任務(wù)執(zhí)行結(jié)果,gather和wait方法的區(qū)別以及如何給任務(wù)添加回調(diào)函數(shù)。2021-05-05Python實(shí)現(xiàn)線性擬合及繪圖的示例代碼
在數(shù)據(jù)處理和繪圖中,我們通常會(huì)遇到直線或曲線的擬合問題,本文主要介紹了Python實(shí)現(xiàn)線性擬合及繪圖的示例代碼,具有一定的參考價(jià)值,感興趣的可以了解一下2024-04-04