C++를 바탕 으로 조세 프 링 문 제 를 실현 하 는 세 가지 해법 을 상세히 설명 하 다.

머리말
무엇이 조세 프 링 문제 입 니까?
조세 프 링 문 제 는 서로 다른 플랫폼 에서'최적화'에 의 해 묘사 되 는 것 이 다르다.예 를 들 어 소 객 검 지 는 offer 가 아이들 을 부 르 는 게임,그리고 살인 게임 이 라 고 부 르 고 출석 을 부 르 는 것 이다.가장 직접적인 느낌 은 검 지 offer 62 의 설명 이다동그라미 의 마지막 남 은 숫자.
질문 설명:
0,1......................................................................................이 동그라미 안에 남 은 마지막 숫자 를 구하 세 요.
예 를 들 어 0,1,2,3,4 라 는 5 개의 숫자 가 하나의 원 을 이 루 고 숫자 0 부터 매번 세 번 째 숫자 를 삭제 하면 삭제 되 는 앞의 4 개의 숫자 가 2,0,4,1 순 이 므 로 마지막 에 남 은 숫자 는 3 이다.
물론 여기 서 m,n 은 모두 정상 적 인 데이터 범위 이 고 그 중에서

1 <= n <= 10^5

1 <= m <= 10^6

이 문제 에 대해 당신 은 어 렸 을 때 마을 의 한 무리의 아이들 이 함께 앉 아 있 었 다 는 인상 을 받 았 을 것 입 니 다.어떤 것 부터 번 호 를 매기 고 몇 줄 까지 세 었 다가 다음 것 은 마지막 까지 다시 시작 하 겠 습 니 다.
2.순환 링크 시 뮬 레이 션
이 문제 의 가장 본질 적 인 것 은 바로 순환 링크 의 문제 이다.원 을 둘 러 싼 후에 끝 이 없다.이것 이 바로 전형 적 인 순환 링크 잖 아!하나의 순서 로 번 호 를 매 기 는 것 은 바로 링크 의 매 거 진 것 이 잖 아!대응 하 는 숫자의 열 을 세 는 것 은 순환 링크 의 삭제 가 아 닙 니까?

그리고 이곳 에는 매우 편리 한 곳 이 있다.

순환 링크 의 아래로 매 거 진 것 은 머리 와 꼬리 문 제 를 고려 할 필요 가 없고 직접 node=node.next 에서 아래로

순환 대화 표 의 삭제 도 두미 문 제 를 고려 하지 않 고 node.next=node.next.next 에서 삭제 합 니 다

물론 주의해 야 할 부분도 있 습 니 다.
4.567917.링 링크 를 형성 하 는 것 은 매우 간단 하 다.일반 링크 의 마지막 노드 인 next 를 첫 번 째 노드 로 가리 키 면 된다

순환 링크 에서 한 노드 만 있 을 때 되 돌아 오지 않 습 니 다.즉,node.next=node 일 때

4.567917.삭제 하려 면 삭제 할 앞의 노드 를 찾 아야 합 니 다.그래서 우 리 는 계 수 를 삭제 할 때 한 자리 가 적 고 앞의 노드 를 이용 하여 뒤의 노드 를 직접 삭제 하면 됩 니 다이렇게 하면 사고방식 이 명확 하고 코드 를 직접 훑 어 본다.

class Solution {
    class node//    
    {
        int val;
        public node(int value) {
            this.val=value;
        }
        node next;
    }
    public int lastRemaining(int n, int m) {
        if(m==1)return n-1;//              
        node head=new node(0);
        node team=head;//      
        for(int i=1;i<n;i++)
        {
            team.next=new node(i);
            team=team.next;
        }
        team.next=head;//    
        int index=0;// 0    
        while (head.next!=head) {//            
            //  index=m-2         (m-1)    
            if(index==m-2)
            {
                head.next=head.next.next;
                index=0;
            }
            else {
                index++;
            }
            head=head.next;
        }
        return head.val;
    }
}

물론 이런 알고리즘 은 너무 복잡 해서 대부분의 OJ 를 제출 하면 AC 를 할 수 없습니다.시간 초과 가 너무 심각 하기 때문에 구체 적 인 것 은 다음 과 같이 분석 할 수 있 습 니 다.
3.질서 있 는 집합 시 뮬 레이 션
위 에서 링크 를 사용 하여 게임 과정 을 직접 모 의 하면 매우 심각 하고 심각 한 시간 초과,n 개의 숫자 를 사용 하여 m 번 째 로 배열 할 수 있 습 니 다.m 가 m 보다 훨씬 크 면 여러 차례 원 을 돌 기 때문이다.

그래서 우 리 는 잉여 를 구 하 는 방법 으로 등가 의 가장 낮은 매 거 횟수 를 판단 한 다음 에 이 를 삭제 하면 된다.여기 서 너 는 계속 자체 체인 표를 사용 하여 시 뮬 레이 션 을 할 수 있다.위의 while 순환 과 위 에 기록 길이 의 매번 잉여 계산 권 수 를 추가 하면 된다.

int len=n;
while (head.next!=head) {
  if(index==(m-2)%len)
  {
    head.next=head.next.next;
    index=0;
    len--;
  }
  else {
    index++;
  }
  head=head.next;
}

그러나 우 리 는 수 동 으로 링크 시 뮬 레이 션 을 쓰 지 않 을 때 가 많 습 니 다.우 리 는 Array List 와 LinkedList 를 통 해 시 뮬 레이 션 을 할 것 입 니 다.만약 에 LinkedList 를 사용 하면 그 밑 에 있 는 데이터 구 조 는 배열 입 니 다.하지만 List 를 사용 하고 있 습 니 다.코드 방법 이 일치 합 니 다.
List 는 길 이 를 직접 알 수 있 고 요 소 를 삭제 할 수 있 습 니 다.List 를 사용 하 는 어 려 운 점 은 순서 표 입 니 다.어떻게 순환 링크 를 모 의 합 니까?
우 리 는 곰 곰 이 생각 합 니 다.현재 길이 가 n 이 라 고 가정 하고 m 번 째(위의 분석 을 통 해 이 효과 적 인 m 가 n 보다 크 지 않도록 할 수 있 습 니 다)를 삭제 하고 index 위치 에서 삭제 합 니 다.그러면 삭제 후 남 은 것 은 n-1 길이 입 니 다.index 위 치 는 첫 번 째 계수 의 위 치 를 나타 내 는 것 입 니 다.우 리 는 나머지 를 통 해 다음 삭제 에 몇 걸음 이 필요 한 지 알 수 있 습 니 다.그러면 다음 위 치 는 어떻게 확정 합 니까?

너 는 걷 는 횟수 가 경 계 를 넘 었 는 지 분류 해서 토론 할 수 있 지만,여기 에는 더욱 교묘 한 방법 이 있다.다음 구체 적 인 위 치 를 직접 구 할 수 있다.공식 은 다음 과 같다.

index=(index+m-1)%(list.size());

index 는 1 계수 이기 때문에 순환 한 다음 에 m-1 개 를 앞으로 가면 진정한 위치 입 니 다.그러나 여기 서 먼저 이 질서 있 는 집합 길 이 를 몇 배 확대 한 다음 에 index 계수 부터 순환 하지 않 는 위 치 를 찾 을 수 있 습 니 다 index 2.마지막 으로 우 리 는 이 위치 index 2%(집합 길이)를 진정한 길이 로 가정 할 수 있 습 니 다.

이 공식 을 사용 하면 일거에 몇 개 를 얻 을 수 있 고 위의 m 가 너무 큰 순환 과 다 한 상황 을 해결 할 수 있 을 뿐만 아니 라 진실 한 위 치 를 찾 을 수 있다.바로 이 고 리 를 선형 으로 가정 한 다음 에 진짜 위 치 를 찾 는 것 이다.이해 하지 못 하면 이 그림 을 다시 볼 수 있다.

이런 경우 대부분의 OJ 는 겨우 통과 할 수 있 고 면접 관 의 차원 도 확률 이 많 지 않 습 니 다.구체 적 인 코드 는 다음 과 같 습 니 다.

class Solution {
    public int lastRemaining(int n, int m) {
        if(m==1)
            return n-1;
        List<Integer>list=new ArrayList<>();
        for(int i=0;i<n;i++)
        {
            list.add(i);
        }
        int index=0;
        while (list.size()>1)
        {
            index=(index+m-1)%(list.size());
            list.remove(index);
        }
        return list.get(0);
    }
}

4.귀속 공식 해결
우 리 는 위의 최적화 과정 을 돌 이 켜 보면 위 에서 잉여 를 구하 면 m 가 n 보다 훨씬 큰 상황 을 해결 할 수 있다(즉,이론 적 으로 많은 원 을 돌려 야 하 는 상황).그러나 n 자체 가 큰 경우 도 있 을 수 있 습 니 다.순서 표 Array List 든 링크 드 List 든 자주 조회 하고 삭제 하 는 것 은 비효 율 적 입 니 다.
그래서 똑똑 한 사람 은 데이터 에서 규칙 이나 관 계 를 찾기 시작한다.
먼저 공식 을 던진다.
f(n,m)=(f(n-1,m)+m)%n
f(n,m)는 n 개인 을 가리 키 며,m 번 호 를 보고 하여 최종 번 호 를 나열 한다.
다음은 나의 분석 과정 을 진지 하 게 살 펴 봐 야 한다.
우 리 는 예 를 들 어 4.567914.10 개의 숫자 가 있 는데 m 가 3 이 라 고 가정 하면 마지막 결 과 는 f(10,3)로 먼저 기록 할 수 있다.설령 우리 가 그것 이 얼마 인지 모 르 더 라 도.
처음 진행 할 때 요 소 를 찾 았 습 니 다0 1 2 3 4 5 6 7 8 9삭 제 했 습 니 다.이때 9 개의 요소 가 남 았 지만 시작 위 치 는 요소 3 이 되 었 습 니 다.등가 성2이 9 개의 숫자 를 다시 쓰기 시작 했다.

이때 이 서열 의 마지막 남 은 값 은 f(10,3)이다.이 서열 의 값 은 f(9,3)와 다 르 지만 모두 9 개의 수 이 고 m 는 3 이기 때문에 삭제 위 치 는 같다.즉,알고리즘 은 대체적으로 절차 가 일치 하지만 각 위치의 숫자 만 다르다.그래서 우리 가 해 야 할 일 은 이 서열 에 f(9,3)값 과 관련 이 있 는 지 찾 아 보 는 것 이다.
찾 는 과정 에서 두 가 지 를 잊 지 마 세 요.먼저%기 호 를 통 해 숫자 를 효과적으로 확장 할 수 있 습 니 다.즉,우 리 는 4,567914.이 서열 을(3,4,5,6,7,8,9,10,11)%10 으로 볼 수 있 습 니 다.여기 의 10 은 바로 이때 의 n 수치 입 니 다.
또한 수치 가 연속 이 라면 최종 결 과 는 연락 처 를 찾 을 수 있 습 니 다(차 이 는 맞 춤 형 입 니 다).그래서 우 리 는 f(10,3)와 f(9,3)값 간 의 결과 관 계 를 찾 을 수 있 고 다음 그림 을 볼 수 있다.

그래서 f(10,3)의 결 과 는 f(9,3)의 표현 으로 바 뀔 수 있 고 뒤에 도 마찬가지 이다.
f(10,3)=(f(9,3)+3)%10
f(9,3)=(f(8,3)+3)%9
……
f(2,3)=(f(1,3)+3)%2
f(1,3)=0
이렇게 하면 우 리 는 시 뮬 레이 션 을 하지 않 고 수치 적 인 관계 에서 전달 하 는 관 계 를 직접 찾 을 수 있 고 코드 를 가볍게 쓸 수 있다.

class Solution {
    int index=0;
    public int lastRemaining(int n, int m) {
         if(n==1)
            return 0;      
        return (lastRemaining(n-1,m)+m)%n;
    }
}

그러나 재 귀 효율 은 왔다갔다 하 는 규정 이 있 기 때문에 효율 이 직접적 으로 교체 하 는 것 보다 약간 떨 어 지고 예전 부터 뒤로 교체 할 수 있다.

class Solution {
    public int lastRemaining(int n, int m) {
        int value=0;
            for(int i=1;i<=n;i++)
            {
                value=(value+m)%i;
            }
            return  value;
    }
}

결어
나 는 이 글 을 통 해 조세 프 링 문 제 를 파악 하고 이해 해 야 한다 고 생각한다.이런 누 드 조세 프 링 문제 가 발생 할 확률 이 매우 높 고 고찰 이 빈번 하 다.링크 시 뮬 레이 션 은 근본 사상 이 고 질서 있 는 집합 시 뮬 레이 션 링크 는 향상 이 며 공식 적 인 전달 이 야 말로 가장 학습 가치 가 있 는 곳 이다.만약 에 처음에 이 해 를 접 하고 이해 하지 못 하면 몇 번 더 볼 수 있다.
이상 은 C++를 바탕 으로 조세 프 링 문 제 를 실현 하 는 세 가지 해법 에 대한 상세 한 내용 입 니 다.C+조세 프 링 에 관 한 자 료 는 우리 의 다른 관련 글 을 주목 하 세 요!