Skip to content

Instantly share code, notes, and snippets.

@jk195417
Last active February 19, 2024 16:02
Show Gist options
  • Save jk195417/be34e53fca423ba82dcf5ff52a61a980 to your computer and use it in GitHub Desktop.
Save jk195417/be34e53fca423ba82dcf5ff52a61a980 to your computer and use it in GitHub Desktop.
leetcode 1642
class LinkNode<TValue> {
value: TValue;
prev: LinkNode<TValue> | null;
next: LinkNode<TValue> | null;
constructor(value: TValue) {
this.value = value;
}
}
interface IPrioryQueue {
get head(): LinkNode<number> | null;
get tail(): LinkNode<number> | null;
enqueue(n: number): void;
peekMin(): number | undefined;
dequeueMin(): number | undefined;
peekMax(): number | undefined;
dequeueMax(): number | undefined;
}
class PrioryQueue implements IPrioryQueue {
// asc, from head to tail
protected _head: LinkNode<number> | null = null;
get head(): LinkNode<number> | null {
return this._head;
}
protected _tail: LinkNode<number> | null = null;
get tail(): LinkNode<number> | null {
return this._tail;
}
enqueue(n: number): void {
const listNode = new LinkNode(n);
// first
if (this.head == null || this.tail == null) {
this._head = listNode;
this._tail = listNode;
return;
}
// new head
if (listNode.value <= this.head.value) {
this.head.prev = listNode;
listNode.next = this.head;
this._head = listNode;
return;
}
// new tail
if (listNode.value >= this.tail.value) {
this.tail.next = listNode;
listNode.prev = this.tail;
this._tail = listNode;
return;
}
const diffWithHead = listNode.value - this.head.value;
const diffWithTail = this.tail.value - listNode.value;
// close to head
if (diffWithHead <= diffWithTail) {
let pointer = this.head;
while (pointer.next != null) {
if (
pointer.value <= listNode.value &&
listNode.value <= pointer.next.value
) {
listNode.next = pointer.next;
listNode.prev = pointer;
pointer.next.prev = listNode;
pointer.next = listNode;
return;
}
pointer = pointer.next;
}
pointer.next = listNode;
listNode.prev = pointer;
return;
}
// close to tail
if (diffWithTail < diffWithHead) {
let pointer = this.tail;
while (pointer.prev != null) {
if (
pointer.prev.value <= listNode.value &&
listNode.value <= pointer.value
) {
listNode.next = pointer;
listNode.prev = pointer.prev;
pointer.prev.next = listNode;
pointer.prev = listNode;
return;
}
pointer = pointer.prev;
}
pointer.prev = listNode;
listNode.next = pointer;
return;
}
// didn't fit any condition
throw new Error("enqueue error");
}
peekMin(): number | undefined {
return this.head?.value;
}
dequeueMin(): number | undefined {
if (this.head == null) return undefined;
const old = this.head;
const next = this.head.next;
if (next != null) next.prev = null;
this._head = next;
return old.value;
}
peekMax(): number | undefined {
return this.tail?.value;
}
dequeueMax(): number | undefined {
if (this.tail == null) return undefined;
const old = this.tail;
const prev = this.tail.prev;
if (prev != null) prev.next = null;
this._tail = prev;
return old.value;
}
}
type Constructor<T> = new (...args: any[]) => T;
function withSumming<T extends Constructor<IPrioryQueue>>(Base: T) {
return class Summable extends Base {
protected _sum: number = 0;
get sum(): number {
return this._sum;
}
enqueue(n: number): void {
super.enqueue(n);
this._sum += n;
}
dequeueMin(): number | undefined {
const min = super.dequeueMin();
this._sum -= min ?? 0;
return min;
}
dequeueMax(): number | undefined {
const max = super.dequeueMax();
this._sum -= max ?? 0;
return max;
}
};
}
function withCounting<T extends Constructor<IPrioryQueue>>(Base: T) {
return class Countable extends Base {
private _count: number = 0;
get count(): number {
return this._count;
}
enqueue(n: number): void {
super.enqueue(n);
this._count += 1;
}
dequeueMin(): number | undefined {
const min = super.dequeueMin();
if (min != null) this._count -= 1;
return min;
}
dequeueMax(): number | undefined {
const max = super.dequeueMax();
if (max != null) this._count -= 1;
return max;
}
};
}
// Mixin
const SuperPrioryQueue = withCounting(withSumming(PrioryQueue));
function furthestBuilding(
heights: number[],
bricks: number,
ladders: number
): number {
let sum = 0;
const pq = new SuperPrioryQueue();
for (let index = 0; index < heights.length; index++) {
if (index === 0) continue;
const currentHeight = heights[index];
const lastHeight = heights[index - 1];
const cost = currentHeight <= lastHeight ? 0 : currentHeight - lastHeight;
sum += cost;
pq.enqueue(cost);
if (pq.count > ladders) {
pq.dequeueMin();
}
if (bricks < sum - pq.sum) {
return index - 1;
}
}
return heights.length - 1;
}
function furthestBuilding2(
heights: number[],
bricks: number,
ladders: number
): number {
const result = heights.reduce(
(acc, current, index, array) => {
console.log(acc.pq);
if (index === 0) return acc;
if (acc.stopped) return acc;
const lastHeight = array[index - 1];
const cost = current <= lastHeight ? 0 : current - lastHeight;
acc.sum += cost;
acc.pq.enqueue(cost);
if (acc.pq.count > ladders) {
acc.pq.dequeueMin();
}
if (bricks >= acc.sum - acc.pq.sum) {
acc.furthest = index;
return acc;
}
acc.stopped = true;
return acc;
},
{
sum: 0,
pq: new SuperPrioryQueue(),
furthest: 0,
stopped: false,
}
);
return result.furthest;
}
class Heap<TValue> {
store: TValue[] = [];
get size() {
return this.store.length;
}
// if true, parent stays in parent, child stays in child
// if false, parent need to swap with child
private compareFn: (parent: TValue, child: TValue) => boolean;
constructor(compareFn: (a: TValue, b: TValue) => boolean) {
this.compareFn = compareFn;
}
enqueue(n: TValue): void {
this.store.push(n);
this.heapifyUp(this.store.length - 1);
}
dequeue(): TValue | undefined {
if (this.store.length === 0) return undefined;
const head = this.store.shift();
if (this.store.length === 0) return head;
const tail = this.store.pop()!;
this.store.unshift(tail);
this.heapifyDown(0);
return head;
}
private heapifyUp(currentIndex: number) {
if (currentIndex === 0) return;
const parentIndex =
currentIndex % 2 === 1 ? (currentIndex - 1) / 2 : (currentIndex - 2) / 2;
const targetIndex = this.compareIndex(parentIndex, currentIndex);
if (targetIndex == null) return;
if (targetIndex === parentIndex) return;
this.swap(currentIndex, parentIndex);
this.heapifyUp(parentIndex);
}
private heapifyDown(currentIndex: number) {
const leftIndex = currentIndex * 2 + 1;
const rightIndex = currentIndex * 2 + 2;
const childIndex = this.compareIndex(leftIndex, rightIndex);
if (childIndex == null) return;
const targetIndex = this.compareIndex(currentIndex, childIndex);
if (targetIndex == null) return;
if (targetIndex === currentIndex) return;
this.swap(currentIndex, targetIndex);
this.heapifyDown(targetIndex);
}
private compareIndex(aIndex: number, bIndex: number): number | null {
const a = this.store[aIndex];
const b = this.store[bIndex];
if (a == null && b == null) return null;
if (a == null) return bIndex;
if (b == null) return aIndex;
return this.compareFn(a, b) ? aIndex : bIndex;
}
private swap(aIndex: number, bIndex: number): void {
const a = this.store[aIndex];
const b = this.store[bIndex];
this.store[aIndex] = b;
this.store[bIndex] = a;
}
}
function furthestBuilding(
heights: number[],
bricks: number,
ladders: number
): number {
const result = heights.reduce(
(acc, current, index, array) => {
if (index === 0) return acc;
if (acc.stopped) return acc;
const lastHeight = array[index - 1];
const cost = current <= lastHeight ? 0 : current - lastHeight;
if(cost === 0) {
acc.furthest = index;
return acc;
}
acc.sum += cost;
acc.heap.enqueue(cost);
acc.heapSum += cost;
if (acc.heap.size > ladders) {
const min = acc.heap.dequeue()!;
acc.heapSum -= min;
}
if (bricks >= acc.sum - acc.heapSum) {
acc.furthest = index;
return acc;
}
acc.stopped = true;
return acc;
},
{
sum: 0,
heap: new Heap<number>((a, b) => a <= b),
heapSum: 0,
furthest: 0,
stopped: false,
}
);
return result.furthest;
}
class PrioryQueueArray {
// asc
private store: number[] = [];
enqueue(n: number): void {
let inserted = false;
for (const [i, e] of this.store.entries()) {
if (n <= e) {
this.store.splice(i, 0, n);
inserted = true;
break;
}
}
if (inserted) return;
this.store.push(n);
}
peekMin(): number | undefined {
return this.store[0];
}
dequeueMin(): number | undefined {
return this.store.shift();
}
peekMax(): number | undefined {
return this.store[this.store.length - 1];
}
dequeueMax(): number | undefined {
return this.store.pop();
}
}
function furthestBuilding(
heights: number[],
bricks: number,
ladders: number
): number {
const prioryQueue = new PrioryQueueArray();
for (const [i, e] of heights.entries()) {
if (i === 0) continue;
const prev = heights[i - 1];
const cost = prev >= e ? 0 : e - prev;
// using nothing
if (cost === 0) continue;
// using ladder
if (ladders > 0) {
ladders -= 1;
prioryQueue.enqueue(cost);
continue;
}
const min = prioryQueue.peekMin();
// using ladder for now, replace old ladder by bricks
if (min != null && cost > min && bricks >= min) {
prioryQueue.dequeueMin();
prioryQueue.enqueue(cost);
bricks -= min;
continue;
}
// using bricks
if (bricks >= cost) {
bricks -= cost;
continue;
}
// can't go further
return i - 1;
}
return heights.length - 1;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment