常见题解汇总

最小大堆

最小/最大堆对应的ts和js实现如下：

type compareFn<T> = (a:T, b:T) => boolean;
class Heap<T>{
  private compare:compareFn<T>;
  private arr:T[];
  constructor(compare:compareFn<T>, arr:T[] = []){
    this.compare = compare;
    this.arr = arr;
    if(this.arr.length > 0){
      this.buildDown2Top();
    }
  }
  get size():number {
    return this.arr.length
  }
  get data():T[]{
    return this.arr;
  }
  private compareNode(nodes:number[], type:string, end:number):void{
    let [parent, left, right] = nodes;
    if(parent < 0) return;
    let target = parent;
    if(left <= end && this.compare(this.arr[target],this.arr[left])) target = left;
    if(right <= end && this.compare(this.arr[target], this.arr[right])) target = right;
    if(target !== parent){
      let temp = this.arr[target];
      this.arr[target] = this.arr[parent];
      this.arr[parent] = temp;
      type === 'up' ? this.up(parent, end): this.down(target, end)
    }
  }
  private up(child:number, end:number):void{
    if(child < 0 || child > end) return;
    let parent = Math.floor((child - 1) / 2);
    let left = parent * 2 + 1, right = left + 1;
    this.compareNode([parent, left, right], 'up', end);
  }
  private down(parent:number, end:number):void{
    if(parent < 0 || parent > end) return;
    let left = parent * 2 + 1, right = left + 1;
    this.compareNode([parent, left, right], 'down', end); 
  }
  private buildDown2Top(){
    for(let i = this.size - 1; i >= 0; i--) this.down(i, this.size - 1);
  }
  private buildTop2Down(){
    for(let i = 0; i < this.size; i++) this.up(i, this.size - 1);
  }
  public push(item:T){
    this.arr.push(item);
    if(this.size > 1) this.up(this.size - 1, this.size - 1);
  }
  public pop():T | undefined{
    if(this.size <= 0) return undefined;
    let result = this.arr[0];
    this.arr[0] = this.arr[this.size - 1];
    this.arr.pop();
    if(this.size > 1) this.down(0, this.size - 1);
    return result;
  }
  public peek():T|undefined{
    if(this.size <= 0) return undefined;
    return this.arr[0];
  }
  public replace(item:T):void{
    if(this.size <= 0) return;
    this.arr[0] = item;
    if(this.size > 1) this.down(0, this.size - 1);
  }
}

class Heap { // 先实现了堆数据结构
  constructor(compare, arr=[]){
    this.compare = compare; // 比较函数，用于控制生产最大堆或最小堆
    this.arr = arr; // 初始化array
    if(arr && Array.isArray(arr)){ // 建堆代码与此题无关
      this._buildDown2Top(); // 若初始化arr不为空，则对arr建堆
    }
  }
  get size() {
    return this.arr.length;
  }
  _buildDown2Top() { // 建堆代码与此题无关
    for(let i = this.size - 1; i >= 0; i--){
      this._down(i, this.size - 1);
    }
  }
  _buildTop2Down() { // 建堆代码与此题无关
    for(let i = 0; i < this.size; i++){
      this._up(i, this.size - 1);
    }
  }
  _down(parent, end) { // 向下递归堆化
    if(parent < 0 || parent > end) return;
    let left = parent * 2 + 1;
    let right = left + 1;
    this._compareNode(parent, left, right, 'down', end);
  }
  _up(child, end){ // 向上递归堆化
    if(child < 0 || child > end) return;
    let parent = Math.floor((child - 1) / 2);
    let left = parent * 2 + 1;
    let right = left + 1;
    this._compareNode(parent, left, right, 'up', end);
  }
  _compareNode(parent, left, right, type, end){ // 每个节点对通用对比函数
    let target = parent;
    if(left <= end && this.compare(this.arr[target], this.arr[left])){
      target = left;
    }
    if(right <= end && this.compare(this.arr[target], this.arr[right])){
      target = right;
    }
    if(target !== parent){
      let temp = this.arr[target];
      this.arr[target] = this.arr[parent];
      this.arr[parent] = temp;
      type === 'up' ? this._up(parent, end) : this._down(target, end);
    }
  }
  push(num) {
    this.arr.push(num);
    this._up(this.size - 1, this.size - 1);
  }
  pop() {
    if(this.size <= 0) return undefined;
    let result = this.arr[0];
    this.arr[0] = this.arr[this.size - 1];
    this.arr.pop();
    this._down(0, this.size - 1);
    return result;
  }
  peek(){
    if(this.size <= 0) return undefined;
    return this.arr[0];
  }
}

n数之和

常见两数之和题目通常使用哈希表存储差值，通过比较差值解题算法复杂度为O(n)，空间复杂度为O(n)，而其扩展题三数之和则通常将数组进行排序，先固定一位数，然后使用双指针对撞的方式来扫描数组，求取三数之和，对于三数以上的n数之和，则与三数之和类似先遍历固定一个元素，然后使用递归求取n-1数之和，直到将问题转换为三数之和，则使用三数之和的方法进行求解。以下为代码示例

class Demo {
  static nSum(nums:number[], target:number, n:number):number[][]{
    let result:number[][] = [];
    nums.sort((a, b) => a -b); // 对数组进行排序，方便使用指针对撞
    Demo.nSumCore(nums, target, n, 0, result, []);
    return result;
  }
  static nSumCore(nums:number[], target:number, n:number, index:number, res:number[][], acc:number[]) {
    if(index >= nums.length || n < 3) return; // 仅当n >= 3时才采用此算法
    for(let i = index;i < nums.length; i++){
      if(i>index && nums[i] === nums[i-1]) continue; // 跳过之前已遍历的重复元素
      if(n>3){ // 当n大于3时递归的调用n数之和，最终转换为3数之和求解
        Demo.nSumCore(nums, target, n-1, i+1, res, [nums[i], ...acc]);
        continue;
      }
      let left = i + 1, right = nums.length - 1;
      while(left < right) { // 固定i值，左右指针对撞
        let accVal = 0 // 当acc为空数组时，直接调用reduce会报错
        if(acc.length > 0) accVal = acc.reduce((pre, cur) => pre + cur);
        let sum = nums[i] + nums[left] + nums[right] + accVal;
        if(sum === target) { // 找到组合，存储结果
          res.push([...acc, nums[i], nums[left], nums[right]]);
          while(left < right && nums[left] === nums[left+1]){
            left++; // 左右指针对撞，若左指针的下一个值与当前值相同，则右移一位
          }
          while(left < right && nums[right] === nums[right-1]){
            right--; // 左右指针对撞，与左指针逻辑类似，可跳过重复的元素
          }
          left++; // 找到组合和左右指针当前值已被存储，需要向右向左移动一位
          right--;
        } else if (sum < target) {
          left++; // 如果求和较小，则右移左指针
        } else {
          right--;
        }
      }
    }
  }
  static test(){
    let data = [-1,0,1,2,-1,-4];
    console.log(Demo.nSum(data, 0, 3));
  }
}
Demo.test();

接雨水

topK优先队列问题

背景：求数组中出现频率top k的元素

思路：此类问题需要先进行一次遍历，通过map统计并保存元素出现的频次，然后遍历map可通过维护大小为k的最小堆(top k)或最大堆(low k)实现top k元素的获取

// 通过遍历实现
class Solution {
  static duplicate(nums, k){
    let result;
    let cache = new Map();
    for(const item of nums){
      if(!cache.has(item)){
        cache.set(item, 1)
      }else{
        let tmp = cache.get(item);
        cache.set(item, tmp+1);
      }
    }
    return (Array.from(cache)).sort((a, b) => a[1] <= b[1] ? 1 : -1).slice(0, k).map(item => item[0]);
  }
  static test(){
    let nums = [1,2,3,3,4,5,5];
    let k = 2
    // 重复次数最多的前k个数字
    console.log(Solution.duplicate(nums, k))
  }
}
Solution.test();

// 通过最大/小堆实现
class Solution{
  static topKFrequent<T>(nums:T[], k:number):T[]|undefined{
    if(nums.length < k) return undefined;
    let countMap:Map<T, number>= new Map();
    for(const item of nums){
      if(countMap.has(item)){
        let tmp = countMap.get(item);
        countMap.set(item, tmp+1);
      }else countMap.set(item, 1);
    }
    const compare = (a:[T,number], b:[T, number]) => a[1] > b[1] ? true : false;
    let result:Heap<[T, number]> = new Heap(compare);
    debugger
    for(const item of countMap){
      if(result.size < k) result.push(item);
      else {
        let tmp = result.peek();
        if(item[1] > tmp[1]) {
          result.replace(item);
        }
      }
    }
    return result.data.map(item => item[0])
  }
  static test(){
    let example = [5,3,1,1,1,3,73,1], k = 2;
    console.log(Solution.topKFrequent<number>(example, k));
  }
}
Solution.test();