国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[Leetcode] Restore IP Address 修復(fù)IP地址

VioletJack / 696人閱讀

摘要：四分法復(fù)雜度時(shí)間空間思路用三個(gè)點(diǎn)將字符串分成四段，驗(yàn)證每一段是否是有效的。注意使用時(shí)要確保所得到數(shù)不會(huì)超界。代碼第一個(gè)分割點(diǎn)第二個(gè)分割點(diǎn)第三個(gè)分割點(diǎn)

Restore IP Address 
Given a string containing only digits, restore it by returning all possible valid IP address combinations.


For example: Given "25525511135",


return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
四分法 復(fù)雜度

時(shí)間 O(N^2) 空間 O(1)

思路

用三個(gè)點(diǎn)將字符串分成四段，驗(yàn)證每一段是否是有效的。我們只要控制這三個(gè)分割點(diǎn)就行了，注意約束條件有兩個(gè)，一個(gè)是一段字符串不超過3個(gè)字母，另一個(gè)是控制好每段字符串最遠(yuǎn)結(jié)束的位置，比如第一個(gè)字符串最多延伸到倒數(shù)第4個(gè)字母。

注意

使用Integer.valueOf()時(shí)要確保所得到數(shù)不會(huì)超界。

代碼 
public class Solution {
    public List restoreIpAddresses(String s) {
        List res = new LinkedList();
        int len = s.length();
        // 第一個(gè)分割點(diǎn)
        for(int i = 1; i < 4 && i < len - 2; i++){
            // 第二個(gè)分割點(diǎn)
            for(int j = i + 1; j < i + 4 && j < len - 1; j++){
                // 第三個(gè)分割點(diǎn)
                for(int k = j + 1; k < j + 4 && k < len ; k++){
                    String s1 = s.substring(0,i), s2 = s.substring(i, j), s3 = s.substring(j, k), s4 = s.substring(k, s.length());
                    if(isValid(s1)&&isValid(s2)&&isValid(s3)&&isValid(s4)) res.add(s1+"."+s2+"."+s3+"."+s4);
                }
            }
        }
        return res;
    }
    
    private boolean isValid(String sub){
        return sub.length()<=3 && ((sub.charAt(0) != "0" && Integer.valueOf(sub) <=255) || sub.equals("0"));
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/64483.html

相關(guān)文章

  • LeetCode: 93. Restore IP Addresses

    摘要：以剩下的字符串，當(dāng)前字符串，剩余單元數(shù)傳入下一次遞歸。結(jié)束條件字符串長度為，并且剩余單元數(shù)為 Given a string containing only digits, restore it by returning all possible valid IP address combinations. For example:Given 25525511135, return [2...

    Shisui 評(píng)論0 收藏0

  • leetcode93. Restore IP Addresses

    摘要：題目要求返回字符串能夠組成的所有地址。思路與代碼地址由位二進(jìn)制數(shù)字構(gòu)成，一共分為個(gè)區(qū)間，每個(gè)區(qū)間位。那么我們只要?jiǎng)澐殖鲞@四個(gè)區(qū)間，然后判斷這四個(gè)區(qū)間的值是否符合標(biāo)準(zhǔn)即可。 題目要求 Given a string containing only digits, restore it by returning all possible valid IP address combinatio...

    chenjiang3 評(píng)論0 收藏0

  • [LeetCode] 93. Restore IP Addresses

    Problem Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example: Input: 25525511135Output: [255.255.11.135, 255.255.111.35] Solution class So...

    xingqiba 評(píng)論0 收藏0

  • leetcode-93-Restore IP Addresses

    摘要：題目描述題目理解將一段字符廣度搜索截取，分別有種組合形式，添加限制條件，過濾掉不適合的組合元素。長度，大小，首字母應(yīng)用如果進(jìn)行字符串的子元素組合窮舉，可以應(yīng)用。所有的循環(huán)，利用到前一個(gè)狀態(tài)，都可以理解為動(dòng)態(tài)規(guī)劃的一種分支 題目描述：Given a string containing only digits, restore it by returning all possible va...

    wmui 評(píng)論0 收藏0

  • [LintCode/LeetCode] Restore IP Addresses

    摘要：第一個(gè)分割點(diǎn)第二個(gè)分割點(diǎn)第三個(gè)分割點(diǎn) Problem Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example Given 25525511135, return [ 255.255.11.135, 255....

    bingo 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<