https://leetcode.cn/submissions/detail/588897066/
这个题真的是凹了好久，写的太脏了
```js
class MaxHeap {
constructor(comparator = (a, b) => a - b) {
this.heap = [];
this.comparator = comparator;
}
// 获取父节点索引
parentIndex(index) {
return Math.floor((index - 1) / 2);
}
// 获取左子节点索引
leftChildIndex(index) {
return 2 * index + 1;
}
// 获取右子节点索引
rightChildIndex(index) {
return 2 * index + 2;
}
// 交换两个节点
swap(index1, index2) {
const temp = this.heap;
this.heap = this.heap;
this.heap = temp;
}
// 向堆中插入元素
insert(value) {
this.heap.push(value);
this.heapifyUp();
}
// 堆化上移
heapifyUp() {
let index = this.heap.length - 1;
while (index > 0 && this.comparator(this.heap, this.heap) > 0) {
this.swap(index, this.parentIndex(index));
index = this.parentIndex(index);
}
}
// 移除堆顶元素
extractMax() {
if (this.heap.length === 0) return null;
if (this.heap.length === 1) return this.heap.pop();
const max = this.heap;
this.heap = this.heap.pop();
this.heapifyDown(0);
return max;
}
// 堆化下移
heapifyDown(index) {
let largest = index;
const left = this.leftChildIndex(index);
const right = this.rightChildIndex(index);
if (left < this.heap.length && this.comparator(this.heap, this.heap) > 0) {
largest = left;
}
if (right < this.heap.length && this.comparator(this.heap, this.heap) > 0) {
largest = right;
}
if (largest !== index) {
this.swap(index, largest);
this.heapifyDown(largest);
}
}
// 获取堆顶元素
peek() {
return this.heap.length > 0 ? this.heap : null;
}
// 获取堆的大小
size() {
return this.heap.length;
}
}
// 示例使用
var ExamRoom = function (n) {
this.n = n
this.seats = {};
this.left = {};
this.right = {};
const getDistance = (l, r) => {
if (l == -1) {
return r
} else if (r == n) {
return n - l - 1
} else {
return Math.floor(((r - l) / 2))
}
}
this.maxHeap = new MaxHeap((a, b) => {
const d1 = getDistance(a, a);
const d2 = getDistance(b, b);
if (d1 == d2) {
return b - a
}
return d1 - d2
}); // 默认比较器，构建最大堆
this.maxHeap.insert([-1, n])
};
/**
* @Return {number}
*/
ExamRoom.prototype.seat = function () {
const n = this.n
const = this.maxHeap.extractMax()
if (l == -1 && !this.seats && (this.seats || r == n)) {
this.seats = true;
this.left = -1;
this.right = r;
this.left = 0;
if (r - 1 !== 0) {
this.maxHeap.insert()
}
return 0
} else if (r == n && !this.seats && (this.seats || l == -1)) {
this.seats = true;
this.left = l;
this.right = n;
this.right = n - 1;
if (n - 1 - 1 != l) {
this.maxHeap.insert()
}
return n - 1
} else if (this.seats && this.seats) {
const center = Math.floor((l + r) / 2)
if (this.seats) {
return this.seat()
}
this.seats = true;
this.left = l;
this.right = r;
this.right = center;
this.left = center;
if (center - 1 != l) {
this.maxHeap.insert();
}
if (r - 1 != center) {
this.maxHeap.insert();
}
return center
}
return this.seat()
};
/**
* @param {number} p
* @return {void}
*/
ExamRoom.prototype.leave = function (p) {
this.seats = false;
const l = this.left;
const r = this.right;
if (r !== this.n) {
this.left = l
}
if (l !== -1) {
this.right = r
}
this.maxHeap.insert(, this.right]);
};
```
https://leetcode.cn/submissions/detail/588930611/
堆+贪心问题
```js
class MaxHeap {
constructor(comparator = (a, b) => a - b) {
this.heap = [];
this.comparator = comparator;
}
// 获取父节点索引
parentIndex(index) {
return Math.floor((index - 1) / 2);
}
// 获取左子节点索引
leftChildIndex(index) {
return 2 * index + 1;
}
// 获取右子节点索引
rightChildIndex(index) {
return 2 * index + 2;
}
// 交换两个节点
swap(index1, index2) {
const temp = this.heap;
this.heap = this.heap;
this.heap = temp;
}
// 向堆中插入元素
insert(value) {
this.heap.push(value);
this.heapifyUp();
}
// 堆化上移
heapifyUp() {
let index = this.heap.length - 1;
while (
index > 0 &&
this.comparator(this.heap, this.heap) > 0
) {
this.swap(index, this.parentIndex(index));
index = this.parentIndex(index);
}
}
// 移除堆顶元素
extractMax() {
if (this.heap.length === 0) return null;
if (this.heap.length === 1) return this.heap.pop();
const max = this.heap;
this.heap = this.heap.pop();
this.heapifyDown(0);
return max;
}
// 堆化下移
heapifyDown(index) {
let largest = index;
const left = this.leftChildIndex(index);
const right = this.rightChildIndex(index);
if (
left < this.heap.length &&
this.comparator(this.heap, this.heap) > 0
) {
largest = left;
}
if (
right < this.heap.length &&
this.comparator(this.heap, this.heap) > 0
) {
largest = right;
}
if (largest !== index) {
this.swap(index, largest);
this.heapifyDown(largest);
}
}
// 获取堆顶元素
peek() {
return this.heap.length > 0 ? this.heap : null;
}
// 获取堆的大小
size() {
return this.heap.length;
}
}
/**
* @param {number[]} apples
* @param {number[]} days
* @Return {number}
*/
var eatenApples = function (apples, days) {
const maxHeap = new MaxHeap((a, b) => {
return b.day - a.day;
});
let nextDay = 0;
let total = 0;
for (let index = 0; index < apples.length; index++) {
maxHeap.insert({ num: apples, day: index + days });
while (maxHeap.size() !== 0) {
const obj = maxHeap.extractMax();
if (obj.day > nextDay && obj.num > 0) {
maxHeap.insert({ num: obj.num - 1, day: obj.day });
total++;
break;
}
}
nextDay++;
}
while (maxHeap.size() !== 0) {
const obj = maxHeap.extractMax();
if (obj.day > nextDay && obj.num > 0) {
maxHeap.insert({ num: obj.num - 1, day: obj.day });
total++;
nextDay++;
}
}
return total;
};
```
https://leetcode.cn/problems/balanced-binary-tree/submissions/588931291/
爽一题收工
```js
var isBalanced = function (root) {
let ans = true;
const dfs = (node) => {
if (node == null) {
return 0;
}
const l = dfs(node.left);
const r = dfs(node.right);
if (Math.abs(l - r) > 1) {
ans = false;
}
return Math.max(l, r) + 1;
};
dfs(root)
return ans
};
```
https://leetcode.cn/problems/minimum-cost-for-cutting-cake-i/submissions/589239949/
贪心太难凹了
看了一眼答案用了缓存dp，一次过
```js
var minimumCost = function (m, n, horizontalCut, verticalCut) {
const cache = new Map()
const dfs = (x, y, xLen, yLen) => {
const tag = `${x} ${y} ${xLen} ${yLen}`
if (cache.has(tag)) {
return cache.get(tag)
}
if (xLen == 1 && yLen == 1) {
return 0
}
let ans = Number.MAX_SAFE_INTEGER;
for (let index = 1; index < xLen; index++) {
ans = Math.min(ans, dfs(x, y, index, yLen) + dfs(x + index, y, xLen - index, yLen) + horizontalCut)
}
for (let index = 1; index < yLen; index++) {
ans = Math.min(ans, dfs(x, y, xLen, index) + dfs(x, y + index, xLen, yLen - index) + verticalCut)
}
cache.set(tag,ans)
return ans
}
return dfs(0, 0, m, n)
};
```
https://leetcode.cn/problems/minimum-cost-for-cutting-cake-ii/submissions/589244396/
贪心好神奇
```js
/**
* @param {number} m
* @param {number} n
* @param {number[]} horizontalCut
* @param {number[]} verticalCut
* @Return {number}
*/
var minimumCost = function(m, n, horizontalCut, verticalCut) {
horizontalCut.sort((a, b) => b - a);
verticalCut.sort((a, b) => b - a);
h = 0;
v = 0;
vBlock = 1;
hBlock = 1;
ans = 0
while (h < horizontalCut.length && v < verticalCut.length) {
if (horizontalCut > verticalCut) {
hBlock++;
ans += horizontalCut * vBlock
h++
} else {
vBlock++;
ans += verticalCut * hBlock
v++
}
}
while (h < horizontalCut.length) {
hBlock++;
ans += horizontalCut * vBlock
h++
}
while (v < verticalCut.length) {
vBlock++;
ans += verticalCut * hBlock
v++
}
return ans
};
```
https://leetcode.cn/problems/word-search-ii/submissions/589248008/?envType=study-plan-v2&envId=top-interview-150
树+dfs过了，感觉不像困难
```js
var findWords = function (board, words) {
const tree = {}
function insert(str) {
let node = tree
for (let index = 0; index < str.length; index++) {
const char = str;
if (node == undefined) {
node = {}
}
node = node
}
node.end = true
node.str = str
}
for (let index = 0; index < words.length; index++) {
insert(words)
}
const ans = {}
const dfs = (x, y, node) => {
if (x < 0 || y < 0 || x >= board.length || y >= board.length) {
return
}
const char = board
if (node !== undefined) {
if (node.end) {
ans.str] = true
}
board=-1
dfs(x + 1, y, node)
dfs(x - 1, y, node)
dfs(x, y + 1, node)
dfs(x, y - 1, node)
board=char
}
}
for (let index = 0; index < board.length; index++) {
for (let indey = 0; indey < board.length; indey++) {
dfs(index, indey, tree)
}
}
return Object.keys(ans);
};
```
https://leetcode.cn/problems/existence-of-a-substring-in-a-string-and-its-reverse/submissions/589358515/
打卡题
秒了
```js
var isSubstringPresent = function (s) {
const cache = new Map();
let lastChar = s
for (let index = 1; index < s.length; index++) {
const char = s;
let str = lastChar + char
cache.set(str, (cache.get(str) ?? 0) + 1)
lastChar=char
}
lastChar = s
for (let index = s.length - 2; index >= 0; index-- ){
const char = s;
let str = lastChar + char
if(cache.has(str)){
return true
}
lastChar=char
}
return false
};
```
https://leetcode.cn/problems/sign-of-the-product-of-an-array/submissions/589358721/?envType=study-plan-v2&envId=programming-skills、
来个垃圾题
```go
func arraySign(nums []int) int {
ret:=1
for i := 0; i < len(nums); i++ {
num:=nums
if num<0{
ret=ret*-1
}else if num==0{
return 0
}else{
ret=ret*1
}
}
return ret
}
```
https://leetcode.cn/problems/find-occurrences-of-an-element-in-an-array/submissions/589615937/
感觉这是简单题吧
```js
var occurrencesOfElement = function (nums, queries, x) {
const find = [];
for (let index = 0; index < nums.length; index++) {
const num = nums;
if (num == x) {
find.push(index);
}
}
const ans=[]
for (let index = 0; index < queries.length; index++) {
ans.push(find-1]??-1)
}
return ans
};
```
https://leetcode.cn/problems/integer-to-roman/submissions/589619025/?envType=study-plan-v2&envId=top-interview-150
罗马就是这么灭亡的！
```js
const numList = ;
const charList = [
"M",
"CM",
"D",
"CD",
"C",
"XC",
"L",
"XL",
"X",
"IX",
"V",
"IV",
"I",
];
var intToRoman = function (num) {
let pos = 0;
let ans = "";
while (num !== 0) {
if (num >= numList) {
ans += charList;
num-=numList
} else {
pos++;
continue;
}
}
return ans;
};
```