https://leetcode.cn/problems/median-of-two-sorted-arrays/submissions/562723857/?envType=study-plan-v2&envId=top-100-liked
这题是真做不出来
思路太巧妙了
看了答案自己写一遍都感觉骚，边界卡了我一下午
```js
var findMedianSortedArrays = function (nums1, nums2) {
const getRankK = (nums1, start1, nums2, start2, rank) => {
const len1 = nums1.length - start1;
const len2 = nums2.length - start2;
if (len1 > len2) {
return getRankK(nums2, start2, nums1, start1, rank)
}
if (len1 == 0) {
return nums2
}
if (rank == 1) {
return Math.min(nums1, nums2)
}
k = Math.floor(rank / 2)
k = Math.min(k, len1)
const num1 = nums1;
const num2 = nums2;
if (num1 > num2) {
return getRankK(nums1, start1, nums2, start2 + k, rank - k)
} else {
return getRankK(nums1, start1 + k, nums2, start2, rank - k)
}
}
const len = nums1.length + nums2.length
const floor = Math.floor(len / 2)
if (len % 2 == 0) {
return (getRankK(nums1, 0, nums2, 0, floor) + getRankK(nums1, 0, nums2, 0, floor + 1)) / 2
} else {
return getRankK(nums1, 0, nums2, 0, floor + 1)
}
};
```
https://leetcode.cn/problems/decode-string/submissions/562738091/?envType=study-plan-v2&envId=top-100-liked
堆栈题，秒
```js
var decodeString = function (s) {
s = s.split("")
const stack = []
const handleCycle = () => {
let str = ""
let char = stack.pop()
do {
str = char+str
char = stack.pop()
} while (char !== '[');
let cycleNum = ""
while (stack.length !== 0) {
const code = stack.charCodeAt()
if (code >= 48 && code <= 57) {
cycleNum = stack.pop() + cycleNum
} else {
break;
}
}
cycleNum = parseInt(cycleNum)
let result = ''
for (let index = 0; index < cycleNum; index++) {
result += str
}
stack.push(result)
}
for (const char of s) {
if (char === ']') {
handleCycle()
} else {
stack.push(char)
}
}
return stack.join("")
};
```
https://leetcode.cn/problems/largest-rectangle-in-histogram/submissions/562851106/?envType=study-plan-v2&envId=top-100-liked
这题基本看不懂
没理解定理的问题
一个最大的矩形一定是某一高度的矩形
同时边界卡在最后低于该高度的柱
实际上理解了光是扣边界就花了一晚上...
```js
var largestRectangleArea = function (heights) {
const stack = []
let maxArea = Number.MIN_SAFE_INTEGER
heights.unshift(0)
heights.push(0)
for (let index = 0; index < heights.length; index++) {
const height = heights;
while (stack.length != 0) {
const lastHeight = heights]
if (lastHeight <= height) {
break;
}
if (stack.length - 2 < 0) {
//边界
maxArea = Math.max(maxArea, lastHeight * (index))
stack.pop()
} else {
const leftHeight = heights]
if (leftHeight < lastHeight) {
maxArea = Math.max(maxArea, lastHeight * (index - 1 - stack))
stack.pop()
} else if (leftHeight == lastHeight) {
stack.pop()
} else {
break;
}
}
}
// if(stack.length!==0&&heights]===height){
// continue;
// }
stack.push(index)
}
for (let index = stack.length - 1; index >= 0; index--) {
const heightIdx = stack;
let leftIndex = stack ?? -1
if (heights == heights) {
continue;
}
const height = heights;
maxArea = Math.max(maxArea, height * (heights.length - leftIndex - 1))
}
return maxArea
};
```
https://leetcode.cn/problems/kth-largest-element-in-an-array/?envType=study-plan-v2&envId=top-100-liked
大小堆秒了
```js
class MaxHeadp {
heap
border
constructor(nums) {
this.heap = nums;
this.border = nums.length - 1
this.initHeap();
}
initHeap() {
const endIndex = this.getTopNode(this.border)
for (let index = endIndex; index >= 0; index--) {
this.downNode(index)
}
}
haveNum() {
return this.border + 1
}
pop() {
if (this.border === -1) {
return undefined
}
const temp = this.heap;
this.heap = this.heap;
this.border--;
this.downNode(0)
return temp
}
swap(x, y) {
let temp = this.heap
this.heap = this.heap
this.heap = temp
}
downNode(index) {
let left = this.getLeftNode(index);
let right = this.getRightNode(index);
while (left <= this.border || right <= this.border) {
let maxIndex = undefined
if (left <= this.border || right <= this.border) {
maxIndex = this.heap < this.heap ? right : left
} else {
maxIndex = left <= this.border ? right : left
}
if (this.heap < this.heap) {
this.swap(index, maxIndex)
index = maxIndex
left = this.getLeftNode(index);
right = this.getRightNode(index);
} else {
break;
}
}
}
getTopNode(index) {
return Math.floor((index - 1) / 2)
}
getLeftNode(index) {
return (index + 1) * 2 - 1
}
getRightNode(index) {
return (index + 1) * 2
}
}
var findKthLargest = function (nums, k) {
const heap = new MaxHeadp(nums)
let times = 0
let lastNum = undefined
while (heap.haveNum() != 0) {
const num = heap.pop()
if (num !== lastNum) {
times++
}
if (times == k) {
return num
}
}
return -1
};
```
https://leetcode.cn/problems/top-k-frequent-elements/?envType=study-plan-v2&envId=top-100-liked
复杂度N，改进大小堆秒了。..
```js
class MaxHeadp {
heap
border
compare
constructor(nums, compare) {
this.heap = nums;
this.border = nums.length - 1
this.compare = compare ?? ((a, b) => a < b)
this.initHeap();
}
initHeap() {
const endIndex = this.getTopNode(this.border)
for (let index = endIndex; index >= 0; index--) {
this.downNode(index)
}
}
haveNum() {
return this.border + 1
}
pop() {
if (this.border === -1) {
return undefined
}
const temp = this.heap;
this.heap = this.heap;
this.border--;
this.downNode(0)
return temp
}
insert() {
}
swap(x, y) {
let temp = this.heap
this.heap = this.heap
this.heap = temp
}
downNode(index) {
let left = this.getLeftNode(index);
let right = this.getRightNode(index);
while (left <= this.border || right <= this.border) {
let maxIndex = undefined
if (left <= this.border || right <= this.border) {
maxIndex = this.compare(this.heap, this.heap) ? right : left;
} else {
maxIndex = left <= this.border ? right : left
}
// if (this.heap < this.heap) {
if (this.compare(this.heap, this.heap)) {
this.swap(index, maxIndex)
index = maxIndex
left = this.getLeftNode(index);
right = this.getRightNode(index);
} else {
break;
}
}
}
getTopNode(index) {
return Math.floor((index - 1) / 2)
}
getLeftNode(index) {
return (index + 1) * 2 - 1
}
getRightNode(index) {
return (index + 1) * 2
}
}
var topKFrequent = function (nums, k) {
const map = new Map()
const newNums=[]
for (const num of nums) {
if (map.has(num)) {
map.set(num, map.get(num) + 1)
} else {
map.set(num, 1)
newNums.push(num)
}
}
const heap = new MaxHeadp(newNums,(a,b)=>{
return map.get(a)<map.get(b)
})
let times = 0
let lastNum = undefined
const result = []
while (heap.haveNum() != 0) {
const num = heap.pop()
if (num !== lastNum) {
times++
result.push(num)
}
if (times == k) {
return result
}
lastNum=num
}
return result
};
```
https://leetcode.cn/problems/find-median-from-data-stream/submissions/563588959/?envType=study-plan-v2&envId=top-100-liked
维护一个大根堆一个小根堆
剩下就是凑边界了
因为总是上的模板有点长
```js
class MaxHeadp {
heap;
border;
compare;
constructor(nums, compare) {
this.heap = nums;
this.border = nums.length - 1;
this.compare = compare ?? ((a, b) => a < b);
this.initHeap();
}
initHeap() {
const endIndex = this.getTopNode(this.border);
for (let index = endIndex; index >= 0; index--) {
this.downNode(index);
}
}
haveNum() {
return this.border + 1;
}
pop() {
if (this.border === -1) {
return undefined;
}
const temp = this.heap;
this.heap = this.heap;
this.border--;
this.downNode(0);
return temp;
}
peek() {
if (this.border === -1) {
return undefined;
}
return this.heap;
}
insert(num) {
this.border++;
if(this.border==this.heap.length){
this.heap.push(num);
}else{
this.heap=num
}
this.upNode(this.border);
}
swap(x, y) {
let temp = this.heap;
this.heap = this.heap;
this.heap = temp;
}
upNode(index) {
let top = this.getTopNode(index);
while (top !== -1 && this.compare(this.heap, this.heap)) {
this.swap(index, top);
index = top;
top = this.getTopNode(index);
}
}
downNode(index) {
let left = this.getLeftNode(index);
let right = this.getRightNode(index);
while (left <= this.border || right <= this.border) {
let maxIndex = undefined;
if (left <= this.border || right <= this.border) {
maxIndex = this.compare(this.heap, this.heap)
? right
: left;
} else {
maxIndex = left <= this.border ? right : left;
}
// if (this.heap < this.heap) {
if (this.compare(this.heap, this.heap)) {
this.swap(index, maxIndex);
index = maxIndex;
left = this.getLeftNode(index);
right = this.getRightNode(index);
} else {
break;
}
}
}
getTopNode(index) {
return Math.floor((index - 1) / 2);
}
getLeftNode(index) {
return (index + 1) * 2 - 1;
}
getRightNode(index) {
return (index + 1) * 2;
}
}
var MedianFinder = function () {
this.leftHeap = new MaxHeadp([]);
this.rightHeap = new MaxHeadp([], (a, b) => a > b);
// this.rightHeap.insert(-2)
// this.rightHeap.insert(-1)
// this.rightHeap.insert(-3)
};
/**
* @param {number} num
* @Return {void}
*/
MedianFinder.prototype.addNum = function (num) {
const center=this.findMedian()
if(num<center){
this.leftHeap.insert(num);
}else{
this.rightHeap.insert(num);
}
if (this.leftHeap.border - 1 > this.rightHeap.border) {
this.rightHeap.insert(this.leftHeap.pop());
}
if (this.rightHeap.border - 1 > this.leftHeap.border) {
this.leftHeap.insert(this.rightHeap.pop());
}
};
/**
* @return {number}
*/
MedianFinder.prototype.findMedian = function () {
const nums=this.leftHeap.border + this.rightHeap.border + 2
const isOne =
(nums) % 2 === 0 ? false : true;
if (isOne) {
return Math.floor(nums/2)<=this.leftHeap.border? this.leftHeap.peek():this.rightHeap.peek();
} else {
return ((this.leftHeap.peek() + this.rightHeap.peek()) / 2);
}
};
```
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/submissions/563593218/?envType=study-plan-v2&envId=top-100-liked
前缀和秒的
```js
var maxProfit = function (prices) {
const min = [];
let lastMin = Number.MAX_SAFE_INTEGER;
for (let index = 0; index < prices.length; index++) {
const price = prices;
min.push(lastMin);
lastMin = Math.min(lastMin, price);
}
let maxProfit = 0;
for (let index = 1; index < prices.length; index++) {
const price = prices;
maxProfit=Math.max(maxProfit,price-min)
}
return maxProfit;
};
```
https://leetcode.cn/problems/jump-game/submissions/563613612/?envType=study-plan-v2&envId=top-100-liked
递归秒的
方法应该是有问题了
擦边过的
```js
var canJump = function (nums) {
let status = false;
const jump = (pos) => {
if (pos == nums.length - 1) {
status = true;
return;
}
if (pos > nums.length - 1) {
return;
}
const times = Math.min(nums, nums.length - 1);
for (let index = 1;!status&& index <= times; index++) {
!status&&jump(pos + index);
}
nums = 0;
};
jump(0);
return status;
};
```
https://leetcode.cn/problems/jump-game-ii/submissions/563760469/?envType=study-plan-v2&envId=top-100-liked
会上一题的贪心思路了
靠变量缓存上一步秒了
```js
var jump = function (nums) {
if(nums.length==1){
return 0
}
let times = 1;
let lastMax = 0
let maxLength = nums;
while (maxLength < (nums.length - 1)) {
let newMax = maxLength;
times++;
for (let index = lastMax; index <= maxLength; index++) {
const num = nums;
newMax = Math.max(newMax, index + num)
}
if(newMax===maxLength){
return -1
}
lastMax = maxLength;
maxLength = newMax;
}
return times;
};
```
https://leetcode.cn/problems/longest-palindromic-substring/submissions/563817622/
dp秒的
但是复杂度很差
```js
var longestPalindrome = function (s) {
s = s.split("");
let l = 0, r = 0;
const arr = new Array(s.length)
for (let index = 0; index < arr.length; index++) {
arr = new Array(s.length).fill(false);
}
arr = true;
for (let index = 1; index < s.length; index++) {
arr = true;
arr = s === s;
if (arr) {
l = index - 1;
r = index
}
}
for (let index = s.length - 3; index >= 0; index--) {
for (let indey = index + 2; indey < s.length; indey++) {
if (s === s) {
arr = arr
if (arr&&(indey - index) > (r - l)) {
l = index;
r = indey
}
}
}
}
return s.slice(l,r+1).join("")
};
```