황소고집!한 줄 의 코드 가 나 를 한참 동안 괴 롭 혔 던 알고리즘 문 제 를 이렇게 많이 해결 할 수 있다 니.

설 연 휴가 이렇게 긴 데 뭘 하 는 게 제일 좋아요?물론 알고리즘 문 제 를 괴 롭 혔 습 니 다. 다음 에 한 줄 의 코드 로 해결 할 수 있 는 알고리즘 문 제 를 몇 개 알려 드 리 겠 습 니 다. 물론 저 는 이런 알고리즘 문 제 를 모두 풀 었 다 고 믿 습 니 다. 하지만 해 봤 더 라 도 한 방울 볼 수 있 습 니 다. 왜냐하면 처음에 한 줄 의 코드 로 해결 한 것 이 아니 었 기 때 문 입 니 다.
코드 해결 을 배 웠 는데 면접 관 이 물 어보 면 엄 살 을 부 릴 수 있어 요.
1, 2 의 멱 차방
문제 설명: 정수 n 이 2 인지 아 닌 지 를 판단 하 는 차방
이 문제 에 대해 일반적인 조작 은 이 수 를 2 로 나 눈 다음 에 n 이 1 로 나 눌 때 까지 나머지 가 있 는 지 판단 하 는 것 이다.
n 을 2 진법 으로 나 누 어 처리 할 수 있 습 니 다. n 이 2 의 멱 차방 이 라면 n 의 2 진수 의 최고 위 는 1 이 고 뒤의 것 은 0 입 니 다. 예 를 들 어 16 이라는 숫자 에 대해 서 는 2 진법 이 10000 이 라 고 표시 합 니 다.
우리 가 그것 을 1 로 줄 이면 최고 위 는 0 이 되 고 나머지 는 모두 1 이 된다. 예 를 들 어 10000 - 1 = 01111 이다.
그 다음 에 우 리 는 n 과 (n - 1) 을 조작 하면 결 과 는 0 이다. 예 를 들 어 (n 이 16 이 라 고 가정)
n & (n-1) = 10000 & （10000 - 1) = 10000 & 01111 = 0
즉, n 이 2 의 멱 차방 이 라면 n & (n - 1) 의 결 과 는 0 이 고 그렇지 않 으 면 그렇지 않 기 때문에 코드 는 다음 과 같다.

int isPow(n){
    return (n & (n - 1)) == 0;
}

2. 한 줄 코드 로 전형 적 인 조세 프 링 을 해결 합 니 다.
조세 프 링 문 제 는 여러분 들 이 대학교 1 학년 2 학년 때 접촉 하 셨 을 거 라 고 믿 습 니 다. 많은 사람들 이 링 링크 의 응용 으로 가 져 올 것 입 니 다. 그러나 링 링크 는 가장 좋 은 해결 방법 이 아 닙 니 다. 오늘 저 는 한 줄 의 코드 로 그것 을 해 치 웠 고 거의 최 적 화 된 것 이 라 고 할 수 있 습 니 다.
어떤 사람 이 이 문 제 를 잊 어 버 린 것 을 감안 하여 나 는 이 문제 의 묘 사 를 좀 붙 이 는 것 이 좋 겠 다.
문제 설명: 번호 가 1 - N 인 N 명의 병사 가 둘 러 앉 아 원 을 만 들 고 번호 가 1 인 병사 부터 순서대로 번호 (1, 2, 3. 이렇게 순서대로 보고) 를 매기 면 m 까지 세 는 병사 가 죽 어 나 가 고 그 다음 에 병사 가 1 부터 번 호 를 매기 기 시작한다. 마지막 에 남 은 병사 가 이 병사 의 번 호 를 구한다.
먼저 코드 를 주 고 뒤에 설명 하 세 요.

int f(int n, int m){
    return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
}

원 리 는 이렇다.
만약 우리 가 병 사 를 삭제 한 후에 이 병사 들 에 게 다시 번 호 를 준다 면, 삭제 전과 삭제 후, 이 번호 들 은 어떤 수학 관계 가 존재 하 므 로, 우 리 는 이 관 계 를 찾아내 기만 하면 된다.
우 리 는 재 귀 함수 f (n, m) 의 반환 결 과 를 생존 병사 의 번호 로 정의 합 니 다. 분명히 n = 1 시, f (n, m) = 1. 만약 우리 가 f (n, m) 와 f (n - 1, m) 간 의 관 계 를 찾 을 수 있다 면 우 리 는 재 귀 방식 으로 해결 할 수 있 습 니 다. 우 리 는 인원 수가 n 이 라 고 가정 하고 m 에 신고 한 사람 은 자살 합 니 다. 그러면 처음에 번 호 는 n 이 었 습 니 다.
… 1 … m - 2
m - 1
m
m + 1
m + 2 … n …
한 번 삭제 한 후에 m 로 번 호 를 매 긴 노드 를 삭 제 했 습 니 다. 삭제 한 후에 n - 1 개의 노드 만 남 았 습 니 다. 삭제 전과 삭제 후의 번 호 는 다음 과 같 습 니 다.
삭제 전 --- 삭제 후
… --- …
m - 2 --- n - 2
m - 1 --- n - 1
m --- - 없 음 (번호 가 삭제 되 었 기 때 문)
m + 1 --- 1 (다음 부 터 는 여기 서 번 호 를 매기 기 때문이다)
m + 2 ---- 2
… ---- …
새 링 에는 n - 1 개의 노드 만 있 습 니 다. 또한 이전 번 호 는 m + 1, m + 2, m + 3 의 노드 를 삭제 하면 삭제 후 번호 가 1, 2, 3 의 노드 가 됩 니 다.
old 가 이전의 노드 번 호 를 삭제 하기 위해 new 가 한 노드 뒤의 번 호 를 삭제 하기 위해 old 와 new 간 의 관 계 는 old = (new + m - 1)% n + 1 이다.
이렇게 하면 우 리 는 f (n, m) 와 f (n - 1, m) 간 의 관 계 를 얻 을 수 있 고 f (1, m) = 1. 그래서 우 리 는 재 귀적 인 방식 으로 할 수 있다. 코드 는 다음 과 같다.
주: 어떤 사람들 은 왜 old = (new + m)% n 이 아니 냐 고 의심 할 수 있 습 니 다. 주로 번호 가 0 에서 시작 되 는 것 이 아니 라 1 에서 시작 되 기 때 문 입 니 다. new + m = = n 이 라면 마지막 계산 결 과 는 old = 0 이 될 수 있 습 니 다. 그래서 old = (new + m - 1)% n + 1.

int f(int n, int m){
    if(n == 1)   return n;
    return (f(n - 1, m) + m - 1) % n + 1;
}

왜 한 줄 이 아니 라 두 줄 입 니까? 만약 당신 이 자주 문 제 를 풀 면 자신의 코드 가 짧 아 보일 수록 프로필 이 좋아 지 기 를 바 랄 것 입 니 다. 더 이해 하기 어 려 울 까요? 제 가 게 으 른 이 치 는 다음 과 같 습 니 다.

int f(int n, int m){
    return n == 1 ? n : (f(n - 1, m) + m - 1) % n + 1;
}

물론, 나 는 이전에 글 을 한 편 쓴 적 이 있다. 세 가지 방법 으로 조세 프 링 을 해결 했다. 관심 있 는 것 도 볼 수 있다. 아 리 펜 시험 문 제 를 기억 하 자. 내 가 조세 프 링 문 제 를 어떻게 한 줄 코드 로 해결 하 는 지.
한 번 밖 에 안 나 와 요. 숫자 예요.
문제 설명: 전체 배열 을 드 리 겠 습 니 다. 배열 중 하 나 는 한 번 밖 에 나타 나 지 않 았 고 다른 수 는 두 번 나 타 났 습 니 다. 이것 은 한 번 밖 에 나타 나 지 않 은 수 를 구 합 니 다.
이 문 제 는 많은 사람들 이 하나의 해시 표 로 저장 할 수 있 습 니 다. 저장 할 때마다 특정한 숫자 가 나타 난 횟수 를 기록 하고 마지막 으로 해시 표를 옮 겨 다 니 며 어느 숫자 가 한 번 밖 에 나타 나 지 않 았 는 지 보 세 요. 이런 방법의 시간 복잡 도 는 O (n) 이 고 공간 복잡 도 는 O (n) 입 니 다.
그러나 이 문 제 는 사실 이 또는 연산 으로 해결 할 수 있다. 두 개의 똑 같은 수의 이 또는 결 과 는 0 이 고 한 개의 수 와 0 의 이 또는 결 과 는 그 자체 이 며 이 또는 연산 은 교환 율 을 지원 한다. 이런 특징 을 바탕 으로 우 리 는 이 그룹의 정형 을 모두 이 또는 한 번 만 바 꾸 면 된다. 마지막 결 과 는 우리 가 찾 아야 할 숫자 이다.
예 를 들 어 이 조 의 데 이 터 는 1, 2, 3, 4, 5, 1, 2, 3, 4 이다. 그 중에서 5 개 는 한 번 만 나 타 났 고 다른 것 은 두 번 나 타 났 다. 그들 을 모두 다른 것 으로 만 들 었 다. 결 과 는 다음 과 같다.
교환 율 과 결합 율 이 다 르 거나 지지 하기 때문에:
1^2^3^4^5^1^2^3^4 = （1^1)^(2^2)^(3^3)^(4^4)^5= 0^0^0^0^5 = 5。
이런 방법 을 통 해 공간의 복잡 도 를 O (1) 로 낮 출 수 있 고 시간 복잡 도 는 변 하지 않 으 며 해당 하 는 코드 는 다음 과 같다.

int find(int[] arr){
    int tmp = arr[0];
    for(int i = 1;i < arr.length; i++){
        tmp = tmp ^ arr[i];
    }
    return tmp;
}

약속 한 코드 는 요?
이것 은 당신 에 게 먼저 보 여 주 려 고 하 는 것 이 아 닙 니까? 코드 솔 루 션 은 다음 과 같 습 니 다.

//            ，        i     1，   result    arr[0]
//   find(arr, 1, arr[0])
int find(int[] arr,int i, int result){
    return arr.length <= i ? result : find(arr, i + 1, result ^ arr[i]);
}

솔직히 말 해서 이 문 제 는 코드 를 한 줄 사용 한 후에 더욱 복잡 해 졌 다.
4. n 의 계승
문제 설명: 정수 N 을 정 하면 N 의 곱 하기 N! 끝 에 0 이 몇 개 있 습 니까? 예 를 들 어 N = 10 이면 N! = 3628800, 그러면 N! 끝 에 0 이 두 개 있 습 니 다.
제 가 먼저 코드 를 드 려 서 여러분 께 맛 보 게 하고 자세히 설명 하 겠 습 니 다.

int f(n){
    return n == 0 ? 0 : n / 5 + f(n / 5);
}

이 문제 에 대해 일반적인 조작 은 N! 의 값 을 10 으로 나 누 어 몇 개의 0 을 판단 하 는 것 입 니 다. 그러나 이렇게 하면 반드시 넘 치 는 문제 가 발생 할 것 입 니 다. 그리고 시간 이 복잡 하기 때문에 우 리 는 다른 사고 에서 시작 하 는 것 도 좋 습 니 다. 한 숫자 에 10 을 곱 하면 반드시 끝 에 0 이 생 길 것 입 니 다. 그러면 우 리 는 어떤 숫자 를 곱 하면 10 을 얻 을 수 있 습 니까?
답 은 가능 하 며 2 * 5 만 10 이 생 긴 다.
주의 하 세 요. 4 * 5 = 20 도 0 이 생 길 수 있 습 니 다. 하지만 우 리 는 20 을 분해 할 수 있 습 니 다. 20 = 10 * 2.
그래서 문 제 는 N 으로 바 뀌 었 습 니 다! 종 류 는 몇 대 2 * 5 로 분 해 될 수 있 는 지 다시 한 번 분석 해 보면 N! 에서 2 로 정 제 될 수 있 는 수 는 5 로 정 제 될 수 있 는 수 보다 많 습 니 다. 그래서 문 제 는 1. n. 이 n 개 수 에서 5 로 정 제 될 수 있 는 수 는 몇 개 입 니까?
주의 하 세 요. 25 는 5 로 두 번 나 눌 수 있 기 때문에 25 는 2 대 2 * 5 방울 을 만 들 수 있 습 니 다. 이런 생각 이 들 었 습 니 다. 코드 는 다음 과 같 습 니 다.

int f(int n){
    int sum = 0;
    for(int i = 1; i <= n; i++){
        int j = i;
        while(j % 5 == 0){
            sum++;
            j = j / 5;
        }
    }
    return sum;
}

그러나 좀 더 분해 하면 우 리 는 발견 할 수 있다.
N = 20 일 때 1 ~ 20 에 몇 개의 5 가 생 길 수 있 습 니까? 답 은 4 개 입 니 다. 이때 N / 5 = 4 가 있 습 니 다.
N = 24 일 때 1 ~ 24 는 몇 개의 5 를 만 들 수 있 습 니까? 답 은 4 개 입 니 다. 이때 N / 5 = 4 가 있 습 니 다.
N = 25 일 때 1 ~ 25 에 몇 개의 5 가 생 길 수 있 습 니까? 답 은 6 개 입 니 다. 주로 25 가 두 개의 5 를 기 여 했 기 때 문 입 니 다. 이때 N / 5 + N / 5 ^ 2 = 6 이 있 습 니 다.
…
5 가 생 긴 개 수 는 sum = N / 5 + N / 5 ^ 2 + N / 5 ^ 3 +... 을 발견 할 수 있 습 니 다.
그래서 코드 한 줄 로 해결 할 수 있 습 니 다.

int f(n){
    return n == 0 ? 0 : n / 5 + f(n / 5);
}

총결산
어떤 나무 가 대단 하 다 고 생각 합 니까? 나중에 면접 관 이 당신 에 게 이 문제 들 을 물 으 면 이 코드 를 그 에 게 던 져 주세요!!
물론 계속 압박 을 유지 하려 면 알고리즘 책 을 좀 더 읽 어야 한다. 나 도 좀 정리 했다.
여기 서 모두 에 게 공헌 하 는 것 은 모두 볼 만 한 산법 책 이다.
여러분 은 제 위 챗 공식 번호 인 '멋 있 게 프로 그래 밍 하기' 에서 '알고리즘 을 배우 고 싶 습 니 다' 를 얻 고 다운로드 링크 를 얻 을 수 있 습 니 다.
철 아, 좋아요 누 르 고 갈 까?
1. 저 에 게 칭찬 을 해 주세요. 더 많은 사람들 이 이 글 을 볼 수 있 고 격려 도 해 주세요. 히히.
2. 노 철 들 은 제 오리지널 위 챗 공식 번호 인 '멋 있 게 프로 그래 밍 하기' 에 관심 을 가지 고 알고리즘 + 컴퓨터 기초 지식 (컴퓨터 네트워크 + 운영 체제 + 데이터 베이스 + Linux) 에 전념 합 니 다.
저장 은 당신 에 게 보고 얻 은 것 이 있 습 니 다. 당신 이 나 를 때 리 는 것 을 믿 지 않 습 니 다. 배경 에 "전자 책" 이 라 고 대답 하면 정선 전자 책 큰 선물 을 드 립 니 다. 각종 기능 을 포함 한 양질 의 전자 책 을 드 립 니 다.
작자 가 간결 하 다
저자: 안녕하세요, 저 는 멋 진 곳 입 니 다. 대학, 학교 에서 길 을 걸 어 왔 습 니 다. 알고리즘, 컴퓨터 기초 지식의 중요성 을 잘 알 고 있 습 니 다. 그래서 마이크로 스타 공식 번호 인 '멋 있 게 프로 그래 밍' 을 신 청 했 습 니 다. 이런 기본 지식 을 쓰 고 우리 의 내공 을 향상 시 키 는 것 을 전문 으로 합 니 다. 멋 있 게 당신 의 관심 을 기대 하고 저 와 함께 공부 하 겠 습 니 다.