面试10大算法题汇总-字符串和数组1

题目链接：

http://blog.csdn.net/xiaoranlr/article/details/43963933

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 stub
		String[] 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 strings
		for (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 stub
		String 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 stub
		String 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 i
			String tmp = helper(s, i, i);
			if (tmp.length() > longest.length()) {
				longest = tmp;
			}

			// get longest palindrome with center of i, i+1
			tmp = 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 palindrome
	public 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 stub
		String tokens = "aabcdc";
		String Revresult = longestPalindrome(tokens);
		System.out.println("Reuslt:" + Revresult);
	}
}