면접 7: 빠 른 속도 지침 법 회전 링크 알고리즘 면접 (1)

면접 7: 면접 에서 흔히 볼 수 있 는 링크 알고리즘 지름길
링크 는 우리 데이터 구조 면접 에서 실수 하기 쉬 운 문제 이기 때문에 많은 면접 관 들 이 이 위 에서 공 을 들 이 는 것 을 좋아 합 니 다. 실 수 를 피하 기 위해 우 리 는 먼저 전면적 인 분석 을 하 는 것 이 좋 습 니 다.실제 소프트웨어 개발 주기 에 인 코딩 보다 디자인 시간 이 짧 지 않 습 니 다. 면접 을 볼 때 코드 를 급히 쓰 지 않 고 처음부터 자세히 분석 하고 디자인 하 는 것 이 면접 관 에 게 좋 은 인상 을 줄 것 입 니 다.
상처 투 성 이 코드 를 빨리 쓰 느 니 꼼꼼 히 분석 한 뒤 건장 하고 무적 인 프로그램 을 쓸 수 없다.
면접 문제: 단일 체인 표 의 끝 점 을 입력 하고 중간 요 소 를 되 돌려 줍 니 다.편 의 를 위해 원소 값 을 정형 으로 표시 하 다.
지원자 가 이 문 제 를 보 았 을 때 마음 이 미 친 듯 이 기뻐 서 어떻게 자신 에 게 이렇게 간단 한 문 제 를 만 났 습 니까?펜 을 들 면 쓰기 시작 합 니 다. 먼저 전체 링크 를 옮 겨 다 니 고 링크 의 길 이 를 가 져 옵 니 다. 다시 링크 를 옮 겨 다 니 며 len / 2 에 있 는 요 소 는 바로 링크 의 중간 요소 입 니 다.
그래서 이 문제 의 가장 중요 한 점 은 체인 시계의 길 이 를 얻 는 것 이다.그리고 이 len 을 받 는 것 도 간단 합 니 다. 옮 겨 다 니 기 전에 count 값 을 설정 해 야 합 니 다. 옮 겨 다 닐 때 count + + 는 첫 번 째 옮 겨 다 니 기 가 끝나 면 단일 체인 표 의 길이 len 을 받 을 수 있 습 니 다.
그래서 우 리 는 곧 이런 코드 를 썼 다.

public class Test15 {
    public static class LinkNode {
        int data;
        LinkNode next;

        public LinkNode(int data) {
            this.data = data;
        }
    }

    private static int getTheMid(LinkNode head) {
        int count = 0;
        LinkNode node = head;
        while (head != null) {
            head = head.next;
            count++;
        }
        for (int i = 0; i < count / 2; i++) {
            node = node.next;
        }
        return node.data;
    }

    public static void main(String[] args) {
        LinkNode head = new LinkNode(1);
        head.next = new LinkNode(2);
        head.next.next = new LinkNode(3);
        head.next.next.next = new LinkNode(4);
        head.next.next.next.next = new LinkNode(5);
        System.out.println(getTheMid(head));
    }
}

면접 관 이 이 코드 를 보 았 을 때, 그 는 우리 에 게 위의 코드 가 두 번 순환 되 었 다 고 말 했 지만, 그 가 기대 하 는 것 은 단 한 번 뿐 이 었 다.
그래서 우 리 는 머리 를 쥐 어 짜 서 인터넷 에서 소개 한 개념 인 빠 르 고 느 린 손가락 침 법 이 생각 났 다.
만약 에 우리 가 두 변 수 를 설정 하면 slow, fast 의 시작 은 모두 단일 체인 표 의 두 노드 를 가리 키 고 그 다음 에 순서대로 뒤로 이동 하 며 fast 의 이동 속 도 는 slow 의 2 배 이다.이렇게 하면 fast 가 끝 노드 를 가리 킬 때 slow 는 바로 한가운데 에 있다.
이 사고방식 을 분명히 생각 한 후에 우 리 는 곧 다음 과 같은 코드 를 쓸 수 있다.

public class Test15 {
    public static class LinkNode {
        int data;
        LinkNode next;

        public LinkNode(int data) {
            this.data = data;
        }
    }

    private static int getTheMid(LinkNode head) {
        LinkNode slow = head;
        LinkNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow.data;
    }

    public static void main(String[] args) {
        LinkNode head = new LinkNode(1);
        head.next = new LinkNode(2);
        head.next.next = new LinkNode(3);
        head.next.next.next = new LinkNode(4);
        head.next.next.next.next = new LinkNode(5);
        System.out.println(getTheMid(head));
    }
}

빠 르 고 느 린 지침 법 은 하 나 를 들 면 열 을 안다.
빠 르 고 느 린 지침 법 은 확실히 링크 류 면 시험 문제 에서 특히 유용 하 다. 우 리 는 여기 서 하 나 를 들 어 세 번 째 로 원 제 를 조금 수정 해도 사실은 실현 할 수 있다.
면접 문제: 단일 체인 시트 의 끝 점 을 정 하여 이 링크 가 순환 링크 인지 아 닌 지 를 판단 합 니 다.
앞의 문제 와 마찬가지 로 우 리 는 두 개의 변 수 를 slow, fast 로 정의 해 야 합 니 다. 동시에 링크 의 머리 노드 에서 출발 하여 fast 는 링크 를 걸 을 때마다 slow 는 한 걸음 만 걸 어야 합 니 다.빠 른 지침 이 느 린 지침 을 따라 잡 으 면 링크 는 링 (순환) 링크 다.빠 른 지침 이 링크 의 끝 (fast. next 가 null 을 가리 키 는) 까지 걸 어가 도 느 린 지침 을 따라 잡지 못 하면 링크 는 링 링크 가 아 닙 니 다.
이런 생각 이 들 어서 코드 를 실현 하 는 것 은 아직 분 의 일이 아니다.

public class Test15 {
    public static class LinkNode {
        int data;
        LinkNode next;

        public LinkNode(int data) {
            this.data = data;
        }
    }

    private static boolean isRingLink(LinkNode head) {
        LinkNode slow = head;
        LinkNode fast = head;
        while (slow != null && fast != null && fast.next != null) {
            if (slow == fast || fast.next == slow) {
                return true;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        return false;
    }

    public static void main(String[] args) {
        LinkNode head = new LinkNode(1);
        head.next = new LinkNode(2);
        head.next.next = new LinkNode(3);
        head.next.next.next = new LinkNode(4);
        head.next.next.next.next = new LinkNode(5);
        System.out.println(isRingLink(head));
        head.next.next.next.next.next = head;
        System.out.println(isRingLink(head));
    }
}

정말 재 미 있 습 니 다. 빠 르 고 느 린 손가락 침 법 은 다시 한 번 그것 의 장점 을 이용 하여 우리 의 문 제 를 교묘 하 게 해결 하 였 습 니 다.
쾌속 지 침 법의 연장
우리 가 위 에서 설명 한 '빠 르 고 느 린 손가락 침 법' 은 모두 하나의 변수 가 1 걸음 을 걷 고 하나의 변 수 는 n 걸음 을 걷는다.우 리 는 사실 그것 을 확장 할 수 있다.이 '속도' 는 반드시 동시에 옮 겨 다 녀 야 한 다 는 것 이 아니다.
예 를 들 어 에서 15 번 째 면접 문 제 는 '빠 르 고 느 린 손가락 침 법' 의 연장 에 활용 되 었 다.
면접 문제: 단일 체인 시트 의 끝 점 을 입력 하고 이 링크 의 마지막 k 번 째 노드 의 값 을 출력 합 니 다.
처음에 이것 을 보 니 우리 가 앞에서 배 운 '빠 르 고 느 린 손가락 침 법' 에 대한 고찰 이 아 닌 것 같다.그래서 대부분의 사람들 은 헷 갈 리 고 정규 화 된 사고 에 들어간다.여전히 전체 변수 count 를 설정 하고 순환 할 때마다 count + + 링크 의 길이 n 을 가 져 옵 니 다.그럼 마지막 k 번 째 노드 는 바로 순위 n - k + 1 번 째 노드 입 니 다.그래서 우 리 는 길이 n 을 받 은 후에 n - k + 1 번 순환 을 하면 이 마지막 k 번 째 노드 의 값 을 얻 을 수 있다.
그러나 면접 관 은 이 비대 한 해법 에 만족 하지 않 을 것 이 분명 하 다. 그 는 여전히 우리 가 한 번 순환 하면 이 일 을 해결 할 수 있 기 를 바란다.
링크 를 한 번 만 옮 겨 다 니 면 마지막 k 번 째 노드 를 찾 을 수 있 도록 슬 로 우 와 fast 를 정의 할 수 있 습 니 다.fast 변 수 를 k - 1 단계 로 옮 겨 다 니 게 합 니 다. slow 는 움 직 이지 않 습 니 다.k 단계 부터 slow 변수 도 fast 변 수 를 따라 링크 의 머리 노드 부터 옮 겨 다 닙 니 다.두 변수 가 가리 키 는 결점 거 리 는 항상 k - 1 로 유지 되 기 때문에 fast 변수 가 링크 의 끝 점 에 도 착 했 을 때 slow 변수 가 가리 키 는 결점 은 바로 우리 가 필요 로 하 는 마지막 k 번 째 결점 이다.
우 리 는 여전히 마음속 으로 코드 를 묵인 할 수 있다.

입력 한 링크 는 1 - > 2 - > 3 - > 4 - > 5 라 고 가정 합 니 다.

지금 우 리 는 마지막 세 번 째 결점 의 값, 즉 세 번 째 결점 의 값 을 요구한다. 그것 의 값 은 3 이다.

두 변 수 를 slow, fast 로 정의 하 는데 모두 노드 1 을 가리킨다.

먼저 fast 를 앞으로 가게 합 니 다. k - 1 즉 2 보 입 니 다. 이때 fast 는 세 번 째 결점 을 가리 키 는데 그 값 은 3 입 니 다.

현재 fast 와 slow 가 동시에 오른쪽으로 이동 합 니 다.

fast 는 2 보 를 더 지나 링크 의 끝 점 에 도착 했다.fast 가 마침 세 번 째 결점 을 가 리 켰 는데, 이것 은 분명히 우리 의 추측 에 부합 되 는 것 이다.

마음속 으로 코드 를 한 번 묵인 한 후에 우 리 는 분명히 아래 의 코드 를 쓰기 쉽다.

public class Test15 {
    public static class LinkNode {
        int data;
        LinkNode next;

        public LinkNode(int data) {
            this.data = data;
        }
    }

    private static int getSpecifiedNodeReverse(LinkNode head, int k) {
        LinkNode slow = head;
        LinkNode fast = head;
        if (fast == null) {
            throw new RuntimeException("your linkNode is null");
        }
        //    fast    k-1  
        for (int i = 0; i < k - 1; i++) {
            if (fast.next == null) {
                //       k          ，    
                throw new RuntimeException("the value k is too large.");
            }
            fast = fast.next;

        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow.data;
    }

    public static void main(String[] args) {
        LinkNode head = new LinkNode(1);
        head.next = new LinkNode(2);
        head.next.next = new LinkNode(3);
        head.next.next.next = new LinkNode(4);
        head.next.next.next.next = new LinkNode(5);
        System.out.println(getSpecifiedNodeReverse(head, 3));
        System.out.println(getSpecifiedNodeReverse(null, 1));
    }
}

총결산
링크 유형 시험 문 제 는 정말 다양 하 게 풀 수 있 습 니 다. 우리 가 하나의 변수 로 링크 를 옮 겨 다 니 며 문 제 를 해결 하지 못 할 때 우 리 는 두 개의 변수 로 링크 를 옮 겨 다 닐 수 있 습 니 다. 그 중의 한 변 수 를 옮 겨 다 니 는 속도 가 빠 를 수 있 습 니 다. 예 를 들 어 한 번 에 두 걸음 을 걷 거나 몇 걸음 을 걸 을 수 있 습 니 다.우 리 는 이런 면접 을 만 났 을 때 절대로 스스로 혼란 을 일 으 키 지 말고 이성적으로 문 제 를 분석 하 는 것 을 배 워 야 한다.
내 동료 들 에 게 작별 인 사 를 하려 고 했 는데, 모두 가 아직 진정한 능력 을 배우 지 못 할 까 봐 여기 서 확장 문 제 를 하나 더 남 겼 다.
면접 문제: 단일 체인 표 의 끝 점 을 정 하고 마지막 k 번 째 끝 점 을 삭제 합 니 다.
하하, 위의 제목 과 함께 얻 은 값 을 삭제 하 는 것 뿐 입 니 다. 많은 친구 들 이 몰래 즐 겼 을 것 입 니 다. 하지만 남 진 은 먼저 여러분 에 게 너무 자만 하지 말 라 고 일 깨 워 주 었 습 니 다.
그래, 우리 내일 다시 만 나 자 ~