欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

python 輸入字符串生成所有有效的IP地址(LeetCode 93號題)

 更新時間:2020年10月15日 11:31:13   作者:TechFlow2019  
這篇文章主要介紹了python 生成所有有效的IP地址的方法,幫助大家解答題目,學習python,感興趣的朋友可以了解下

這題的官方難度是Medium,點贊1296,反對505,通過率35.4%。從各項指標來說看起來有些中規(guī)中矩,實際上也的確如此。這道題的解法和立意都有些顯得新意不足,但總體來說題目的質(zhì)量還是可以的,值得一做。

題意

給定一個由數(shù)字組成的字符串,我們希望通過這個字符串得到所有有效ip地址的組合。對于一個有效的ip地址而言,它應該有4個數(shù)字組成,每一個數(shù)字的范圍在0到255之間。

一個字符串可能可以轉(zhuǎn)化成多個ip地址,我們需要存儲下來所有可以成立的情況。

樣例

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

題解

這道題的題意蠻新穎的,將字符串和ip地址結(jié)合在了一起,但是題目的內(nèi)核說實話有些老生常談了,都是那種將一個大局面轉(zhuǎn)化成若干個小局面之和的情況。

我們之前做的全排列問題、八皇后問題等等都是這種,拿八皇后問題舉例,看起來是我們要在棋盤上放置皇后。但實際上我們最終想要的結(jié)果是放置好了八個皇后之后的局面,這個局面是由放置了每一個皇后之后的小局面組合在一起構(gòu)成的。所以本質(zhì)上也可以看成是小局面組裝成大局面的問題。

說了這么多,其實只為了說明一點,就是遇到這些大局面拆分小局面的問題,我們可以率先考慮搜索算法。搜索算法除了可以理解成在一個搜索空間或者是一棵搜索樹當中尋找到解之外,也可以理解成可以用來尋找一些小局面的組合,讓它們組合起來可以構(gòu)成我們想要的大局面。

套用到這道題上來,很顯然最后我們想要的大局面是合法的IP地址,而構(gòu)成這個大局面的小局面則是構(gòu)成IP地址的每一個數(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當中剛好存了4個ip
      # 則生成答案
      if cur >= n:
        if len(ips) == 4:
          ret.append('.'.join(ips[:]))
        return
      
      # 遍歷下一個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和回溯的話不會很難。

今天的文章到這里就結(jié)束了,如果喜歡本文的話,請來一波素質(zhì)三連,給我一點支持吧(關注、轉(zhuǎn)發(fā)、點贊)。

以上就是python 輸入字符串生成所有有效的IP地址(LeetCode 93號題)的詳細內(nèi)容,更多關于python 生成IP地址的資料請關注腳本之家其它相關文章!

相關文章

  • python with statement 進行文件操作指南

    python with statement 進行文件操作指南

    在Python中,with關鍵字是一個替你管理實現(xiàn)上下文協(xié)議對象的好東西。例如:file等。在file的結(jié)束,會自動關閉該文件句柄。而這正是本文所需要的
    2014-08-08
  • python 找出list中最大或者最小幾個數(shù)的索引方法

    python 找出list中最大或者最小幾個數(shù)的索引方法

    今天小編就為大家分享一篇python 找出list中最大或者最小幾個數(shù)的索引方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-10-10
  • Python發(fā)送form-data請求及拼接form-data內(nèi)容的方法

    Python發(fā)送form-data請求及拼接form-data內(nèi)容的方法

    這篇文章主要介紹了Python發(fā)送form-data請求及拼接form-data內(nèi)容的方法,文中采用的是requests的方式發(fā)送multipart/form-data請求,需要的朋友可以參考下
    2016-03-03
  • Python中類的定義、繼承及使用對象實例詳解

    Python中類的定義、繼承及使用對象實例詳解

    這篇文章主要介紹了Python中類的定義、繼承及使用對象,較為詳細的分析了Python中類的相關概念與使用技巧,具有一定參考借鑒價值,需要的朋友可以參考下
    2015-04-04
  • Python3生成手寫體數(shù)字方法

    Python3生成手寫體數(shù)字方法

    本篇文章給大家分享習如何Python3生成手寫體數(shù)字方法以及實例代碼分享,有興趣的朋友參考下吧。
    2018-01-01
  • Python編程中運用閉包時所需要注意的一些地方

    Python編程中運用閉包時所需要注意的一些地方

    這篇文章主要介紹了Python編程中運用閉包時所需要注意的一些地方,文章來自國內(nèi)知名的Python開發(fā)者felinx的博客,需要的朋友可以參考下
    2015-05-05
  • Python Numpy中ndarray的常見操作

    Python Numpy中ndarray的常見操作

    這篇文章主要介紹了Python Numpy中ndarray的常見操作,NumPy是Python的一種開源的數(shù)值計算擴展,更多詳細內(nèi)容需要的朋友可以參考一下
    2022-07-07
  • Python協(xié)程asyncio模塊的演變及高級用法

    Python協(xié)程asyncio模塊的演變及高級用法

    網(wǎng)上很多關于Python協(xié)程asyncio模塊的教程都是基于老版Python的, 本文將以對比方式展示新老Python版本下協(xié)程的寫法有什么不同并總結(jié)了asyncio的一些高級用法, 包括如何獲取協(xié)程任務執(zhí)行結(jié)果,gather和wait方法的區(qū)別以及如何給任務添加回調(diào)函數(shù)。
    2021-05-05
  • Python實現(xiàn)線性擬合及繪圖的示例代碼

    Python實現(xiàn)線性擬合及繪圖的示例代碼

    在數(shù)據(jù)處理和繪圖中,我們通常會遇到直線或曲線的擬合問題,本文主要介紹了Python實現(xiàn)線性擬合及繪圖的示例代碼,具有一定的參考價值,感興趣的可以了解一下
    2024-04-04
  • Python實現(xiàn)簡易的限流器介紹

    Python實現(xiàn)簡易的限流器介紹

    大家好,本篇文章主要講的是Python實現(xiàn)簡易的限流器介紹,感興趣的同學趕快來看一看吧,對你有幫助的話記得收藏一下
    2022-01-01

最新評論