귀속 에 관 한 세 가지 알고리즘 문제 의 총 결

1. 어떻게 재 귀 함수 와 스 택 으로 역 주 행 스 택 을 조작 합 니까?
한 창고 에 1, 2, 3, 4, 5 를 순서대로 넣 으 면 창고 꼭대기 에서 창고 밑 까지 각각 5, 4, 3, 2, 1 이다. 이 창 고 를 옮 긴 후에 창고 꼭대기 에서 창고 밑 까지 는 1, 2, 3, 4, 5 이다. 즉 창고 안의 원소 의 역순 을 실현 하지만 귀속 함수 로 만 실현 할 수 있 고 다른 데이터 구 조 를 사용 하지 않 아 도 된다.
우선, 재 귀 방법 을 어떻게 사용 하 는 지 보조 저장 소 를 사용 하지 않 고 스 택 의 기본 요 소 를 얻 을 수 있 는 지 생각 합 니 다.
4. 567913. 그 다음 에 물이 도랑 에 이 르 렀 다.

public static int getAndRemoveLast(Stack stack){
	int result = stack.pop();
	if(stack.isEmpty()){
		return result;
	}else{
		int last = getAndRemoveLast(Stack);
		stack.push(result);
		return last;
	}
}

2. 문자열 str 를 지정 합 니 다. str 는 표현 식 을 표시 합 니 다. 그 중에서 정수, 덧셈 기호 와 좌우 괄호 만 있 을 수 있 습 니 다. 공식 적 인 계산 결 과 를 되 돌려 줍 니 다. 예 를 들 어 str = "48 * (70 - 65) - 43) + 8 * 1", - 1816;str = "3 + 1 * 4", 7 로 돌아 가기;str = "3 + (1 * 4)", 반환 7
설명: 주어진 문자열 은 반드시 정확 한 표현 식 이 라 고 볼 수 있 습 니 다. 즉, str 에 대해 공식 적 인 유효성 검 사 를 할 필요 가 없습니다.만약 음수 라면 괄호 로 묶 어야 한다. 예 를 들 어 '4 * (- 3)' 이지 만 음수 가 공식 적 인 시작 이나 괄호 부분의 시작 이 라면 괄호 가 없 을 수 있다. 예 를 들 어 '- 3 * 4' 와 '(- 3 * 4)' 는 모두 합법적이다.계산 과정 이 넘 치 는 상황 을 고려 하지 않 는 다.

public static void reverse(Stack stack){
	if(stack.isEmpty()){
		return;
	}
	int i = getAndRemoveLast(stack);
	reverse(stack);
	stack.push;
}

3. 창 최대 값 배열 을 만 드 는 데 는 전체 배열 arr 와 w 크기 의 창 이 배열 의 맨 왼쪽 에서 맨 오른쪽 으로 미 끄 러 지고 창 이 오른쪽으로 미 끄 러 집 니 다.예 를 들 어 배열 은 {4, 3, 5, 4, 3, 3, 6, 7} 이 고 창 크기 는 3 일 때: [4 3 5] 4, 3, 6, 7 창 중 최대 치 는 5, 4 [3, 5 4] 3, 6, 7 창 중 최대 치 는 5, 4, 3 [5, 3] 3, 7 창 중 최대 치 는 5, 4, 3, 5, 3, 7 창 중 최대 치 는 4, 3, 5, 4, 5, 4, 4, 4, 3, 7 창 중 최대 치 는 6, 4, 3, 5, 4, 4, 3, 4, 4, 3, 3, 3, 7 창 중 최대 치 는 7 이 고 배열 길이 가 n 이면 창 크기 는 w,n - w + 1 개의 창의 최대 값 이 발생 합 니 다. 함 수 를 실현 하 십시오. 입력: 정형 배열 arr, 창 크기 는 w 출력 입 니 다. 길이 가 n - w + 1 인 배열 res, res [i] 는 각 창 상태 에서 의 최대 값 을 표시 합 니 다. 이 예 를 들 어 결 과 는 {5, 5, 5, 4, 6, 7} 입 니 다.

public static int getNum(LinkedList que){
	int res = 0;
	boolean add = true;
	String cur = null;
	int num = 0;
	while(!que.isEmpty()){
		cur = que.pollFirst();
		if(cur.equals("+")){
			add = true;
		}else if(cur.equals("-")){
			add = false;
		}else{
			num = Integer.valueOf(cur);
			res += add ? num : (-num);
		}
	}
	return res;
}
public static int getValue(String str){
	return value(str.toCharArray(), 0)[0];
}
public static void addNum(LinkedList que, int num){
	if(!que.isEmpty()){
		int cur = 0;
		String top = que.pollLast();
		if(top.equals("+") || top.equals("-")){
			que.addLast(top);
		}else{
			cur = Integer.valueOf(que.pollLast);
			num = top.equals("*") ? (cur * num) : (cur/num);
		}
	}
	que.addLast(String.valueOf(num));
}
public static int[] value(char[] str, int i){
	LinkedList que = new LinkedList();
	int pre = 0;
	int[] bra = null;
	while(i < str.length && str[i] != ')'){
		if(str[i] >= '0' && str[i] <= '9'){
			pre = pre * 10 + str[i++] - '0';
		}else if（str[i] != '('）{
			addNum(que, pre);
			que.addLast(String.valueOf(str[i++]));
			pre = 0;
		}else{
		//     
			bra = value(str, i + 1);
			pre = bra[0];
			i = bra[i] + 1;
		}
	}
	addNum(que,pre);
	return new int[] {getNum(que), i};
}