jie's notes

Appearance

classic questions ​

content ​

lru ​

js
class ListNode {
  constructor(key, value) {
    this.key = key
    this.value = value
    this.next = null
    this.prev = null
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity
    this.hash = {}
    this.count = 0
    this.dummyHead = new ListNode()
    this.dummyTail = new ListNode()
    this.dummyHead.next = this.dummyTail
    this.dummyTail.prev = this.dummyHead
  }

  get(key) {
    let node = this.hash[key]
    if (node == null) return -1
    this.moveToHead(node)
    return node.value
  }

  put(key, value) {
    let node = this.hash[key]
    if (node == null) {
      if (this.count == this.capacity) {
        this.removeLRUItem()
      }
      let newNode = new ListNode(key, value)
      this.hash[key] = newNode
      this.addToHead(newNode)
      this.count++
    } else {
      node.value = value
      this.moveToHead(node)
    }
  }

  moveToHead(node) {
    this.removeFromList(node)
    this.addToHead(node)
  }
  
  removeFromList(node) {
    let temp1 = node.prev
    let temp2 = node.next
    temp1.next = temp2
    temp2.prev = temp1
  }

  addToHead(node) {
    node.prev = this.dummyHead
    node.next = this.dummyHead.next
    this.dummyHead.next.prev = node
    this.dummyHead.next = node
  }

  removeLRUItem() {
    let tail = this.popTail()
    delete this.hash[tail.key]
    this.count--
  }

  popTail() {
    let tail = this.dummyTail.prev
    this.removeFromList(tail)
    return tail
  }
}

搜索旋转排序数组 ​

js
var search = function (nums, target) {
    // 二分法
    let start = 0;
    let end = nums.length - 1;

    while (start <= end) {
        // >> 1 相当于除以2向下取整
        let mid = (start + end) >> 1;

        if (nums[mid] === target) {
            return mid;
        }

        // 如果中间数小于最右边数，则右半段是有序的
        // 如果中间数大于最右边数，则左半段是有序的
        if (nums[mid] < nums[end]) {
            // 判断target是否在(mid, end]之间
            if (nums[mid] < target && target <= nums[end]) {
                // 如果在，则中间数右移即start增大
                start = mid + 1;
            } else {
                // 如果不在，则中间数左移即end减小
                end = mid - 1;
            }
        } else {
            // [start, mid)
            if (nums[start] <= target && target < nums[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
    }

    return -1;
};

堆排序 ​

js
class Heap {
    constructor(arr) {
        this.arr = [...arr];
    }
    /**
     *      0
     *    1   2 
     *  3 4  5 6
     */
    heapifyTargetItem(index) {
        const left = index * 2 + 1;
        const right = index * 2 + 2;
        let max = index;
        if (left < this.arr.length && this.arr[left] > this.arr[max]) {
            max = left;
        }
        if (right < this.arr.length && this.arr[right] > this.arr[max]) {
            max = right;
        }
        if (max !== index) {
            [this.arr[index], this.arr[max]] = [this.arr[max], this.arr[index]];
            this.heapifyTargetItem(max);
        }
    }
    heapify() {
        for (let i = Math.floor(this.arr.length / 2); i >= 0; i--) {
            this.heapifyTargetItem(i);
        }
    }
    pop () {
        return this.arr.pop();
    }
    shift () {
        return this.arr.shift()
    }
    unsift (val) {
        this.arr.unshift(val);
    }

}

const heapSort = (arr) => {
    const heap = new Heap(arr);
    heap.heapify();
    let res = [];
    while (heap.arr.length) {
        res.push(heap.shift());
        if(heap.arr.length===0) break;
        heap.unsift(heap.pop());
        heap.heapifyTargetItem(0);
    }
    return res;
}

const arr = [3,-1,7,5,1414]

console.log(heapSort(arr));

优先队列 ​

ts
class PriorityQueue<T> {
    private heap: { priority: number; value: T }[] = [];
  
    public enqueue(value: T, priority: number): void {
      this.heap.push({ value, priority });
      this.bubbleUp(this.heap.length - 1);
    }
  
    public dequeue(): T | undefined {
      const max = this.heap[0];
      const end = this.heap.pop();
  
      if (this.heap.length > 0) {
        this.heap[0] = end!;
        this.bubbleDown(0);
      }
  
      return max?.value;
    }
  
    public size(): number {
      return this.heap.length;
    }
  
    private bubbleUp(index: number): void {
      const element = this.heap[index];
  
      while (index > 0) {
        const parentIndex = Math.floor((index - 1) / 2);
        const parent = this.heap[parentIndex];
  
        if (element.priority <= parent.priority) {
          break;
        }
  
        this.heap[parentIndex] = element;
        this.heap[index] = parent;
        index = parentIndex;
      }
    }
  
    private bubbleDown(index: number): void {
      const element = this.heap[index];
      const length = this.heap.length;
  
      while (true) {
        const leftChildIndex = 2 * index + 1;
        const rightChildIndex = 2 * index + 2;
        let leftChild, rightChild;
        let swap = null;
  
        if (leftChildIndex < length) {
          leftChild = this.heap[leftChildIndex];
          if (leftChild.priority > element.priority) {
            swap = leftChildIndex;
          }
        }
  
        if (rightChildIndex < length) {
          rightChild = this.heap[rightChildIndex];
          if (
            (swap === null && rightChild.priority > element.priority) ||
            (swap !== null && rightChild.priority > leftChild!.priority)
          ) {
            swap = rightChildIndex;
          }
        }
  
        if (swap === null) {
          break;
        }
  
        this.heap[index] = this.heap[swap];
        this.heap[swap] = element;
        index = swap;
      }
    }
  }
  
  // Example usage
  const pq = new PriorityQueue<string>();
  pq.enqueue("A", 3);
  pq.enqueue("B", 10);
  pq.enqueue("C", 1);
  console.log(pq.dequeue()); // Output: "A"
  console.log(pq.dequeue()); // Output: "B"
  console.log(pq.dequeue()); // Output: "C"

快速排序 ​

js
const quickSort = (arr) => {
    if (arr.length <= 1) return arr;
    const pivot = arr[0];
    const left = [];
    const right = [];
    for (let i = 1; i < arr.length; i++) {
        if (arr[i] < pivot) left.push(arr[i]);
        else right.push(arr[i]);
    }
    return [...quickSort(left), pivot, ...quickSort(right)];
}