>source

인터뷰에서 코딩 질문을 받았고 설명은 다음과 같았습니다. 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;
}

하지만 이상하게도 샘플 테스트 케이스만 통과했지만 다른 테스트 케이스는 통과하지 못했습니다. 아무도 내가 어떻게 개선해야하는지 도와주세요?

알고리즘은 매우 간단합니다. N을 주문하고 항상 가장 최근의 가장 큰 양에 대해 필터를 사용합니다. 반복하다.

Déjà vu2022-02-14 08:30:55

@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)
    

  • 이전 SQL N에서 관계 없음 테이블로
  • 다음 typescript : 'xxx'유형에 'xxx'속성이 존재하지 않습니다.'를 발생시키는 방법은 무엇입니까?