题目链接：
1. 计算逆波兰式
题目要求如下：
["2","1", "+", "3", "*"] -> ((2 + 1) * 3)-> 9
["4","13", "5", "/", "+"] -> (4 + (13 /5)) -> 6
也就是说给定一个逆波兰式数组，计算其结果。
如：
输入：["2","1", "+", "3", "*"]
输出：9
显然我们可以考虑使用栈。
思路如下：
遍历输入数组，当数组成员为数字时，则入栈；当数组成员为运算符时，取出栈中的数字进行运算。
数组遍历完成后栈中留下的数字即为计算结果。
code：
import java.util.Stack;public class test {public static int GetResult(String[] tokens) {int returnValue = 0;String operators = "+-*/";Stack<String> stack = new Stack<String>();for (String t : tokens) {// 若t不是operators字符串中的某个字符，则说明t是数字if (!operators.contains(t)) {stack.push(t);} else {int a = Integer.valueOf(stack.pop());int b = Integer.valueOf(stack.pop());switch (t) {case "+":stack.push(String.valueOf(a + b));break;case "-":stack.push(String.valueOf(a – b));break;case "*":stack.push(String.valueOf(a * b));break;case "/":stack.push(String.valueOf(a / b));break;}}}returnValue = Integer.valueOf(stack.pop());return returnValue;}public static void main(String[] args) {// TODO Auto-generated method stubString[] tokens = new String[] { "2", "1", "+", "3", "*" };int Revresult = GetResult(tokens);System.out.println("Reuslt:" + Revresult);}}
2.求回文字串
最简单的方法为遍历字符串，求出长度最大的回文：
public class test {public static String longestPalindrome(String s) {int maxPalinLength = 0;String longestPalindrome = null;int length = s.length();// check all possible sub stringsfor (int i = 0; i < length; i++) {for (int j = i + 1; j < length; j++) {int len = j – i;String curr = s.substring(i, j + 1);if (isPalindrome(curr)) {if (len > maxPalinLength) {longestPalindrome = curr;maxPalinLength = len;}}}}return longestPalindrome;}public static boolean isPalindrome(String s) {for (int i = 0; i < s.length() – 1; i++) {if (s.charAt(i) != s.charAt(s.length() – 1 – i)) {return false;}}return true;}public static void main(String[] args) {// TODO Auto-generated method stubString tokens = "aabcdc";String Revresult = longestPalindrome(tokens);System.out.println("Reuslt:" + Revresult);}}
第二种解法为动态规划法：建立一个二维表，其中t[i][j]用于表示字符串t中从i到j的子串是否为回文(1表示是回文，0表示非回文)。
1.初始化：建立长宽为t.length的二维矩阵，将对角线t[i][i]置1
2.若两两相邻的字符相等，则也为回文，因此检查相邻字符，，即为t[i][i+1]赋值
3.若t[i+1][j-1] == 1 && s.charAt(i) == s.charAt(j)，则t[i][j] == 1
public class test {public static String longestPalindrome2(String s) {if (s == null)return null;if (s.length() <= 1)return s;int maxLen = 0;String longestStr = null;int length = s.length();int[][] table = new int[length][length];for (int i = 0; i < length; i++) {table[i][i] = 1;}for (int i = 0; i <= length – 2; i++) {if (s.charAt(i) == s.charAt(i + 1)) {table[i][i + 1] = 1;longestStr = s.substring(i, i + 2);}}for (int l = 3; l <= length; l++) {for (int i = 0; i <= length – l; i++) {int j = i + l – 1;if (s.charAt(i) == s.charAt(j)) {table[i][j] = table[i + 1][j – 1];if (table[i][j] == 1 && l > maxLen)longestStr = s.substring(i, j + 1);} else {table[i][j] = 0;}}}return longestStr;}public static void main(String[] args) {// TODO Auto-generated method stubString tokens = "aabcdc";String Revresult = longestPalindrome2(tokens);System.out.println("Reuslt:" + Revresult);}}
最后还有一个：
构造helper函数：public String helper(String s, int begin, int end)，其功能为求出以begin、end为中心的回文的字串，之后遍历字符串中所有位。
public class test {public static String longestPalindrome(String s) {if (s.isEmpty()) {return null;}if (s.length() == 1) {return s;}String longest = s.substring(0, 1);for (int i = 0; i < s.length(); i++) {// get longest palindrome with center of iString tmp = helper(s, i, i);if (tmp.length() > longest.length()) {longest = tmp;}// get longest palindrome with center of i, i+1tmp = helper(s, i, i + 1);if (tmp.length() > longest.length()) {longest = tmp;}}return longest;}// Given a center, either one letter or two letter,// Find longest palindromepublic static String helper(String s, int begin, int end) {while (begin >= 0 && end <= s.length() – 1&& s.charAt(begin) == s.charAt(end)) {begin–;end++;}return s.substring(begin + 1, end);}public static void main(String[] args) {// TODO Auto-generated method stubString tokens = "aabcdc";String Revresult = longestPalindrome(tokens);System.out.println("Reuslt:" + Revresult);}}
走过的路成为背后的风景，不能回头不能停留，若此刻停留，
