Leetcode823: 인자 이차수 문제
문제 설명
하나의 그룹을 지정합니다. 그룹의 수는 중복되지 않고 모두 1보다 큽니다.수조의 수를 사용하여 두 갈래 나무를 구축하도록 요구합니다. 모든 숫자는 중복 사용될 수 있습니다. 잎 노드를 제외하고 각 노드의 값은 그 하위 노드의 곱셈과 같습니다. 두 갈래 나무를 구축하는 수량을 구하면 되돌아오는 결과mod10*9+7
Example 1:
Input:
A = [2, 4] Output: 3 Explanation: We can make these trees: [2], [4], [4, 2, 2] Example 2: Input:
A = [2, 4, 5, 10] Output: 7 Explanation: We can make these trees: [2], [4], [5], [10], [4, 2, 2], [10, 2, 5], [10, 5, 2] . 원본 링크:https://leetcode.com/problems/binary-trees-with-factors/
분석
조건에 부합되는 두 갈래 나무는 두 가지 상황으로 나뉘는데 하나는 하나의 절점으로 구성된 두 갈래 나무로 하위 노드가 없고 모두 A.length의 상황이 있다.또 다른 상황은 여러 노드로 구성된 두 갈래 나무로 노드의 값은children 노드 값의 곱셈입니다.첫 번째 상황은 매우 간단해서 토론할 필요가 없다. 두 번째 상황은 약간 복잡하지만, 우리는 다음과 같이 생각할 수 있다.
만약에 a=b*c 등식이 성립된다면 a가 아버지 노드로 구성된 두 갈래 나무의 수량=b가 아버지 노드로 구성된 두 갈래 나무*가 아버지 노드로 구성된 두 갈래 나무*2(좌우 노드 교환 위치).
따라서 원소 a가 루트에 대응하는 두 갈래 나무의 수량에 대해 우리는 모든 b와 c가 대응하는 두 갈래 나무의 수량(b
실현
public int umFactoredBinaryTrees(int[] A){
int mod = 1000000007;
Arrays.sort(A);
//key root ，value
Map map = new HashMap();
Long result = 0;
for(int m = 0; i < A.length; m++){
long cnt = 1; //
int a = A[m];
for(Integer b : map.keySet()){
if(a % b == 0 && map.containsKey(a/b)){
cnt += map.get(b) * map.get(a/b);
}
}
map.put(num, cnt);
result = (result + cnt) % mod;
}
return (int) result;
} 공간 복잡도 O(n), 시간 복잡도 O(n^2)
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
