- 判定一個由[a-z]字符構(gòu)成的字符串和一個包含'?'和''通配符的字符串是否匹配。 通配符'?'匹配任意單一字符,''匹配任意多個字符包括0個字符。 字符串長度不會超過100梨睁，字符串不為空障贸。
輸入描述:
字符串 str 和包含通配符的字符串 pattern擂错。1 <= 字符串長度 <= 100輸出描述: true 表示匹配，false 表示不匹配
/**
* 判定一個由[a-z]字符構(gòu)成的字符串和一個包含'.'和'*'通配符的字符串是否匹配扁眯。
* 通配符'.'匹配任意單一字符,'*'匹配任意多個字符包括0個字符。 字符串長度不
* 會超過100翅帜，字符串不為空姻檀。
* 輸入描述:
* 字符串 str 和包含通配符的字符串 pattern。1 <= 字符串長度 <= 100輸出
* 描述: true 表示匹配涝滴，false 表示不匹配
*/
public class IsMatch {
// 暴力遞歸
// 根據(jù)提議施敢，pattern匹配串中'*'能出現(xiàn)在開頭，且兩個'*'不能連續(xù)出現(xiàn)（挨在一起）
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開始一直到結(jié)尾僵娃，能不能匹配出str從si開始一直到結(jié)尾的字符串
private static boolean process(char[] strC,int si,char[] patternC,int pi){
if(pi == patternC.length){
// 匹配串已經(jīng)沒有字符了，變成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不是'*'
// 假設(shè)，pi ...pi+1,可以匹配si....開始的0個字符骤素，1個字符匙睹，兩個字符愚屁。。痕檬。（主要開si開始后面有幾個重復(fù)字符）
// 如果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];
}
// 校驗(yàn)字符串是否合法
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;
}
}
- 給定一個數(shù)組 arr梦谜，代表一排有分?jǐn)?shù)的氣球丘跌。每打爆一個氣球都能獲得分?jǐn)?shù)，假設(shè)打爆氣 球 的分?jǐn)?shù)為 X唁桩，獲得分?jǐn)?shù)的規(guī)則如下: 1)如果被打爆氣球的左邊有沒被打爆的氣球闭树，找到離被打爆氣球最近的氣球，假設(shè)分?jǐn)?shù)為 L;如果被打爆氣球的右邊有沒被打爆的氣球荒澡，找到離被打爆氣球最近的氣球报辱，假設(shè)分?jǐn)?shù)為 R。 獲得分?jǐn)?shù)為 LXR单山。 2)如果被打爆氣球的左邊有沒被打爆的氣球碍现，找到離被打爆氣球最近的氣球，假設(shè)分?jǐn)?shù)為 L;如果被打爆氣球的右邊所有氣球都已經(jīng)被打爆米奸。獲得分?jǐn)?shù)為 LX鸵赫。 3)如果被打爆氣球的左邊所有的氣球都已經(jīng)被打爆;如果被打爆氣球的右邊有沒被打爆的 氣球，找到離被打爆氣球最近的氣球躏升，假設(shè)分?jǐn)?shù)為 R;如果被打爆氣球的右邊所有氣球都 已經(jīng) 被打爆辩棒。獲得分?jǐn)?shù)為 XR。 4)如果被打爆氣球的左邊和右邊所有的氣球都已經(jīng)被打爆膨疏。獲得分?jǐn)?shù)為 X一睁。
目標(biāo)是打爆所有氣球，獲得每次打爆的分?jǐn)?shù)佃却。通過選擇打爆氣球的順序者吁，可以得到不同的總分，請返回能獲得的最大分?jǐn)?shù)饲帅。
【舉例】
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 返回能獲得的最大分?jǐn)?shù)為50
/**
* 給定一個數(shù)組 arr芯义，代表一排有分?jǐn)?shù)的氣球。每打爆一個氣球都能獲得分?jǐn)?shù)妻柒，假設(shè)打爆氣 球 的分?jǐn)?shù)為 X扛拨，獲得分?jǐn)?shù)的
* 規(guī)則如下: 1)如果被打爆氣球的左邊有沒被打爆的氣球，找到離被打爆氣球最近的氣球举塔，假設(shè)分?jǐn)?shù)為 L;如果被打爆氣球
* 的右邊有沒被打爆的氣球绑警，找到離被打爆氣球最近的氣球，假設(shè)分?jǐn)?shù)為 R央渣。 獲得分?jǐn)?shù)為 L*X*R计盒。 2)如果被打爆氣球的
* 左邊有沒被打爆的氣球，找到離被打爆氣球最近的氣球芽丹，假設(shè)分?jǐn)?shù)為 L;如果被打爆氣球的右邊所有氣球都已經(jīng)被打爆北启。獲
* 得分?jǐn)?shù)為 L*X。 3)如果被打爆氣球的左邊所有的氣球都已經(jīng)被打爆;如果被打爆氣球的右邊有沒被打爆的 氣球拔第，找到離
* 被打爆氣球最近的氣球咕村，假設(shè)分?jǐn)?shù)為 R;如果被打爆氣球的右邊所有氣球都 已經(jīng) 被打爆。獲得分?jǐn)?shù)為 X*R蚊俺。 4)如果被
* 打爆氣球的左邊和右邊所有的氣球都已經(jīng)被打爆懈涛。獲得分?jǐn)?shù)為 X。
* 目標(biāo)是打爆所有氣球泳猬，獲得每次打爆的分?jǐn)?shù)批钠。通過選擇打爆氣球的順序，可以得到不同的總分得封，請返回能獲得的最大分?jǐn)?shù)埋心。
* 【舉例】
* 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 返回能獲得的最大分?jǐn)?shù)為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上打爆所有的氣球咒吐，返回可以獲得的最大分?jǐn)?shù)
private static int process(int[] arr,int L,int R){
if(L == R){
// 范圍上只有一個氣球直接打爆
return arr[L-1]*arr[L]*arr[R+1];
}
// 不止一個氣球，討論可能性属划，以最后一個打爆的氣球是哪個位置為討論點(diǎn)
// 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));
}
}
