【字节专题】-字符串-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背包问题
