java - lintcode 계단 훈련 제6 장

llintcode 제6 장, 현재 lintcode 는 거의 이 장 만 닦 을 뻔 했 습 니 다...제7 장 은 두 문제 밖 에 없 는데 하 나 는 노드 공공 조상 들 의 문제 입 니 다. 저 는 나무의 알고리즘 을 복습 할 때 썼 습 니 다. 하 나 는 string 이 int 를 돌리 고 leetcode 는 이 문 제 를 풀 어서 다시 한 번 썼 을 뿐 입 니 다.제8 장 현재 한 문제 만 풀 었 다.
        6 장도 할 말 이 없 을 것 같 아서...이 문제 만 있 습 니 다. 검 지 offer 의 원 제 는 사전에 답 을 몰 랐 다 면 가장 좋 은 해 를 찾기 가 쉽 지 않 았 습 니 다.

  2*n + 1     ，                    ，      。

 문 제 는 별도의 공간 이 없다 는 것 이다. O (n) 의 시간 은 정말 미안 하 다. 처음에 나 는 풀 지 못 했 지만 이런 문 제 는 수영 과 같다. 만약 에 미리 만 났 다 면 나중에 다시 만 나 서 그 는 생각 이 어디 에 있 는 지 알 게 될 것 이다.
      사실은 매우 간단 하 다. 바로 하나 또는 하나의 특성 을 이용 한 것 이다.

a^b^a = b

     즉, 또는 산식 에서 두 개의 같은 숫자 는 서로 약속 할 수 있 고 코드 는 매우 간단 하 며 그의 원 리 를 본 사람 은 모두 할 수 있 을 것 이다.
      그런데 오늘 이 걸 봤 을 때 갑자기 또 다른 문제 가 생각 났 어 요. 두 개의 int 변수의 값 을 교환 하면 보통 상황 에서 저 는 이 렇 습 니 다.

int temp = a;
temp = a;
a = b;
b = temp;

 이렇게 쓰 는 것 은 분명 문제 가 없 을 것 입 니 다. 하지만 좀 낮 아 보 입 니 다. 그리고 면접 을 보면 면접 관 에 게 계속 물 어보 기 쉽 습 니 다. (공간 보다 많 지 않 아 도 될까요?)
      나중에 이렇게 썼어 요.

a = a + b;
b = a - b;
a = a - b;

 이것 은 이전 보다 조금 높 아 보인다.    판매 면접 때 면접 관 을 속 이 는 것 처럼 기술적 으로 면접 관 을 속 이 는 방법 이기 도 하 다.
     그리고 오늘 또 다른 방법 을 배 웠 습 니 다.

a = a ^ b;
b = a ^ b;
a = a ^ b;

        격 이 순식간에 한 단계 올 라 간 것 같 지 않 아 요?나 는 예전 의 블 로그 에서 int 형 데이터 계산 을 할 때 비트 연산 은 절대적 으로 신 기 를 설치 하 는 것 이 라 고 말 한 것 으로 기억한다.하지만 위의 세 가지 코드 가 사람 에 게 주 는 느낌 은 정말 다르다. 적어도 나 는 나의 첫 인상, 세 번 째 코드 를 쓴 사람 은 프로 그래 밍 이 앞의 두 가지 코드 보다 강하 고 면접 이 야. 첫 인상 이 중요 해.
 

public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a = 2;
		int b = 3;
		a = a ^ b;
		b = a ^ b;
		a = a ^ b;
		System.out.println(a);
		System.out.println(b);
	}

        결과:

3
2