[Leetcode][第93题][JAVA][复原IP地址][剪枝][回溯]

雨点打透心脏的1/2处 2022-11-26 07:42 159阅读 0赞

#### 【问题描述】\[中等\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

###### 1. 递归 回溯剪枝 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]

**复杂度**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]

class Solution { 
        static final int SEG_COUNT = 4;
        List<String> ans = new ArrayList<String>();
        int[] segments = new int[SEG_COUNT];
    
        public List<String> restoreIpAddresses(String s) { 
            segments = new int[SEG_COUNT];
            dfs(s, 0, 0);
            return ans;
        }
    
        public void dfs(String s, int segId, int segStart) { 
            // 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
            if (segId == SEG_COUNT) { 
                if (segStart == s.length()) { 
                    StringBuffer ipAddr = new StringBuffer();
                    for (int i = 0; i < SEG_COUNT; ++i) { 
                        ipAddr.append(segments[i]);
                        if (i != SEG_COUNT - 1) { 
                            ipAddr.append('.');
                        }
                    }
                    ans.add(ipAddr.toString());
                }
                return;
            }
    
            // 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯 剪枝 
            if (segStart == s.length()) { 
                return;
            }
    
            // 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0 条件 
            if (s.charAt(segStart) == '0') { 
                segments[segId] = 0;
                dfs(s, segId + 1, segStart + 1);
            }
    
            // 一般情况，枚举每一种可能性并递归 
            int addr = 0;
            for (int segEnd = segStart; segEnd < s.length(); ++segEnd) { 
                addr = addr * 10 + (s.charAt(segEnd) - '0');
                if (addr > 0 && addr <= 0xFF) { 
                    segments[segId] = addr;
                    dfs(s, segId + 1, segEnd + 1);
                } else { 
                    break;
                }
            }
        }
    }

###### 2. 三重循环暴力遍历 ######

1.  i、j、j分别表征分隔点的位置，比如255|255|255|255，i，j，k分别为2、5、8；
2.  分割成子字符串，并且转换成数字；
3.  判断是否合理：1）数字是否小于等于255，2）连续0的个数只能为1 && 非0数字不能以0开头

import java.util.*;
    
    class lc93 { 
        static List<String> res = new ArrayList<>();
        public List<String> restoreIpAddresses(String s) { 
            int len = s.length();
            if (len > 12) return res;
            for (int i = 0; i < len - 3; i++) { 
                int num1 = Integer.parseInt(s.substring(0, i + 1));
                if (num1 > 255 || getLen(num1) != i + 1) continue;
                for (int j = i + 1; j < len - 2; j++) { 
                    int num2 = Integer.parseInt(s.substring(i + 1, j + 1));
                    if (num2 > 255 || getLen(num2) != j - i) continue;
                    for (int k = j + 1; k < len - 1; k++) { 
                        int num3 = Integer.parseInt(s.substring(j + 1, k + 1));
                        if (num3 > 255 || getLen(num3) != k - j) continue;
                        int num4 = Integer.parseInt(s.substring(k + 1, len));
                        if (num4 > 255 || getLen(num4) != len - k - 1) continue;
                        String temp = num1 + "." + num2 + "." + num3 + "." + num4;
                        res.add(temp);
                    }
                }
            }
            return res;
        }
    
        int getLen(int num) { 
            if (num == 0)
                return 1;
    //num =100， Math.log(num) / Math.log(10) =2
            return (int) (Math.log(num) / Math.log(10)) + 1;//位数
        }
    }

#### 【总结】 ####

###### 1. 全排列回溯法模板回顾 ######

if 满足结束条件:
            result.add(路径)
            return
    for 选择 in 选择列表:
        #排除不合法的选择d
        将该选择从选择列表移除（used数组 /条件限制）
        # 做选择
        路径.add(选择)
        backtrack(路径, 选择列表)
        # 撤销选择
        路径.remove(选择)

###### 2.回溯剪枝 定义出口 剪枝（排除条件+特有情况 ） 一般情况 ######

*  定义出口 if (segId == SEG\_COUNT)
 *  剪枝（排除条件+特有情况 ）

1.  if (segStart == s.length()) //提前终止
2.  if (s.charAt(segStart) == ‘0’) // 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0

*  一般情况 枚举每一种可能性并递归 做选择

###### 3. First make it work, then make it right, and, finally, make it fast. ######

首先使其正常运行，然后使其正确，最后使其快速。

先写暴力，然后再优化。

转载链接：https://leetcode-cn.com/problems/restore-ip-addresses/solution/fu-yuan-ipdi-zhi-by-leetcode-solution/

参考链接：https://leetcode-cn.com/problems/restore-ip-addresses/solution/hui-su-suan-fa-hua-tu-fen-xi-jian-zhi-tiao-jian-by/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20221124/198508bec8fb478c95893c31cc76be01.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: /images/20221124/aaf66ad87d124179a11b6aefb4e6035e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: /images/20221124/d597a716a46c4729b151af18fd913acc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 3]: /images/20221124/22d7541dab0244b9823bbd6c05c1b1b0.png