LeetCode 1483 트 리 노드 의 K 번 째 조상 인 구조 캐 시, 조회 최적화 O (logN)

제목.
LeetCode 1483 나무 노드 의 K 번 째 조상
나무 한 그루 를 드 리 겠 습 니 다. 나무 에 n 개의 노드 가 있 습 니 다. 0 에서 n - 1 번 호 를 누 르 십시오.나 무 는 부모 노드 배열 의 형식 으로 제 시 됩 니 다. 그 중에서 parent [i] 는 노드 i 의 부모 노드 입 니 다.나무의 뿌리 노드 는 번호 가 0 인 노드 이다.
getKthAncestor (int node, int k) 함 수 를 설계 하고 실현 하 십시오. 함 수 는 노드 node 의 k 번 째 조상 노드 를 되 돌려 줍 니 다.이러한 조상 노드 가 존재 하지 않 는 다 면 - 1 로 돌아 갑 니 다.
나무 노드 의 k 번 째 조상 노드 는 이 노드 에서 뿌리 노드 까지 의 k 번 째 노드 이다.알림:

1 <= k <= n <= 5*10^4

parent [0] = = - 1 은 번호 가 0 인 노드 가 루트 노드 임 을 나타 낸다.

모든 0 < i < n, 0 < = parent [i] < n 총 성립

0 <= node < n

최대 5 * 10 ^ 4 회 조회

사고의 방향
각 노드 의 첫 번 째 조상, 10 번 째 조상, 100 번 째 조상, 1000 번 째 조상 과 10000 번 째 조상 을 기록 합 니 다. 데이터 규모 가 10 ^ 4 이기 때문에 이 10000 까지 유지 하면 됩 니 다. 이 캐 시 시트 로 찾 아 보 세 요. 찾 는 시간 복잡 도 는 O (logN) 입 니 다.캐 시 구성 시간 복잡 도 O (N)
코드

class TreeAncestor {
     
    private int[][] anc;

    public TreeAncestor(int n, int[] parent) {
     
        anc = new int[n][5];
        for(int i = 0; i < n; i++) {
     
            Arrays.fill(anc[i], -1);
            anc[i][0] = parent[i];
        }
        for(int i = 1; i < 5; i++) {
     
            for(int j = 0; j < n; j++) {
     
                int cur = anc[j][i-1];
                for(int k = 0; k < 9; k++) if(cur != -1) {
     
                    cur = anc[cur][i-1];
                }
                anc[j][i] = cur;
            }
        }
    }
    
    public int getKthAncestor(int node, int k) {
     
        for(int i = 4; i >= 0; i--) {
     
            int base = 1;
            for(int j = 0; j < i; j++) {
     
                base *= 10;
            }
            while(k >= base) {
     
                node = anc[node][i];
                k -= base;
                if(node == -1) {
     
                    return -1;
                }
            }
        }
        return node;
    }
}