Python 은 인접 관계 에 따라 배열 의 두 가지 방식(단 방향 구조 와 양 방향 구조)을 복원 합 니 다.
이것 은 LeetCode 의 1743 입 니 다.인접 요소 에서 배열 을 복원 하 는 데 어려움 이 중간 입 니 다.
태그:"해시 표","더 블 포인터","시 뮬 레이 션"
n 개의 서로 다른 요소 로 구 성 된 정수 배열 nums 가 존재 하지만 구체 적 인 내용 은 기억 나 지 않 습 니 다.다행히 너 는 nums 중의 모든 인접 요 소 를 기억 하고 있다.
2 차원 정수 배열 adjacent Pairs 를 드 리 겠 습 니 다.크기 는 n-1 입 니 다.그 중에서 각 adjacent Pairs[i]=[ui,vi]는 요소 ui 와 vi 가 nums 에서 인접 해 있다 는 것 을 표시 합 니 다.
제목 데 이 터 는 요소 nums[i]와 nums[i+1]로 구 성 된 모든 인접 요소 가 adjacent Pairs 에 존재 하도록 보장 합 니 다.존재 형식 은[nums[i],nums[i+1]일 수도 있 고[nums[i+1],nums[i]일 수도 있 습 니 다.이 인접 원소 들 은 임의의 순서에 따라 나타 날 수 있다.
원본 배열 nums 를 되 돌려 줍 니 다.여러 가지 해답 이 있다 면,그 중 하 나 를 되 돌려 주면 된다.
예시 1:
입력:adjacentPairs=[2,1],[3,4],[3,2]]
출력:[1,2,3,4]
설명:배열 의 모든 인접 요 소 는 adjacent Pairs 에 있 습 니 다.
특히 주의해 야 할 것 은 adjacent Pairs[i]는 두 요소 가 서로 인접 해 있다 는 것 만 표시 하고 왼쪽-오른쪽 순 서 를 보장 하지 않 습 니 다.
예시 2:
입력:adjacentPairs=[4,-2],[1,4],[-3,1]]
출력:[-2,4,1,-3]
설명:배열 에 마이너스 가 있 을 수 있 습 니 다.
또 다른 해답 은[-3,1,4,-2]로 정 답 으로 간주 된다.
예시 3:
입력:adjacentPairs=[100000,-100000]]
출력:[100000,-100000]
알림:
제목 에 따 르 면 모든 인접 관계 가 numsnumsnums 에 나타 나 기 때문에 그 중의 합 법 적 인 배열 이 ansansans 이 고 길 이 는 Nn 이 라 고 가정 합 니 다.
그러면 분명히 ans[0]ans[0]ans[0]와 ans[n-1]ans[n-1]ans[n-1]는 numsnumsnums 에서 한 쌍 의 인접 관계 만 존재 하고 다른 ans[i]ans[i]ans[i]ans[i]는 두 쌍 의 인접 관계 가 존재 한다.
따라서 우 리 는'해시 표'를 사용 하여 numsnumsnums 에 나타 난 수 치 를 계산 할 수 있 습 니 다.'한 번 나타 난'수 치 를 ansansans 수치의 첫 번 째 로 찾 은 다음 에 주어진 인접 관계 에 따라'단 방향 구조'를 할 수 있 습 니 다.그 인접 한 수가 어떤 것 인지 쉽게 찾기 위해 우 리 는'해시 표'를 하나 더 열 어 인접 관 계 를 기록 해 야 합 니 다.
Java 코드:
class Solution {
public int[] restoreArray(int[][] aps) {
int m = aps.length, n = m + 1;
Map<Integer, Integer> cnts = new HashMap<>();
Map<Integer, List<Integer>> map = new HashMap<>();
for (int[] ap : aps) {
int a = ap[0], b = ap[1];
cnts.put(a, cnts.getOrDefault(a, 0) + 1);
cnts.put(b, cnts.getOrDefault(b, 0) + 1);
List<Integer> alist = map.getOrDefault(a, new ArrayList<>());
alist.add(b);
map.put(a, alist);
List<Integer> blist = map.getOrDefault(b, new ArrayList<>());
blist.add(a);
map.put(b, blist);
}
int start = -1;
for (int i : cnts.keySet()) {
if (cnts.get(i) == 1) {
start = i;
break;
}
}
int[] ans = new int[n];
ans[0] = start;
ans[1] = map.get(start).get(0);
for (int i = 2; i < n; i++) {
int x = ans[i - 1];
List<Integer> list = map.get(x);
for (int j : list) {
if (j != ans[i - 2]) ans[i] = j;
}
}
return ans;
}
}
class Solution:
def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
m = n = len(adjacentPairs)
n += 1
cnts = defaultdict(int)
hashmap = defaultdict(list)
for a, b in adjacentPairs:
cnts[a] += 1
cnts[b] += 1
hashmap[a].append(b)
hashmap[b].append(a)
start = -1
for i, v in cnts.items():
if v == 1:
start = i
break
ans = [0] * n
ans[0] = start
ans[1] = hashmap[start][0]
for i in range(2, n):
x = ans[i - 1]
for j in hashmap[x]:
if j != ans[i - 2]:
ans[i] = j
return ans
해법 1 에서 우 리 는'해시 표'계 수 를 통 해 ansansans 최초의 원 초적 인 것 을 기점 으로'단 방향 구조'를 실시 했다.
그렇다면 임의의 수 치 를 기점 으로 하 는 양 방향 구조 가 있 을 까?
답 은 분명 하 다.우 리 는 ansansans 의 길 이 를 2<=n<=1052<=n<=10^52<=n<=105 로 이용 하여 길이 10610^6106 의 배열 qqq 를 구성 할 수 있다.
여기 qqq 배열 은 반드시 1e61e61e 6 크기 로 열 어야 하 는 것 이 아 닙 니 다.우리 qqq 크기 가 ansansans 의 두 배 이상 이면 월경 문제 가 존재 하지 않 습 니 다.
qqq 배열 의 중간 위치 부터 그 중의 한 요 소 를 중간 위치 에 마음대로 추가 하고'더 블 포인터'를 사용 하여 각각'양쪽 확장'(l 과 r 는 각각 좌우 로 삽입 할 위 치 를 가리킨다).
l 지침 과 r 지침 이 직접 nnn 개의 수 치 를 가지 고 전체 ansansans 구조 가 완성 되 었 음 을 설명 할 때 우 리 는[l+1,r-1][l+1,r-1][l+1,r-1]범위 내의 수치 출력 을 답 으로 하면 된다.
Java 코드:
class Solution {
static int N = (int)1e6+10;
static int[] q = new int[N];
public int[] restoreArray(int[][] aps) {
int m = aps.length, n = m + 1;
Map<Integer, List<Integer>> map = new HashMap<>();
for (int[] ap : aps) {
int a = ap[0], b = ap[1];
List<Integer> alist = map.getOrDefault(a, new ArrayList<>());
alist.add(b);
map.put(a, alist);
List<Integer> blist = map.getOrDefault(b, new ArrayList<>());
blist.add(a);
map.put(b, blist);
}
int l = N / 2, r = l + 1;
int std = aps[0][0];
List<Integer> list = map.get(std);
q[l--] = std;
q[r++] = list.get(0);
if (list.size() > 1) q[l--] = list.get(1);
while ((r - 1) - (l + 1) + 1 < n) {
List<Integer> alist = map.get(q[l + 1]);
int j = l;
for (int i : alist) {
if (i != q[l + 2]) q[j--] = i;
}
l = j;
List<Integer> blist = map.get(q[r - 1]);
j = r;
for (int i : blist) {
if (i != q[r - 2]) q[j++] = i;
}
r = j;
}
int[] ans = new int[n];
for (int i = l + 1, idx = 0; idx < n; i++, idx++) {
ans[idx] = q[i];
}
return ans;
}
}
class Solution:
N = 10 ** 6 + 10
q = [0] * N
def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
m = len(adjacentPairs)
n = m + 1
hashmap = defaultdict(list)
for a, b in adjacentPairs:
hashmap[a].append(b)
hashmap[b].append(a)
l = self.N // 2
r = l + 1
std = adjacentPairs[0][0]
lt = hashmap[std]
self.q[l] = std
l -= 1
self.q[r] = lt[0]
r += 1
if len(lt) > 1:
self.q[l] = lt[1]
l -= 1
while (r-1)-(l+1)+1<n:
alt = hashmap[self.q[l+1]]
j = l
for i in alt:
if i != self.q[l+2]:
self.q[j] = i
j -= 1
l = j
blt = hashmap[self.q[r-1]]
j = r
for i in blt:
if i != self.q[r - 2]:
self.q[j] = i
j += 1
r = j
ans = [0] * n
for idx in range(n):
ans[idx] = self.q[idx+l+1]
return ans
공간 복잡 도:O(n)O(n)O(n)
마지막.
파 이 썬 이 인접 관계 에 따라 배열 을 복원 하 는 두 가지 방식(단 방향 구조 와 양 방향 구조)에 관 한 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 파 이 썬 인접 복원 배열 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 도 많은 응원 부탁드립니다!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Python의 None과 NULL의 차이점 상세 정보그래서 대상 = 속성 + 방법 (사실 방법도 하나의 속성, 데이터 속성과 구별되는 호출 가능한 속성 같은 속성과 방법을 가진 대상을 클래스, 즉 Classl로 분류할 수 있다.클래스는 하나의 청사진과 같아서 하나의 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
