模板网站的建设方式与方法,湖南专业seo优化公司,大流量网站 优化,一般建设网站的布局面试题85#xff1a; 问题#xff1a;
输入一个正整数n#xff0c;输出所有包含n个左括号和n个右括号的组合#xff0c;要求每个组合的左括号和右括号匹配。
解决方案#xff1a;
使用回溯法。因为要生成n个左括号和n个右括号#xff0c;故需要走2n步#xff0…面试题85 问题
输入一个正整数n输出所有包含n个左括号和n个右括号的组合要求每个组合的左括号和右括号匹配。
解决方案
使用回溯法。因为要生成n个左括号和n个右括号故需要走2n步每一步生成一个括号每一步都面临两个选项既可能生成左括号也可能生成右括号。有限制条件第一左括号和右括号的个数不能大于n第二已生成右括号的个数不能大于已生成左括号。
源代码
class Solution {public ListString generateParenthesis(int n) {ListString result new LinkedList();dfs(n,n,,result);return result;}//left表示未生成左括号个数、right表示未生成右括号个数private void dfs(int left,int right,String s,ListString result){if(left 0 right 0){result.add(s);return;}if(left 0){dfs(left-1,right,s (,result);}//当生成左括号的个数大于生成右括号的个数时出现生成右括号的情况。if(left right){dfs(left,right-1,s),result);}}
}面试题86 问题
输入一个字符串要求将它分割成若干子字符串使每个子字符串都是回文。
解决方案
使用回溯法。当处理到字符串中的某个字符时如果包括该字符在内后面还有n个字符那么此时面临n个选项即分割出长度为1的子字符串只包含该字符、分割出长度为2子字符串即包含该字符及它后面的一个字符以此类推分割出长度为n的子字符串即包含该字符在内的后面的所有字符。由于题目要求分割出来的每个子字符串都是回文因此需要逐一判断这n个子字符串是不是回文只有回文子字符串才是符合条件的分割。分割出一段回文子字符串之后接着分割后面的字符串。
源代码
class Solution {public ListListString partition(String s) {ListListString result new LinkedList();dfs(s,0,new LinkedList(),result);return result;}private void dfs(String s,int start,LinkedListString list,ListListString result){if(start s.length()){result.add(new LinkedList(list));}else{//分割出包括该字符在内后面还有n个字符长度为1的子字符串只包含该字符、分割出长度为2子字符串即包含该字符及它后面的一个字符。for(int i start;i s.length();i){if(isBack(s,start,i)){list.add(s.substring(start,i1));//继续对分割剩余部分进行判断dfs(s,i1,list,result);list.removeLast();}} }}//判断从字符串str下标start到end的子字符串是否是回文字符串。private boolean isBack(String str,int start,int end){while(start end){if(str.charAt(start) ! str.charAt(end--)){return false;}}return true;}
}面试题87 问题
输入一个只包含数字的字符串列出所有可能恢复出来的IP地址。
解决方案
使用回溯法。逐个扫描输入字符串中的字符以恢复IP地址。针对字符串中的每个数字通常面临两个选项。第1个选项是将当前字符拼接到当前分段数字的末尾拼接之后的数字应该在0到255之间。第2个选项是当前字符作为一个新的分段数字的开始。需要注意的是一个IP地址最多只有4个分段数字并且当开始一个新的分段数字时前一个分段数字不能是空的。
源代码
class Solution {public ListString restoreIpAddresses(String s) {ListString result new LinkedList();dfs(s,0,0,,,result);return result;}//i用于记录已经扫描到字符串的下标、segI表示当前分段数字的下标、seg表示当前分段字符串、ip表示已经拼接好的部分IP地址private void dfs(String s,int i,int segI,String seg,String ip,ListString result){if(i s.length() segI 3 isValidSeg(seg)){result.add(ip seg);//例如字符串s为10203040}else if(i s.length() segI 3){//当ch为2时seg为10char ch s.charAt(i);if(isValidSeg(seg ch)){//情况一添加当前char字符到该分段seg字符串变为102dfs(s,i1,segI,seg ch,ip,result);}if(seg.length() 0 segI 3){//情况二不添加当前char字符到该分段seg字符串变为2IP地址为10.dfs(s,i 1,segI 1, ch,ip seg .,result);}}}//判断当前分段数字是否有效private boolean isValidSeg(String seg){return Integer.valueOf(seg) 255 (seg.equals(0) || seg.charAt(0) ! 0);}
}
