- 判定一个由[a-z]字符构成的字符串和一个包含'?'和''通配符的字符串是否匹配。 通配符'?'匹配任意单一字符,''匹配任意多个字符包括0个字符。 字符串长度不会超过100，字符串不为空。
输入描述:
字符串 str 和包含通配符的字符串 pattern。1 <= 字符串长度 <= 100输出描述: true 表示匹配，false 表示不匹配
/**
* 判定一个由[a-z]字符构成的字符串和一个包含'.'和'*'通配符的字符串是否匹配。
* 通配符'.'匹配任意单一字符,'*'匹配任意多个字符包括0个字符。 字符串长度不
* 会超过100，字符串不为空。
* 输入描述:
* 字符串 str 和包含通配符的字符串 pattern。1 <= 字符串长度 <= 100输出
* 描述: true 表示匹配，false 表示不匹配
*/
public class IsMatch {
// 暴力递归
// 根据提议，pattern匹配串中'*'能出现在开头，且两个'*'不能连续出现（挨在一起）
public static boolean isMathch(String str,String pattern){
char[] strC = str.toCharArray();
char[] patternC = pattern.toCharArray();
return isCheck(strC,patternC) && process(strC,0,patternC,0);
}
// 递归含义，pattern从pi开始一直到结尾，能不能匹配出str从si开始一直到结尾的字符串
private static boolean process(char[] strC,int si,char[] patternC,int pi){
if(pi == patternC.length){
// 匹配串已经没有字符了，变成strC[si...],strC[i...]必须为空串
return si == strC.length;
}
// 如果pi+1不是'*',si....一定要有字符，并且si,pi的字符必须相等
if((pi+1 == patternC.length || patternC[pi+1] != '*') ){
return process(strC,si+1,patternC,pi+1) && (strC.length != si)
&& (strC[si] == patternC[pi] || patternC[pi] == '.');
}
// 如果pi+1等于'*'，pi+2不是'*'
// 假设，pi ...pi+1,可以匹配si....开始的0个字符，1个字符，两个字符。。。（主要开si开始后面有几个重复字符）
// 如果si不是最后一个元素，且si一直等于pi,就一直匹配下去
while ((strC.length != si) && (strC[si] == patternC[pi] || patternC[pi] == '.')){
if(process(strC,si,patternC,pi+2)){
return true;
}
si++;
}
return process(strC,si,patternC,pi+2);
}
public static boolean dp(String str,String pattern){
char[] strC = str.toCharArray();
char[] patternC = pattern.toCharArray();
if(!isCheck(strC,patternC)){
return false;
}
int elen = patternC.length;
int slen = strC.length;
boolean[][] dp = new boolean[str.length()+1][patternC.length+1];
// 最右下角的值为true
dp[dp.length-1][dp[0].length-1] = true;
// 每一个普遍位置依赖右下角和右边隔一行
// 最后一行
// 空字符串，怎么通过pattern匹配出来
// pattern必须满足 ...a*a*a*
for (int j = elen - 2; j > -1; j = j - 2) {
if (patternC[j] != '*' && patternC[j + 1] == '*') {
dp[slen][j] = true;
} else {
break;
}
}
if (slen > 0 && elen > 0) {
if ((patternC[elen - 1] == '.' || patternC[slen - 1] == patternC[elen - 1])) {
dp[slen - 1][elen - 1] = true;
}
}
for (int i = strC.length - 1; i > -1; i--) {
for (int j = patternC.length - 2; j > -1; j--) {
if (patternC[j + 1] != '*') {
dp[i][j] = (strC[i] == patternC[j] || patternC[j] == '.') && dp[i + 1][j + 1];
} else {
int si = i;
while (si != strC.length && (strC[si] == patternC[j] || patternC[j] == '.')) {
if (dp[si][j + 2]) {
dp[i][j] = true;
break;
}
si++;
}
if (dp[i][j] != true) {
dp[i][j] = dp[si][j + 2];
}
}
}
}
return dp[0][0];
}
// 校验字符串是否合法
private static boolean isCheck(char[] strC,char[] pattrenC){
// str中不能包含匹配字符
for (int i = 0; i < strC.length; i++) {
if(strC[i] == '*' || strC[i] == '.'){
return false;
}
}
// 匹配串
for (int i = 0; i < pattrenC.length; i++) {
if(pattrenC[i] == '*' && (i == 0 || pattrenC[i-1] == '*')){
return false;
}
}
return true;
}
}
- 给定一个数组 arr，代表一排有分数的气球。每打爆一个气球都能获得分数，假设打爆气 球 的分数为 X，获得分数的规则如下: 1)如果被打爆气球的左边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为 L;如果被打爆气球的右边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为 R。 获得分数为 LXR。 2)如果被打爆气球的左边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为 L;如果被打爆气球的右边所有气球都已经被打爆。获得分数为 LX。 3)如果被打爆气球的左边所有的气球都已经被打爆;如果被打爆气球的右边有没被打爆的 气球，找到离被打爆气球最近的气球，假设分数为 R;如果被打爆气球的右边所有气球都 已经 被打爆。获得分数为 XR。 4)如果被打爆气球的左边和右边所有的气球都已经被打爆。获得分数为 X。
目标是打爆所有气球，获得每次打爆的分数。通过选择打爆气球的顺序，可以得到不同的总分，请返回能获得的最大分数。
【举例】
arr = {3,2,5} 如果先打爆3，获得32;再打爆2，获得25;最后打爆5，获得5;最后总分21 如果先打爆3，获得32;再打爆5，获得25;最后打爆2，获得2;最后总分18 如果先打爆2，获得325;再打爆3，获得35;最后打爆5，获得5;最后总分50 如果先打爆2，获得325;再打爆5，获得35;最后打爆3，获得3;最后总分48 如果先打爆5，获得25;再打爆3，获得32;最后打爆2，获得2;最后总分18 如果先打爆5，获得25;再打爆2，获得32;最后打爆3，获得3;最后总分19 返回能获得的最大分数为50
/**
* 给定一个数组 arr，代表一排有分数的气球。每打爆一个气球都能获得分数，假设打爆气 球 的分数为 X，获得分数的
* 规则如下: 1)如果被打爆气球的左边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为 L;如果被打爆气球
* 的右边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为 R。 获得分数为 L*X*R。 2)如果被打爆气球的
* 左边有没被打爆的气球，找到离被打爆气球最近的气球，假设分数为 L;如果被打爆气球的右边所有气球都已经被打爆。获
* 得分数为 L*X。 3)如果被打爆气球的左边所有的气球都已经被打爆;如果被打爆气球的右边有没被打爆的 气球，找到离
* 被打爆气球最近的气球，假设分数为 R;如果被打爆气球的右边所有气球都 已经 被打爆。获得分数为 X*R。 4)如果被
* 打爆气球的左边和右边所有的气球都已经被打爆。获得分数为 X。
* 目标是打爆所有气球，获得每次打爆的分数。通过选择打爆气球的顺序，可以得到不同的总分，请返回能获得的最大分数。
* 【举例】
* arr = {3,2,5} 如果先打爆3，获得3*2;再打爆2，获得2*5;最后打爆5，获得5;最后总分21 如果先打爆3，获得3*2;
* 再打爆5，获得2*5;最后打爆2，获得2;最后总分18 如果先打爆2，获得3*2*5;再打爆3，获得3*5;最后打爆5，获得5;
* 最后总分50 如果先打爆2，获得3*2*5;再打爆5，获得3*5;最后打爆3，获得3;最后总分48 如果先打爆5，获得2*5;再打
* 爆3，获得3*2;最后打爆2，获得2;最后总分18 如果先打爆5，获得2*5;再打爆2，获得3*2;最后打爆3，获得3;最后总分
* 19 返回能获得的最大分数为50
*/
public class Balloon {
// 暴力递归
public static int balloon(int[] arr){
if(arr == null || arr.length == 0){
return 0;
}
int[] temp = copyArray(arr);
return process(temp,1,temp.length-2);
}
// 在L -> R上打爆所有的气球，返回可以获得的最大分数
private static int process(int[] arr,int L,int R){
if(L == R){
// 范围上只有一个气球直接打爆
return arr[L-1]*arr[L]*arr[R+1];
}
// 不止一个气球，讨论可能性，以最后一个打爆的气球是哪个位置为讨论点
// 1.若在L->R上最后一个打爆的位置是L
int max = 0;
max = process(arr,L+1,R) + arr[L-1] * arr[L] * arr[R+1];
// 2.若在L->R上最后一个打爆的位置是R
max = Math.max(max,process(arr,L,R-1) + arr[L-1] * arr[R] * arr[R+1]);
// 3.在L+1->R-1中随意打破哪个
for (int i = L+1; i < R; i++) {
max = Math.max(max,process(arr,L,i-1)+process(arr,i+1,R) + arr[L-1] * arr[i] * arr[R+1]);
}
return max;
}
private static int[] copyArray(int[] arr){
int[] copy = new int[arr.length+2];
copy[0] = 1;
for (int i = 1;i < copy.length-1;i++){
copy[i] = arr[i-1];
}
copy[copy.length-1] = 1;
return copy;
}
public static void main(String[] args) {
int[] arr = {3,2,5};
System.out.println(balloon(arr));
}
}
