数据结构面试题
常见的数据结构一. 数组1.寻找数组中第二大的元素2.寻找数组中不重复出现的整数3.实现数组中负数在左，正数在右二. 栈1.用栈计算后缀表达式2.对栈数据进行排序2.用栈来判断括号匹配问题三. 队列常见的数据结构
数组栈队列链表树图字典树(高效树形结构)散列表(哈希表)一. 数组
1.寻找数组中第二大的元素
//冒泡排序法public static void getMethod_1(int[] array){int temp = 0;int len = array.length;for(int i = 0;i<len;i++){if(i == len-1){break;}for(int j = i+1;j<len;j++){if(array[i]>=array[j])continue;else{temp = array[j];array[j] = array[i];array[i] = temp;}}}System.out.println(array[1]);}public static void main(String[] args) {getMethod_1(new int[]{1,2,3,9,8,7,5,6,-1,-2,-3,-9,-8,-7,-5,-6});}
2.寻找数组中不重复出现的整数
//有且只有一个数字不重复public static int getMethod_2(int[] array){int len = array.length;int res = -1;if(len>1){res = array[0];for(int i = 1;i<len;i++){res = res^array[i];}}return res;}//有多个不重复数字，找出所有不重复数字public static ArrayList<Integer> getMethod_3(int[] array){ArrayList<Integer> res = new ArrayList<Integer>();if(array==null||array.length<2)return res;Map<Integer,Integer> map = new LinkedHashMap<>();for(int i = 0;i<array.length;i++){if(map.containsKey(array[i]))map.put(array[i],map.get(array[i])+1);elsemap.put(array[i], 1);}for(Integer key : map.keySet()){if(map.get(key) == 1)res.add(key);}return res;}//寻找数组中第一个不重复出现的字符public static char findFirst(String str) {if (str == null || str.length() == 0)return '#';int[] hashtable = new int[256];int len = str.length();char[] arr = str.toCharArray();for (int i = 0; i < len; i++) {hashtable[arr[i]]++;}for (int i = 0; i < len; i++) {if (hashtable[arr[i]] == 1)return arr[i];}return '#';}public static void main(String[] args) {//不重复的数字只有一个,找到这个数int number = getMethod_2(new int[]{1,1,1,1,1,1,1,1,1,-2,1,1,1});System.out.println(number);//寻找数组中第一个不重复出现的整数ArrayList<Integer> number_3 = getMethod_3(new int[]{8,7,5,6,-1,-2,-3,-9,-8,-7,-5,-6,1,2,3,9,8});System.out.println(number_3.size()>0?number_3.get(0):"没有找到不重复数字");}
3.实现数组中负数在左，正数在右
/*** 方式一* 实现原理是：两个变量记录左右节点，两边分别开始遍历。左边的节点遇到负值继续前进，遇到正值停止。右边的节点正好相反。 * 然后将左右节点的只进行交换，然后再开始遍历直至左右节点相遇。 * 这种方式的时间复杂度是O(n).空间复杂度为O(1)* @param a要排列数组* @param left左开始索引* @param right右开始索引*/public static void setParted1(int[] a, int left, int right) {if (left >= right || left == a.length || right == 0) {for (int i = 0; i < a.length; i++) {System.out.println(a[i]);}return;}while (a[left] < 0) {left++;}while (a[right] >= 0) {right--;}if (left >= right || left == a.length || right == 0) {for (int i = 0; i < a.length; i++) {System.out.print(a[i]+"\t");}System.out.println();return;}swap(a, left, right);left++;right--;setParted1(a, left, right);}private static void swap(int a[], int left, int right) {int temp = 0;temp = a[left];a[left] = a[right];a[right] = temp;}/*** 方式二*/public static void setParted(int[] a) {int temp = 0;int border = -1;for (int i = 0; i < a.length; i++) {if (a[i] < 0) {temp = a[i];a[i] = a[border + 1];a[border + 1] = temp;border++;}}for (int j = 0; j < a.length; j++) {System.out.print(a[j]+"\t");}System.out.println();}public static void main(String[] args) {int a[] = {1, 2, -1, -5, -6, 7, -7, -10 };int b[] = {8,7,-1,-2,-3,-9,-8,-7,2,3,9,8};setParted(a);setParted1(b,0,b.length-1);}
二. 栈
1.用栈计算后缀表达式
private static final char ADD = '+';private static final char SUB = '-';private static final char MUL = '*';private static final char DIV = '/';private static Stack<Integer> stack = new Stack<Integer>();/*** 后缀表达式就是：操作符位于两个操作数之后，后缀表达式的形式如下：<操作数><操作数><操作符>* 中缀表达式就是：操作符位于操作数之间。中缀表达式的形式如下：<操作数><操作符><操作数>*/public static int evaluate(String expr){// 将字符串分解,\s 匹配任何空白字符，包括空格、制表符、换页符等。String[] tokenizer = expr.split("\\s");// for(int i = 0;i<tokenizer.length;i++){String token = tokenizer[i].trim();if(isOperator(token)){// 判断是操作符，则出栈两个操作数int op2 = stack.pop().intValue();int op1 = stack.pop().intValue();char operator = token.charAt(0);stack.push(calc(operator,op1,op2));}else{stack.push(Integer.parseInt(token));}}return stack.pop();// 将最后的计算结果返回}private static Integer calc(char operation, int op1, int op2) {int result = 0;switch (operation) {case ADD:result = op1 + op2;break;case SUB:result = op1 - op2;break;case MUL:result = op1 * op2;break;case DIV:result = op1 / op2;break;}return result;}private static boolean isOperator(String token) {return (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/"));}public static void main(String[] args) {String expression = "3 2 2 * + 1 -";int result = evaluate(expression);System.out.println("计算结果为：" + result);}
2.对栈数据进行排序
//双栈排序public Stack<Integer> twoStackSort(Stack<Integer> s){Stack<Integer> stack = new Stack<Integer>();while(!s.isEmpty()){int tmp = s.pop();while(!stack.isEmpty() && stack.peek() > tmp){s.push(stack.pop());}stack.push(tmp);}return stack;}public static void main(String[] args) {Stack<Integer> stack = new Stack<Integer>();stack.push(5);stack.push(4);stack.push(7);stack.push(8);stack.push(6);stack.push(1);stack.push(9);stack.push(2);stack.push(3);Stack<Integer> stack2 = twoStackSort(stack);System.out.println(stack2);}
2.用栈来判断括号匹配问题
public static boolean isValidate(String s){Stack<Character> a = new Stack<Character>();for(int i = 0 ;i<s.length();i++){char c = s.charAt(i);if(c=='(')a.push(')');if(c=='[')a.push(']');if(c=='{')a.push('}');if(c == ')' || c == ']' || c == '}'){if(a.size()==0)return false;if(a.pop()!=c)return false;}}if(a.size()!=0)return false;return true;}public static void main(String[] args) {//判断括号匹配问题String s = "..(..(..[]..)..)";boolean a = isValidate(s);System.out.println(a);}
