codility 에서 의 연습 (2)

codility 에 연습 레 슨 2 가 추가 되 었 습 니 다.
세 문제 가 있 습 니 다.
(1) Perm-Check
주어진 정수 배열 은 N 개의 수 를 가지 고 있 습 니 다. 1 - N 의 배열 이 냐 고 물 었 습 니 다. 즉, 모든 수 는 1 - N 이 고 한 번 만 나타 나 는 것 입 니까?출력 1 과 0 은 여부, 입력 범위 N [1. 10 ^ 5], 배열 의 정수 [1. 10 ^ 5], 복잡 도 시간 공간 이 모두 O (N) 임 을 요구 합 니 다.
분석: 공간 복잡 도 O (N) 의 알고리즘 은 매우 간단 합 니 다. 우 리 는 bool 배열 을 만들어 1 - N 을 표시 할 수 있 습 니 다. 모든 숫자 가 나 타 났 는 지 여 부 를 표시 할 수 있 습 니 다.코드 는 다음 과 같 습 니 다:

// you can also use includes, for example:
// #include <algorithm>
int solution(vector<int> &A) {
    // write your code here...
    vector<bool> have;
    int i,n = A.size();
    have.resize(n, false);
    for (i = 0; i < n; ++i) {
        if ((--A[i] >= n) || (have[A[i]])) {
            return 0;
        }
        have[A[i]] = true;
    }
    return 1;
       	
}

사실 우 리 는 공간 복잡 도가 O (1) 인 알고리즘 이 있다.이용 연습
Perm - Missing - Em 의 방법 은 A [i] 를 A [A [i] - 1] 의 위치 로 바 꾸 고 코드 는 다음 과 같 습 니 다.

 // you can also use includes, for example:
// #include <algorithm>
int solution(vector<int> &A) {
    // write your code here...
    int n = A.size(),i,x,t;
    for (i = 0; i < n; ++i) {
        for (x = A[i]; (x <= n) && (A[x - 1] != x); ) {
            t = A[x - 1];
            A[x - 1] = x;
            x = t;
        }
        if (x > n) {
            return 0;
        }
    }
    for (i = 0; i < n; ++i) {
        if (A[i] != i + 1) {
           return 0;
        }
    }
    return 1;
       
}

우 리 는 또한 그것 을 좀 더 아름 답 게 할 수 있다. 만약 에 우리 가 A [0. i] 를 각각 1. i + 1 로 만 들 려 고 한다 면 현재 의 A [i] 에 대해! =i + 1, A [0. i - 1] 에서 이미 1. i 입 니 다. 만약 에 A [i] < i + 1, 그러면 중복 되 었 다 는 뜻 입 니 다. 그리고 A [i] > n 도 안 됩 니 다. 모든 수 는 1. n 밖 에 안 되 기 때 문 입 니 다. 그리고 A [A [i] - 1] 의 위치 수 와 A [i] 가 중복 되 는 지, 중복 되 지 않 으 면 반복 되 지 않 으 면 A [i] 가 요 구 를 만족 시 킬 때 까지 바 꾸 겠 습 니 다. 코드 는 다음 과 같 습 니 다.

// you can also use includes, for example:
// #include <algorithm>
int solution(vector<int> &A) {
    // write your code here...
    int n = A.size(),i,t;
    for (i = 0; i < n; ++i) {
        while (A[i] != i + 1) {
            if ((A[i] > n) || (A[i] < i + 1) || (A[A[i] - 1] == A[i])) {
                return 0;
            }
            t = A[i];
            A[i] = A[A[i] - 1];
            A[t - 1] = t;
        }
    }
    return 1;
}

이 안 에는 while 순환 이 있 지만 사실은 O (n) 입 니 다. 매번 교환 할 때마다 적어도 하나의 수 를 그 가 있어 야 할 위치 로 바 꾸 었 기 때 문 입 니 다.우 리 는 이 while 순환 을 사용 하지 않 아 도 됩 니 다. 생각 이 일치 합 니 다. 우 리 는 순환 변수 i 의 값 을 수정 하려 고 할 수 있 습 니 다. 코드 는 다음 과 같 습 니 다.

int solution(vector<int> &A) {
    // write your code here...
    int n = A.size(),i,t;
    for (i = 0; i < n;) {
        if (A[i] == i + 1) {
            ++i;
        }
        else {
            if ((A[i] > n) || (A[i] < i + 1) || (A[A[i] - 1] == A[i])) {
                return 0;
            }
            t = A[i];
            A[i] = A[A[i] - 1];
            A[t - 1] = t;
        }
    }
    return 1;
}

(2) Frog-River-One
배경 이 재 미 있 습 니 다. 실질 적 으로 N 길이 의 정수 배열 이 1 - X 에서 의 모든 정 수 를 포함 하고 있 는 지 물 어 보 는 것 입 니 다.N 과 X 는 모두 [1. 10 ^ 5] 이 고 배열 의 수 는 모두 1. X 이다.배열 A [0. r] 가 1. X 의 모든 수 를 포함 하고 있 으 면 r 로 돌아 갑 니 다. 그렇지 않 으 면 - 1 로 돌아 갑 니 다.복잡 도 시간 O (N), 공간 O (X) 를 요구 합 니 다.
이 문 제 는 사실 이전 문제 와 차이 가 많 지 않 습 니 다. 공간 적 으로 우 리 는 X 길이 의 bool 배열 을 만들어 서 나타 난 적 이 없 음 을 표시 할 수 있 습 니 다.사실 우 리 는 O (1) 를 위 한 공간 이 있다.우선 우리 가 존재 한다 면 적어도 X 항 이 있어 야 한다. 우 리 는 배열 의 앞 X 항 을 앞에서 말 한 교환 을 이용 하여 놓 아야 할 위치 로 교환 한 다음 에 X. N - 1 항 에서 그 값 이 0. X - 1 의 위치 에 있 는 지 확인 하고 필요 하 다 면 놓 아야 한다. 그리고 r 를 업데이트 하 는 것 은 약간 번 거 롭 지만 생각 은 변 하지 않 는 다.

// you can also use includes, for example:
// #include <algorithm>
int solution(int X, vector<int> &A) {
    // write your code here...
    int i, r,t,n = A.size();
    if (X > n) {
        return -1;
    }
    for (i = 0; i < X;) {
        if ((A[i] > X) || (A[A[i] - 1] == A[i])) {
            ++i;
        }
        else {
            t = A[i];
            A[i] = A[A[i] - 1];
            A[t - 1] = t;
            /*if (t < i + 1) {
                ++i;
            }*/
        }
    }
    r = X - 1;
    for (i = X; i < n; ++i) {
        if ((A[i] <= X) && (A[A[i] - 1] != A[i])) {
            A[A[i] - 1] = A[i];
            r = i;
        }
    }
    for (i = 0; i < X; ++i) {
        if (A[i] != i + 1) {
            return -1;
        }
    }
    return r;
 }

(3) Max-Counters
한 배열 의 길 이 는 N 이 고 처음에 모든 수 는 0 이 며 두 가지 조작 이 있 습 니 다. 하 나 는 특정한 요소 에 1 을 추가 하 는 것 이 고 다른 하 나 는 모든 요 소 를 현재 의 최대 치 로 바 꾸 는 것 입 니 다. 이런 조작 을 몇 번 정 한 후에 배열 의 최종 상 태 를 구 하 는 것 입 니 다.배열 길이 N 과 조작 개수 M 은 모두 [1. 10 ^ 5] 에 있 습 니 다.복잡 도 시간 O (N + M), 공간 O (N) 를 요구 합 니 다.
우 리 는 배열 에서 모든 작업 에 대해 하나의 시간 스탬프 를 유지 해 야 합 니 다. 시간 스탬프 에 따라 배열 요소 의 값 이 이전의 최대 치 인지, 아니면 현재 의 값 인지 결정 합 니 다. 매번 두 번 째 작업 전의 최대 치 를 기록 합 니 다. 코드 는 다음 과 같 습 니 다.

// you can also use includes, for example:
// #include <algorithm>
vector<int> solution(int N, vector<int> &A) {
    // write your code here...
    int i,m = A.size(), lastv = 0, lastt = -1, v = 0;
    vector<int> r, t;
    r.resize(N , 0);
    t.resize(N, -1);
    for (i = 0; i < m; ++i) {
        if (--A[i] < N) {
            v = max(r[A[i]] = ((t[A[i]] > lastt)?r[A[i]]:lastv) + 1, v);
            t[A[i]] = i;
        }
        else {
            lastv = v;
            lastt = i;
        }
    }
    for (i = 0; i < N; ++i) {
        if (lastt > t[i]) {
            r[i] = lastv;
        }
    }
    return r;
            
}

사실 시간 스탬프 는 생략 할 수 있 습 니 다. 코드 는 다음 과 같 습 니 다.

// you can also use includes, for example:
// #include <algorithm>
vector<int> solution(int N, vector<int> &A) {
    // write your code here...
    int i,m = A.size(), lastv = 0, v = 0;
    vector<int> r;
    r.resize(N , 0);
    for (i = 0; i < m; ++i) {
        if (--A[i] < N) {
            v = max(v, r[A[i]] = max(r[A[i]], lastv) + 1);
        }
        else {
            lastv = v;
        }
    }
    for (i = 0; i < N; ++i) {
        r[i] = max(r[i], lastv);
    }
    return r;
            
}