【每日一题7.11】leetcode93：复原IP地址

【字节专题】-字符串-leetcode

93. 复原IP地址

1、暴力求解

• 首先审题要清，是字符串顺序不变，这样其实就是放点的问题；
• 首先考虑好放点能成ip的条件，int（一部分）小于255，且不能有0开头；
• 划分四部分，三个循环，弄清在哪放点，弄清i+1的问题。

class Solution(object):
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        n=len(s)
        res=[]
        # 判读是否满足ip的条件
        def helper(tmp):
            if not tmp or (tmp[0]=="0"and len(tmp)>1) or int(tmp)>255:
                return False
            return True
        # 三个循环,把数字分成四份
            
        for i in range(3):#保证小数点能取到前三位，不会多取
            for j in range(i+1,i+4):
                for q in range(j+1,j+4):
                    if i < n and j < n and q < n:
                        tmp1=s[:i+1]#第一个小数点前的数要能取到
                        tmp2=s[i+1:j+1]
                        tmp3=s[j+1:q+1]
                        tmp4=s[q+1:]
                        #print(tmp1,tmp2,tmp3,tmp4)

                        if all(map(helper, [tmp1, tmp2, tmp3, tmp4])):
                            res.append(tmp1 + "."+tmp2+"."+tmp3+"."+tmp4)
        return res

2、回溯法

• 选好截止条件
• 考虑好怎么遍历（选择回溯）
• 回溯算法事实上就是在一个树形问题上做深度优先遍历，因此首先需要把问题转换为树形问题。这里请大家一定要拿起纸和笔，模拟一下如何通过指定的字符串 s 生成 IP 地址的过程，把树形图画出来（这一点很重要）。

class Solution(object):
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        n=len(s)
        res=[]
        def backtrack(count=0,id="",s=""):#count裁分成几部分；id:id s是剩余字符串
        #截止条件：裁成四部分，且不剩字符
            if count==4:
                if s=="":
                    res.append(id[:-1])
                return
        #因为最长是三位，所以按0，1，2区分间断，只有在最后一部分才判断是否<255
            if len(s)>0:
                backtrack(count+1,id+s[0]+".",s[1:])#取一位
            if len(s)>1 and s[0]!=0:
                backtrack(count+1,id+s[:2]+".",s[2:])#取两位
            if len(s)>2 and s[0]!=0 and int(s[:3])<256:
                backtrack(count+1,id+s[:3]+".",s[3:])#取两位
        backtrack(count=0,id="",s=s)
        return res
        

总结:

• all()的用法
• map()的用法
• 回溯算法的内涵：
  回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
  回溯算法则是一种参考二叉树的遍历过程中的产生的算法处理方式
  image.png

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        # 做选择
       将该选择从选择列表移除
       路径.add(选择)
       backtrack(路径, 选择列表)
       # 撤销选择
       路径.remove(选择)
       将该选择再加入选择列表

写 backtrack 函数时，需要维护属性【走过的「路径」和当前可以做的「选择列表」】，当触发「结束条件」时，将「路径」记入结果集。
例题：八皇后问题
0-1背包问题