Algorithm - Heap Problems

이소라·2022년 10월 4일
0

Algorithm

목록 보기
25/77
post-custom-banner

LeetCode Problem : Last Stone Weight

  • You are given an array of integers stones where stones[i] is the weight of the ith stone.

  • We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:

    • If x == y, both stones are destroyed, and
    • If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.

  • Constraints:

    • 1 <= stones.length <= 30
    • 1 <= stones[i] <= 1000

  • Example 1:

    • Input: stones = [2,7,4,1,8,1]
    • Output: 1
    • Explanation:
      • We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
      • we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
      • we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
      • we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of the last stone.

  • Example 2:

    • Input: stones = [1]
    • Output: 1

Solution

/**
 * @param {number[]} stones
 * @return {number}
 */
var lastStoneWeight = function(stones) {
    if (stones.length === 1) return stones[0];
    let firstStone, secondStone;
    while (stones.length > 1) {
        stones.sort((a, b) => b - a);
        firstStone = stones[0];
        secondStone = stones[1];
        if (firstStone != secondStone) {
            stones.push(firstStone - secondStone);
        }
        stones.splice(0, 2);
    }
    return stones[0] ? stones[0] : 0;
};
  • Max Binary Heap을 사용한 다른 풀이
var lastStoneWeight = function(stones) {
  if (stones.length === 1) return stones[0];
  
  const heap = new MaxBinaryHeap();
  stones.forEach((stone) => heap.insert(stone));
  let firstStone, secondStone, diff;
    
  while (heap.values.length > 1) {
    firstStone = heap.extractMax();
    secondStone = heap.extractMax();
    diff = firstStone - secondStone;
    if (diff != 0) {
      heap.insert(diff);
    }
  }
  return heap.values.length !== 0 ? heap.values[0] : 0;
};

LeetCode Problem : Maximum Product of Two Elements in an Array

  • Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of (nums[i]-1)*(nums[j]-1).
  • Constraints:
    • 2 <= nums.length <= 500
    • 1 <= nums[i] <= 10^3
  • Example 1:
    • Input: nums = [3,4,5,2]
    • Output: 12
    • Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)(nums[2]-1) = (4-1)(5-1) = 3*4 = 12.

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function(nums) {
    let max = 0;
    let product = 0;
  for (let i = 0; i < nums.length; i++) {
      for (let j = i + 1; j < nums.length; j++) {
          product = (nums[i] - 1)*(nums[j] - 1);
          if (product > max) {
              max = product;
          }
      }
  }
    return max;
};
  • Max Binary Heap을 사용한 다른 풀이
var maxProduct = function(nums) {
    const heap = new MaxBinaryHeap();
    nums.forEach((num) => heap.insert(num));
    const first = heap.extractMax();
    const second = heap.extractMax();
    return (first - 1)*(second - 1);
};

LeetCode Problem : Reduce Array Size to The Half

  • You are given an integer array arr. You can choose a set of integers and remove all the occurrences of these integers in the array.
  • Return the minimum size of the set so that at least half of the integers of the array are removed.
  • Constraints:
    • 2 <= arr.length <= 10^5
    • arr.length is even.
    • 1 <= arr[i] <= 10^5
  • Example 1:
    • Input: arr = [3,3,3,3,5,5,5,2,2,7]
    • Output: 2
    • Explanation:
      • Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
      • Possible sets of size 2 are {3,5},{3,2},{5,2}.
      • Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has a size greater than half of the size of the old array.

Solution

/**
 * @param {number[]} arr
 * @return {number}
 */
var minSetSize = function(arr) {
    const threshold = arr.length / 2;
    const numMap = new Map();
    let deletedCount = 0;
    let setSize = 0;
    
    arr.forEach((num) => {
        let frequency = numMap.get(num);
        frequency != undefined ? numMap.set(num, frequency + 1) : numMap.set(num, 1);
    });
    
    const frequencyArray = [...numMap.values()].sort((a,b) => b - a);
    
    for (let i = 0; i < frequencyArray.length; i++) {
        deletedCount += frequencyArray[i];
        if (deletedCount >= threshold) {
            setSize = i + 1;
            break;
        }
    }
    
    return setSize;
};
  • Max Binary Heap을 사용한 다른 풀이
var minSetSize = function(arr) {
    const threshold = arr.length / 2;
    const numMap = new Map();
    let deletedCount = 0;
    let setSize = 0;
    
    arr.forEach((num) => {
        let frequency = numMap.get(num);
        frequency != undefined ? numMap.set(num, frequency + 1) : numMap.set(num, 1);
    });
    
    const heap = new MaxBinaryHeap();
    
    for (let frequency of numMap.values()) {
        heap.insert(frequency);
    }
    
    for (let i = 0; i < heap.values.length; i++) {
        deletedCount += heap.extractMax();
        if (deletedCount >= threshold) {
            setSize = i + 1;
            break;
        }
    }
    
    return setSize;
};

Sort Characters By Frequency

  • Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.
  • Return the sorted string. If there are multiple answers, return any of them.
  • Constraints:
    • 1 <= s.length <= 5 * 10^5
    • s consists of uppercase and lowercase English letters and digits.
  • Example 1:
    • Input: s = "tree"
    • Output: "eetr"
    • Explanation:
      • 'e' appears twice while 'r' and 't' both appear once.
      • So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
  • Example 2:
    • Input: s = "cccaaa"
    • Output: "aaaccc"
    • Explanation:
      • Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.
      • Note that "cacaca" is incorrect, as the same characters must be together.
  • Example 3:
    • Input: s = "Aabb"
    • Output: "bbAa"
    • Explanation:
      • "bbaA" is also a valid answer, but "Aabb" is incorrect.
      • Note that 'A' and 'a' are treated as two different characters.

Solution

/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function(s) {
    const strMap = new Map();
    let str;
    let node;
    let result = '';
    
    for (let i = 0; i < s.length; i++) {
        str = strMap.get(s[i]);
        str != undefined ? strMap.set(s[i], str + 1) : strMap.set(s[i], 1);
    }
    
    const heap = new MaxBinaryHeap();
    
    for (let [value, frequency] of strMap.entries()) {
        heap.insert(value, frequency);
    }
    
    const length = heap.values.length;
    for (let i = 0; i < length; i++) {
        node = heap.extractMax();
        result += node.value.repeat(node.frequency);
    }
    
    return result;
};

class Node {
    constructor(value, frequency) {
        this.value = value;
        this.frequency = frequency;
    }
}

class MaxBinaryHeap {
  constructor() {
    this.values = [];
  }
  
  insert(value, frequency) {
    const node = new Node(value, frequency);
    this.values.push(node);
    this.bubbleUp();
  }
  
  bubbleUp() {
    let idx = this.values.length - 1;
    const element = this.values[idx];
    let parentIdx;
    let parent;
    
    while(idx > 0) {
      parentIdx = Math.floor((idx - 1)/2);
      parent = this.values[parentIdx];
      
      if (element.frequency <= parent.frequency) break;
      
      this.values[parentIdx] = element;
      this.values[idx] = parent;
      idx = parentIdx;
    }
  }
  
  extractMax() {
    const max = this.values[0];
    const end = this.values.pop();
    if (this.values.length > 0) {
      this.values[0] = end;
      this.sinkDown();
    }
      
    return max;
  }
  
  sinkDown() {
    let idx = 0;
    const length = this.values.length;
    const element = this.values[0];
    let leftChildIdx;
    let rightChildIdx;
    let leftChild;
    let rightChild;
    let swap;
    
    while(true) {
      leftChildIdx = 2 * idx + 1;
      rightChildIdx = 2 * idx + 2;
      swap = null;
      
      if (leftChildIdx < length) {
        leftChild = this.values[leftChildIdx];
        if (leftChild.frequency > element.frequency) {
        swap = leftChildIdx;
        }
      }
      
      if (rightChildIdx < length) {
        rightChild = this.values[rightChildIdx];
        if (
          (swap === null && rightChild.frequency > element.frequency) || 
          (swap !== null && rightChild.frequency > leftChild.frequency)
          ) {
          swap = rightChildIdx;
        }
      }
      
      if (swap === null)  break;
      this.values[idx] = this.values[swap];
      this.values[swap] = element;
      idx = swap;
    }
  }
}

Programmers Problem : 이중우선순위큐

  • 이중 우선순위 크는 다음 연산을 할 수 있는 자료구조를 말합니다.
명령어수신 탑(높이)
I 숫자큐에 주어진 숫자를 입력합니다.
D 1큐에서 최댓값을 삭제합니다.
D -1큐에서 최솟값을 삭제합니다.

  • 이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

  • 제한사항

    • operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
    • operations의 원소는 큐가 수행할 연산을 나타냅니다.
      • 원소는 “명령어 데이터” 형식으로 주어집니다.
      • 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
    • 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

  • 입출력 예 1

    • 입력 : ["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]
    • 출력 : [0,0]
    • 설명 :
      • 16과 -5643을 삽입합니다.
      • 최솟값을 삭제합니다. -5643이 삭제되고 16이 남아있습니다.
      • 최댓값을 삭제합니다. 16이 삭제되고 이중 우선순위 큐는 비어있습니다.
      • 우선순위 큐가 비어있으므로 최댓값 삭제 연산이 무시됩니다.
      • 123을 삽입합니다.
      • 최솟값을 삭제합니다. 123이 삭제되고 이중 우선순위 큐는 비어있습니다.
      • 따라서 [0, 0]을 반환합니다.

  • 입출력 예 2

    • 입력 : ["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]
    • 출력 : [333, -45]
    • 설명 :
      • -45와 653을 삽입후 최댓값(653)을 삭제합니다. -45가 남아있습니다.
      • -642, 45, 97을 삽입 후 최댓값(97), 최솟값(-642)을 삭제합니다. -45와 45가 남아있습니다.
      • 333을 삽입합니다.
      • 이중 우선순위 큐에 -45, 45, 333이 남아있으므로, [333, -45]를 반환합니다.

Solution

function solution(operations) {
    const heap = new MaxBinaryHeap();
    
    operations.forEach((operation) => {
        let [command, value] = operation.split(' ');
        value = Number(value);
        
        if (command === 'I') {
            heap.insert(value);
            return;
        }
        if (command === 'D') {
            if (!heap.values.length) {
                return;
            }
            if (value === 1) {
                heap.extractMax();
                return;
            }
            if (value === -1) {
                heap.extractMin();
                return;
            }
            
        }
    });
    
    if (!heap.values.length) {
        return [0, 0];
    }
    
    const max = heap.extractMax();
    const min = heap.extractMin();
    return [max, min];
}
class MaxBinaryHeap {
  constructor() {
    this.values = [];
  }
    
    getSize() {
        return this.values.length;
    }
  
  insert(element) {
    this.values.push(element);
    this.bubbleUp();
  }
  
  bubbleUp() {
    let idx = this.values.length - 1;
    const element = this.values[idx];
    let parentIdx;
    let parent;
    
    while(idx > 0) {
      parentIdx = Math.floor((idx - 1)/2);
      parent = this.values[parentIdx];
      
      if (element <= parent) break;
      
      this.values[parentIdx] = element;
      this.values[idx] = parent;
      idx = parentIdx;
    }
  }
  
  extractMax() {
    const max = this.values[0];
    const end = this.values.pop();
    if (this.values.length > 0) {
      this.values[0] = end;
      this.sinkDown();
    }
    return max;
  }
    
    extractMin() {
        const size = this.getSize();
        const middleIndex = Math.floor(size/2);
        let min = this.values[middleIndex];
        let minIndex = middleIndex;
        let currValue;
        
        for (let i = middleIndex + 1; i < size; i++) {
            currValue = this.values[i];
            if (currValue < min) {
                min = currValue;
                minIndex = i;
            }
        }
        
        this.values.splice(minIndex, 1);
        
        return min;
    }
  
  sinkDown() {
    let idx = 0;
    const length = this.values.length;
    const element = this.values[0];
    let leftChildIdx;
    let rightChildIdx;
    let leftChild;
    let rightChild;
    let swap;
    
    while(true) {
      leftChildIdx = 2 * idx + 1;
      rightChildIdx = 2 * idx + 2;
      swap = null;
      
      if (leftChildIdx < length) {
        leftChild = this.values[leftChildIdx];
        if (leftChild > element) {
        swap = leftChildIdx;
        }
      }
      
      if (rightChildIdx < length) {
        rightChild = this.values[rightChildIdx];
        if (
          (swap === null && rightChild > element) || 
          (swap !== null && rightChild > leftChild)
          ) {
          swap = rightChildIdx;
        }
      }
      
      if (swap === null)  break;
      this.values[idx] = this.values[swap];
      this.values[swap] = element;
      idx = swap;
    }
  }
}
profile
이소라
이전 포스트

Algorithm - Tree Problems

다음 포스트

Algorithm - Union-find

post-custom-banner

0개의 댓글