南宁网站制作专业,中国企业排名前十名,郑州手机网站推广公司,sem优化专员《算法通关村——回溯模板如何解决回溯问题》
93. 复原 IP 地址
有效 IP 地址 正好由四个整数#xff08;每个整数位于 0 到 255 之间组成#xff0c;且不能含有前导 0#xff09;#xff0c;整数之间用 . 分隔。
例如#xff1a;0.1.2.201 和 192.1…《算法通关村——回溯模板如何解决回溯问题》
93. 复原 IP 地址
有效 IP 地址 正好由四个整数每个整数位于 0 到 255 之间组成且不能含有前导 0整数之间用 . 分隔。
例如0.1.2.201 和 192.168.1.1 是 有效 IP 地址但是 0.011.255.245、192.168.1.312 和 192.1681.1 是 无效 IP 地址。
给定一个只包含数字的字符串 s 用以表示一个 IP 地址返回所有可能的有效 IP 地址这些地址可以通过在 s 中插入 . 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例 1
输入s 25525511135
输出[255.255.11.135,255.255.111.35]示例 2
输入s 0000
输出[0.0.0.0]示例 3
输入s 101023
输出[1.0.10.23,1.0.102.3,10.1.0.23,10.10.2.3,101.0.2.3]提示
1 s.length 20s 仅由数字组成
题解
class Solution {ListString result new ArrayList();public ListString restoreIpAddresses(String s) {if(s.length() 4 || s.length() 12){return result;}backTrace(s,0,0);return result;}// startIndex: 搜索的起始位置 pointNum: 添加小数点的数量private void backTrace(String s,int startIndex, int pointNum){if(pointNum 3){// 小数点数量为3时结束分割// 判断第四段子字符串是否合法如果合法就放进result中if (isValid(s,startIndex,s.length()-1)){result.add(s);}return;}for(int i startIndex;is.length() ;i){if(isValid(s,startIndex,i)){// 在 Str 的后面插入小数点s s.substring(0,i1) . s.substring(i1);pointNum;// 插入小数点之后下一个字串的起始位置为 i 2backTrace(s, i2 ,pointNum);pointNum--;// 撤销操作s s.substring(0,i1) s.substring(i2);// 撤销操作}else{break;}}}private Boolean isValid(String s,int start , int end) {if (start end){return false;}// 0开头的数字不合法if(s.charAt(start) 0 start ! end){return false;}int num 0;for(int i start;iend;i){//遇到非数字字符不合法if(s.charAt(i) 9 || s.charAt(i) 0){return false;}num num * 10 (s.charAt(i) - 0) ;if( num 255) {return false;}}return true;}
}17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。 示例 1
输入digits 23
输出[ad,ae,af,bd,be,bf,cd,ce,cf]示例 2
输入digits
输出[]示例 3
输入digits 2
输出[a,b,c]提示
0 digits.length 4digits[i] 是范围 [2, 9] 的一个数字。
题解
class Solution {ListString list new ArrayList();public ListString letterCombinations(String digits) {if(digits null || digits.length() 0){return list;}// 初始对应所有的数字为了直接对应 2 - 9新增了两个无效的字符串String[] numString {,,abc,def,ghi,jkl,mno,pqrs,tuv,wxyz};backTracking(digits,numString,0);return list;}// 每次迭代获取一个字符串所以会涉及大量的字符嫔节所以这里选择更为高效的 StringBuilderStringBuilder temp new StringBuilder();// 比如digits如果为”23“num0则str表示2的对应abcpublic void backTracking(String digits,String[] numString,int num){// 遍历全部一次记录一次得到的字符串if ( num digits.length()){list.add(temp.toString());return ;}// str 表示当前num 对应的字符串String str numString[digits.charAt(num) - 0];for(int i 0;i str.length() ;i){temp.append(str.charAt(i));backTracking(digits,numString,num1);temp.deleteCharAt(temp.length() - 1);}}
}22. 括号生成
数字 n 代表生成括号的对数请你设计一个函数用于能够生成所有可能的并且 有效的 括号组合。
示例 1
输入n 3
输出[((())),(()()),(())(),()(()),()()()]示例 2
输入n 1
输出[()]提示
1 n 8
题解
class Solution {public ListString generateParenthesis(int n) {ListString ans new ArrayListString();backTracking(ans,new StringBuilder(),0,0,n);return ans;}public void backTracking(ListString ans,StringBuilder cur,int open,int close,int max) {if(cur.length() max *2 ){ans.add(cur.toString());return ;}if(open max){cur.append(();backTracking(ans,cur,open1,close,max);cur.deleteCharAt(cur.length() - 1);}if(close open ){cur.append());backTracking(ans,cur,open,close 1,max);cur.deleteCharAt(cur.length() - 1);}}
}
