- 对于一个字符串, 从前开始读和从后开始读是一样的, 我们就称这个字符串是回文串。例如"ABCBA","AA", "A" 是回文串, 而"ABCD", "AAB"不是回文串。牛牛特别喜欢回文串, 他手中有一个字符串s, 牛牛在思考能否从字 符串中移除部分(0个或多个)字符使其变为回文串，并且牛牛认为空串不是回文串。牛牛发现移除的方案可能有 很多种, 希望你来帮他计算一下一共有多少种移除方案可以使s变为回文串。对于两种移除方案, 如果移除的字 符依次构成的序列不一样就是不同的方案。
例如，XXY 4种 ABA 5种
【说明】 这是今年的原题，提供的说明和例子都很让人费解。现在根据当时题目的所有测试用例，重新解释当时的题目 含义: 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;
}
// 倒数第二条对角线
for (int i = 0; i < n-1; i++) {
dp[i][i+1] = c[i] == c[i+1] ? 3 : 2;
}
// 普遍位置,倒数前二行都已经填过了，不用填，
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;
}
// 倒数第二条对角线
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位置字符相等)
// 从下往上，从左往右
// 倒数第三行开始
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];
}
}
- 给定一个二维数组matrix，每个单元都是一个整数，有正有负。最开始的时候小Q操纵 一条长度为0的蛇蛇从矩阵最左侧任选一个单元格进入地图，蛇每次只能够到达当前位 置的右上相邻，右侧相邻和右下相邻的单元格。蛇蛇到达一个单元格后，自身的长度会 瞬间加上该单元格的数值，任何情况下长度为负则游戏结束。小Q是个天才，他拥有一 个超能力，可以在游戏开始的时候把地图中的某一个节点的值变为其相反数(注:最多 只能改变一个节点)。问在小Q游戏过程中，他的蛇蛇最长长度可以到多少?
比如:
1 -4 10
3 -2 -1
2 -1 0
0 5 -2
最优路径为从最左侧的3开始，3 -> -4(利用能力变成4) -> 10。所以返回17。
- 给定一个字符串str，str表示一个公式，公式里可能有整数、加减乘除符号和左右 括号，返回公式的计算结果。
【举例】
str="48((70-65)-43)+81"，返回-1816。
str="3+14"，返回7。
str="3+(14)"，返回7。
【说明】 1.可以认为给定的字符串一定是正确的公式，即不需要对str做公式有效性检查。 2.如果是负数，就需要用括号括起来，比如"4(-3)"。但如果负数作为公式的开头 或括号部分的开头，则可以没有括号，比如"-34"和"(-3*4)"都是合法的。 3.不用考虑计算过程中会发生溢出的情况。
/**
* 给定一个字符串str，str表示一个公式，公式里可能有整数、加减乘除符号和左右 括号，返回公式的计算结果。
* 【举例】
* str="48*((70-65)-43)+8*1"，返回-1816。
* str="3+1*4"，返回7。
* str="3+(1*4)"，返回7。
* 【说明】 1.可以认为给定的字符串一定是正确的公式，即不需要对str做公式有效性检查。 2.如果是负数，
* 就需要用括号括起来，比如"4*(-3)"。但如果负数作为公式的开头 或括号部分的开头，则可以没有括号，比
* 如"-3*4"和"(-3*4)"都是合法的。 3.不用考虑计算过程中会发生溢出的情况。
*/
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){
// 当前的数字
int cur = 0;
LinkedList<String> stack = new LinkedList<>();
int[] res = new int[2];
// 越界或者遇到右括号停止
while (index < c.length && c[index] != ')'){
// 如果遇到的是数字就收集数字
if(c[index] >= '0' && c[index] <= '9'){
// 数字
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));
}
}
