1、括号有效性的题目一个字符串只有[]{}()这三种组合而成，判断是否是闭合有效的。
看到这个首先想到的就是使用栈这种数据结构，闭合有效就对应元素入栈出栈。
public static boolean isValid(String s){
HashMap charmap =new HashMap<>();
charmap.put('(',')');
charmap.put('[',']');
charmap.put('{','}');
Stack stack =new Stack();
for(int i =0;i<s.length();i++){
if(charmap.containsKey(s.charAt(i))){
stack.push(s.charAt(i));
continue;
}
if( stack.isEmpty() || s.charAt(i) != charmap.get(stack.pop())){
return false;
}
}
return stack.isEmpty();
}
2、使用n对'（）'可以组成的闭合字符串有哪些。
这个题目使用回溯算法，关键在于有多少个（ open 就要有多个close）去对应，最后的退出条件就是数量达到了n对
public ArrayList result =new ArrayList();//定义公共的返回结果集
public ArrayList<String> muchString(int n){
backtrace(n,new StringBuilder(),0,0);
return result;
}
public void backtrace(int n, StringBuilder sb,int open,int close){
if (sb.length() == 2*n){
result.add(sb.toString());
}
if(open < n){
sb.append('(');
backtrace(n,sb,open+1,close);
sb.deleteCharAt(sb.length()-1);
}
if(open<close){
sb.append(')');
backtrace(n,sb,open,close+1);
sb.deleteCharAt(sb.length()-1);
}
}
3、最长有效闭合括号长度是多少。
这个题目使用动态规划，主要是dp数组的定位 在这里我们将dp[]数组定义为以s[i]结尾的有效闭合括号的长度。
public static int zuichang(String s){
int[] dp =new int[s.length()];
int max = Integer.MIN_VALUE;
for(int i =1;i<s.length();i++){
if(s.charAt(i) ==')'){
if(s.charAt(i-1) =='('){
if(i>2){
dp[i] = dp[i -2] +2;
}else{
dp[i] =2;
}
}else if (i-dp[i-1] >0 && s.charAt(i-dp[i-1] -1) =='('){
dp[i] = dp[i-1] + (i -dp[i-1] >1?dp[i -dp[i-1]-2]:0) +2;
}
}
max = Math.max(max,dp[i]);
}
return max;
}
网友评论