某公司面试笔试题目(在线
笔编程题两个
1.用冒泡算法实现整数数组排序,
2.实现一个计算器可以计算加减乘除
要求是考虑程序的健壮性
冒泡排序:
比较相邻两个数的大小,如果前者比后者大,则交换两者。
先来一个最简单的例子 3,2,1
对[0,2]区间内相邻的数进行冒泡操作, 3和2交换位置,3和1交换位置 2,1,3
对[0,1]区间内相邻的数进行冒泡操作,2和1交换位置, 1,2,3
对[0,0]区间内相邻的数进行冒泡操作,右端点到0,结束。
外循环: 区间的右端点r从len-1逐渐减小到0,
内循环: 对[0,r]内相邻的数进行冒泡操作。 j由0->r-1,比较item[j] 和 item[j+1]的大小
public class Sort { public static void main(String[] args) { int[] itmes = new int[]{3,2,1} ; sort(itmes); System.out.println(); } public static void sort(int[] items) { int length = items.length; for (int r = length - 1; r > 0; r--) { for (int j = 0; j <= r - 1; j++) { if (items[j] > items[j + 1]) { int tmp = items[j + 1]; items[j + 1] = items[j]; items[j] = tmp; } } } } }
稳定性: 稳定
时间复杂度O(N^2)
空间复杂度O(1)
第二道题目:
分析: + - * / ( ) 0-9
1+2 (1,2,+) 对1和2进行加操作运算
1+2*3+2 ((1,(2,3,*),+) ,2,+)
1+2*(1-2) (1,(2,(1,2,-),*),+)
采用两个栈(stack),一个栈(dataStack) 存在数值,一个栈(operatorStack)存放操作符号。
关于数值的解析: 从正负号开始||从数字开始,直到遇到操作符结束 || 表达式结束
关于正负号的识别:
第0个字符可以是正负号
-1+1 中的第0个字符是负号
(后可以接正负号
1-(-2-3)中的 数字2前面的字符是负号
即遇到操作符时,前面可能一个数值,我们需要将此数值压入dataStack
遇到操作符号进行的处理:
判断该操作符号是否需要压入栈中
需要压入栈中的情况:
1:operatorStack为空
2:符号本身为(, 或者栈顶元素为(
3:本符号的优先级比栈顶元素的优先级高 (乘除高于加减)
其他的情况:
如果符号为")"
如 (1+2*3) 弹出*号,2和3做乘法, 再弹出+号,1和6做加法,弹出"(" , 结束
另外一种情况:
1+2*3 + 2
* 优先级高于+ 2*3 先计算
+ 优先级高于 + 1+6 先计算
操作栈顶元素的优先级比本符号的优先级高,那么弹出栈顶的操作符
异常情况分析:
1:1(2, 1a2 操作符号不是加减乘除符号)
2: 1++2 +++ 计算时缺数字
3:(1+2 1+2) 括号未正常关闭
4:除数不能为0
5: +++ (++ 会导致解析数字异常
遗憾, 后两种异常未处理。
正常结束 dataStack的size为1, operatorStack的size为0.
import java.util.Stack; public class ExpressEval { public static void main(String[] args) { // -123 + 345 ; String test = "9/7/1"; int result = eval(test); System.out.println(result); } public static int eval(String input) { Stack<Integer> dataStack = new Stack<>(); Stack<Character> operatorStack = new Stack<>(); // assert input 不为空 char[] items = input.toCharArray(); int length = items.length; StringBuilder sb = new StringBuilder(); for (int i = 0; i < length; i++) { char item = items[i]; if ((item == '+' || item == '-') && (i == 0 || items[i - 1] == '(')) { sb.append(item); } else if (item <= '9' && item >= '0') { sb.append(item); } else { if (sb.length() > 0) { int number = parseInt(sb); dataStack.push(number); sb = new StringBuilder(); } if (operatorStack.empty()) { if (item == ')') { throw new IllegalArgumentException("非法表达式"); } operatorStack.push(item); } else { char top = operatorStack.peek(); if (item == '(' || top == '(') { operatorStack.push(item); } else if (item == ')') { for (; ; ) { if (operatorStack.empty()) { throw new IllegalArgumentException("非法表达式,未找到与之匹配的("); } char operator = operatorStack.pop(); if (operator == '(') { break; } int tmp = cal(dataStack, operator); dataStack.push(tmp); } } else if ((item == '*' || item == '/') && (top == '+' || top == '-')) { operatorStack.push(item); } else { while (!operatorStack.empty()) { top = operatorStack.peek(); if (top == '(') { break; } if (youxian(top, item)) { operatorStack.pop(); int tmp = cal(dataStack, top); dataStack.push(tmp); } else { break; } } operatorStack.push(item); } } } } if (sb.length() > 0) { dataStack.push(parseInt(sb)); } while (!operatorStack.empty()) { char op = operatorStack.pop(); int tmp = cal(dataStack, op); dataStack.push(tmp); } if (dataStack.size() != 1 || operatorStack.size() != 0) { throw new IllegalArgumentException("非法表达式"); } return dataStack.pop(); } public static boolean youxian(char top, char current) { if ((current == '+' || current == '-') || (top == '*' || top == '/')) { return true; } return false; } public static int cal(Stack<Integer> data, char operator) { if (data.size() < 2 || !(operator == '+' || operator == '-' || operator == '*' || operator == '/')) { throw new IllegalArgumentException("表达式非法"); } int data2 = data.pop(); int data1 = data.pop(); if (operator == '+') { return data1 + data2; } else if (operator == '-') { return data1 - data2; } else if (operator == '*') { return data1 * data2; } else { return data1 / data2; } } public static int parseInt(StringBuilder sb) { if (sb.length() == 1 && (sb.charAt(0) == '+' || sb.charAt(0) == '-')) { throw new IllegalArgumentException("表达式非法"); } try { return Integer.parseInt(sb.toString()); } catch (Exception e) { throw new IllegalArgumentException("解析整数抛出了异常"); } } }#面试题目#