JAVA 프로그래머 가 반드시 파악 해 야 할 데이터 구조의 면접 문제 (정 답 첨부)
59853 단어 데이터 구조 면접 문제
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);
else
map.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);
}
대열
좋은 웹페이지 즐겨찾기
