인터뷰에서 코딩 질문을 받았고 설명은 다음과 같았습니다. N 공장이 오염을 일으키고 있습니다. 주어진 오염량을 정수로 나타냅니다. 카운트 미니. 아니요. 총 오염을 최소한 절반으로 줄이는 데 필요한 필터의 수. 하나의 필터는 오염을 절반으로 줄입니다. 동일한 공장에 다른 필터를 넣으면 4번째(N/2/2)가 됩니다.
Example: N=[5,19,8,1]
totalPollution= 5+19+8+1=33
numberOfFiltersRequire=3
다음과 같이 할 수 있기 때문에= [(19/2)/2, 8/2,5,1]= 4.75+4+5+1= 14.75 이는 기존 오염의 절반 미만입니다.
Example: N=[3,0,5]
numberOfFiltersRequire=2
공해를 일으키는 두 공장에 필터를 넣어야 하기 때문에 이를 위해 아래와 같은 code를 작성했습니다.
int solve(int[] n){
int count= 0;
int totalPollution= Arrays.stream(n).sum();
int halfPollution= totalPollution/2; //I know I should have taken double but thought int wold work
long distinct= Arrays.stream(n).distinct)().count();
if(distinct== 1l)
return n; //this is the corner case where all factories pollute equally i.e [10,10]
PriorityQueue<Integer> pq= new PriorityQueue<>(Collections.reverseOrder());
for(int a:n)
pq.add(a);
while(totalPollution >= halfPollution){
int currnetPoll= pq.poll();
int halfVal= currentPoll/2;
totalPollution -= halfVal;
count++;
pq.add(halfVal);
}
return count;
}
하지만 이상하게도 샘플 테스트 케이스만 통과했지만 다른 테스트 케이스는 통과하지 못했습니다. 아무도 내가 어떻게 개선해야하는지 도와주세요?
@Déjàvu: 거의 비슷하게 했죠?
vihang shah2022-02-14 08:32:16나는 당신이 이미 code의 이 주석에 따른 문제를 알고 있다고 생각합니다: "//나는 두 배를 취해야 한다는 것을 알고 있지만 int wold 작동이라고 생각했습니다."). 정수 나누기는 내림합니다. 따라서 totalPollution이 33이면 halfPollution은 16입니다. 그리고 currentPoll이 19이면 halfVal은 9입니다. 정수 나누기에서 totalPollution -= halfVal은 24이고 8을 더 남겨 16에 도달합니다. 부동 소수점을 사용하면 33/2= 16.5 및 19/2입니다.= 9.5. 33-9.5= 23.5를 감안할 때 16.5에 도달하려면 7개만 더 있습니다.
user33861092022-02-14 08:50:26- 답변 # 1
당신의 프로그래밍 논리는 괜찮아 보입니다. 탐욕스러운 알고리즘입니다. 우선 순위 대기열을 사용하고 매번 가장 큰 요소를 제거하고 절반으로 줄인 다음 우선 순위 대기열에 다시 추가합니다. 다음을 놓친 것 같습니다.
카운트 미니. 아니요. 총 오염을 최소한 절반으로 줄이는 데 필요한 필터의 수.
다음은 잘못된 것입니다.
while(totalPollution >= halfPollution)그럴 수밖에 없다
while(totalPollution > halfPollution)
알고리즘은 매우 간단합니다. N을 주문하고 항상 가장 최근의 가장 큰 양에 대해 필터를 사용합니다. 반복하다.
Déjà vu2022-02-14 08:30:55