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

11.String转int，即atoi函数实现。

主要考虑以下几种情况：

1.      String为空

2.      String中存在非数字字符，如空白字符，abcd等

3.      String的正负

Code：

public class test {
	public static int atoi(String str) {
		if (str == null || str.length() < 1)
			return 0;
		str = str.trim();

		char flag = '+';
		int i = 0;
		if (str.charAt(0) == '-' || str.charAt(0) == '+') {
			++i;
			flag = str.charAt(0);
		}

		double result = 0;

		int j = i;
		while (str.length() > j) {
			if (str.charAt(j) < '0' || str.charAt(i) > '9') {
				System.err.println("Bad Input");
				return Integer.MIN_VALUE;
			}
			++j;
		}
		while (str.length() > i && str.charAt(i) > '0' && str.charAt(i) < '9') {
			result = result * 10 + (str.charAt(i) - '0');
			++i;
		}

		if (flag == '-')
			result = -result;

		if (result > Integer.MAX_VALUE)
			return Integer.MAX_VALUE;
		if (result < Integer.MIN_VALUE)
			return Integer.MIN_VALUE;

		return (int) result;
	}

	public static void main(String[] args) {
		int i = atoi("1+2");
		int j = atoi("55");
		System.out.println("i:" + i + ",j:" + j);
	}
}

12.合并有序数组

给定两个数组A和B，将B合入A中

Code：

public void merge(int A[], int m, int B[], int n) {
	int i = m - 1;
	int j = n - 1;
	int k = m + n - 1;
 
	while (k >= 0) {
		if (j < 0 || (i >= 0 && A[i] > B[j]))
			A[k--] = A[i--];
		else
			A[k--] = B[j--];
	}
}

13.括号匹配

给定一个包含‘(‘,‘)‘, ‘{‘, ‘}‘, ‘[‘ 和 ‘]‘的字符串，判断其中各括号是否匹配

括号匹配必然需要stack，此外还需要map确定是否匹配

Code：

import java.util.HashMap;
import java.util.Stack;

public class test {
	public static boolean bValid(String s) {
		HashMap<Character, Character> map = new HashMap<Character, Character>();
		map.put('(', ')');
		map.put('[', ']');
		map.put('{', '}');

		Stack<Character> stack = new Stack<Character>();

		for (int i = 0; i < s.length(); i++) {
			char curr = s.charAt(i);

			if (map.keySet().contains(curr)) {
				stack.push(curr);
			} else if (map.values().contains(curr)) {
				if (!stack.empty() && map.get(stack.peek()) == curr) {
					stack.pop();
				} else {
					return false;
				}
			}
		}
		return stack.empty();
	}

	public static void main(String[] args) {
		System.out.println(bValid("{()}"));
	}
}