- 對于一個字符串, 從前開始讀和從后開始讀是一樣的, 我們就稱這個字符串是回文串。例如"ABCBA","AA", "A" 是回文串, 而"ABCD", "AAB"不是回文串。牛牛特別喜歡回文串, 他手中有一個字符串s, 牛牛在思考能否從字 符串中移除部分(0個或多個)字符使其變?yōu)榛匚拇?，并且牛牛認為空串不是回文串。牛牛發(fā)現(xiàn)移除的方案可能有 很多種, 希望你來幫他計算一下一共有多少種移除方案可以使s變?yōu)榛匚拇?。對于兩種移除方案, 如果移除的字 符依次構成的序列不一樣就是不同的方案。
例如，XXY 4種 ABA 5種
【說明】 這是今年的原題，提供的說明和例子都很讓人費解?，F(xiàn)在根據(jù)當時題目的所有測試用例，重新解釋當時的題目 含義: 1)"1AB23CD21"，你可以選擇刪除A、B、C、D，然后剩下子序列{1,2,3,2,1}，只要剩下的子序列是同一個，那 么就只算1種方法，和A、B、C、D選擇什么樣的刪除順序沒有關系。 2)"121A1"，其中有兩個{1,2,1}的子序列，第一個{1,2,1}是由{位置0，位置1，位置2}構成，第二個{1,2,1} 是由{位置0，位置1，位置4}構成。這兩個子序列被認為是不同的子序列。也就是說在本題中，認為字面值一樣 但是位置不同的字符就是不同的。 3)其實這道題是想求，str中有多少個不同的子序列，每一種子序列只對應一種刪除方法，那就是把多余的東 西去掉，而和去掉的順序無關。
4)也許你覺得我的解釋很荒謬，但真的是這樣，不然解釋不了為什么，XXY 4種 ABA 5種，而且其他的測 試用例都印證了這一點。
public class PalindromeNum {
// 范圍上的嘗試模型
public static int palindromeNum(String str){
if(str == null || str.equals("")){
return 0;
}
char[] c = str.toCharArray();
int n = c.length;
int[][] dp = new int[n][n];
// 對角線全是1
for (int i = 0; i < c.length; i++) {
dp[i][i] = 1;
}
// 倒數(shù)第二條對角線
for (int i = 0; i < n-1; i++) {
dp[i][i+1] = c[i] == c[i+1] ? 3 : 2;
}
// 普遍位置,倒數(shù)前二行都已經(jīng)填過了，不用填，
for (int i = n - 3; i >= 0 ; i--) {
for (int j = i+2; j < n; j++) {
dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1];
if(c[i] == c[j]){
dp[i][j] += dp[i+1][j-1] + 1;
}
}
}
return dp[0][n-1];
}
public static void main(String[] args) {
String str1 = "xxy";
String str2 = "ABA";
System.out.println(palindromeNum(str1));
System.out.println(palindromeNum(str2));
}
}
/**
* 給定一個字符串str，求最長回文子序列長度。
*/
public class MaxLenPalindromeSubSeq {
public static int maxLenPalindromeSubSeq(String str){
if(str == null || str.equals("")){
return 0;
}
// 范圍上嘗試的模型
// dp[i][j] 表示以開頭，j結尾的子串中最長回文子序列是多少
// 由于是范圍上的嘗試模型，則左下部分無效
int n = str.length();
char[] c = str.toCharArray();
int[][] dp = new int[n][n];
// 對角線
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
// 倒數(shù)第二條對角線
for (int i = 0; i < n-1; i++) {
dp[i][i+1] = c[i] == c[i+1] ? 2 : 1;
}
// 普遍位置
// 1.i...j的回文子串以不以i，j結尾dp[i][j] = dp[i+1][j-1]
// 2.i...j的回文子串以i開頭，不以j結尾 dp[i][j] = dp[i][j-1]
// 3.i...j的回文子串不以i開頭，以j結尾 dp[i][j] = dp[i+1][j]
// 4.i...j的回文子串以i開頭，以j結尾 dp[i][j] = dp[i+1][j-1](i,j位置字符相等)
// 從下往上，從左往右
// 倒數(shù)第三行開始
for (int i = c.length-3; i >= 0; i--) {
for (int j = i+2; j < n; j++) {
dp[i][j] = Math.max(dp[i+1][j-1],Math.max(dp[i][j-1],dp[i+1][j]));
if(c[i] == c[j]){
dp[i][j] = Math.max(dp[i][j],dp[i+1][j-1]+2);
}
}
}
return dp[0][n-1];
}
}
- 給定一個二維數(shù)組matrix，每個單元都是一個整數(shù)，有正有負。最開始的時候小Q操縱 一條長度為0的蛇蛇從矩陣最左側任選一個單元格進入地圖，蛇每次只能夠到達當前位 置的右上相鄰，右側相鄰和右下相鄰的單元格。蛇蛇到達一個單元格后，自身的長度會 瞬間加上該單元格的數(shù)值，任何情況下長度為負則游戲結束。小Q是個天才，他擁有一 個超能力，可以在游戲開始的時候把地圖中的某一個節(jié)點的值變?yōu)槠湎喾磾?shù)(注:最多 只能改變一個節(jié)點)。問在小Q游戲過程中，他的蛇蛇最長長度可以到多少?
比如:
1 -4 10
3 -2 -1
2 -1 0
0 5 -2
最優(yōu)路徑為從最左側的3開始，3 -> -4(利用能力變成4) -> 10。所以返回17。
- 給定一個字符串str，str表示一個公式，公式里可能有整數(shù)、加減乘除符號和左右 括號，返回公式的計算結果。
【舉例】
str="48((70-65)-43)+81"，返回-1816。
str="3+14"，返回7。
str="3+(14)"，返回7。
【說明】 1.可以認為給定的字符串一定是正確的公式，即不需要對str做公式有效性檢查。 2.如果是負數(shù)，就需要用括號括起來，比如"4(-3)"。但如果負數(shù)作為公式的開頭 或括號部分的開頭，則可以沒有括號，比如"-34"和"(-3*4)"都是合法的。 3.不用考慮計算過程中會發(fā)生溢出的情況。
/**
* 給定一個字符串str，str表示一個公式，公式里可能有整數(shù)、加減乘除符號和左右 括號，返回公式的計算結果。
* 【舉例】
* str="48*((70-65)-43)+8*1"，返回-1816。
* str="3+1*4"，返回7。
* str="3+(1*4)"，返回7。
* 【說明】 1.可以認為給定的字符串一定是正確的公式，即不需要對str做公式有效性檢查。 2.如果是負數(shù)，
* 就需要用括號括起來，比如"4*(-3)"。但如果負數(shù)作為公式的開頭 或括號部分的開頭，則可以沒有括號，比
* 如"-3*4"和"(-3*4)"都是合法的。 3.不用考慮計算過程中會發(fā)生溢出的情況。
*/
public class Calculate {
public static int calculate(String str){
char[] c = str.toCharArray();
return process(c,0)[0];
}
// 從index開始算，返回index開始計算的有效結果，和計算到的位置
//0位置，結果；1位置，此次計算到的位置
public static int[] process(char[] c,int index){
// 當前的數(shù)字
int cur = 0;
LinkedList<String> stack = new LinkedList<>();
int[] res = new int[2];
// 越界或者遇到右括號停止
while (index < c.length && c[index] != ')'){
// 如果遇到的是數(shù)字就收集數(shù)字
if(c[index] >= '0' && c[index] <= '9'){
// 數(shù)字
cur = cur * 10 + (c[index] - '0');
index ++;
}else if(c[index] == '+' || c[index] == '-' || c[index] == '*' || c[index] == '/'){
// 如果棧頂是乘除先計算在放
if("*".equals(stack.peekFirst()) || "/".equals(stack.peekFirst())){
String op = stack.pop();
String num = stack.pop();
int re = 0;
if("*".equals(op)){
re = cur*Integer.parseInt(num);
}else {
re = cur/Integer.parseInt(num);
}
stack.push(re+"");
stack.push(String.valueOf(c[index]));
cur = 0;
}else{
stack.push(cur+"");
stack.push(String.valueOf(c[index]));
cur = 0;
}
index++;
}else{
//左括號調用遞歸過程
int[] process = process(c, index + 1);
if("*".equals(stack.peekFirst()) ||"/".equals(stack.peekFirst())){
String op = stack.pop();
String num = stack.pop();
int re = 0;
if("*".equals(op)){
re = process[0]*Integer.parseInt(num);
}else {
re = process[0]/Integer.parseInt(num);
}
cur = re;
index = process[1]+1;
}else{
cur = process[0];
index = process[1]+1;
}
}
}
int d = 0;
if("*".equals(stack.peekFirst()) || "/".equals(stack.peekFirst())){
String op = stack.pop();
String num = stack.pop();
int re = 0;
if("*".equals(op)){
re = cur*Integer.parseInt(num);
}else {
re = cur/Integer.parseInt(num);
}
stack.push(re+"");
}else{
stack.push(cur+"");
}
while (stack.size() >=2){
int one = Integer.valueOf(stack.pollLast());
String op = stack.pollLast();
int two = Integer.valueOf(stack.pollLast());
if(op.equals("+")){
d = one + two;
}else{
d = one - two;
}
stack.addLast(d+"");
}
return new int[]{d,index};
}
public static void main(String[] args) {
String str = "48*((70-65)-43)+8*1";
System.out.println(calculate(str));
}
}
