steven026 发表于 2024-4-5 16:07
!(data/attachment/forum/202404/05/160636akgzflttlgta3flb.png)
在哥哥基础上优化了一 ...
他好像数据量不够
哥哥好歹比我多了百分之几呢~
我今天做斐波那契那个是最抽象的
https://leetcode.cn/submissions/detail/520274431/
一开始只超过了大概30%
我都怀疑人生了，还有人能超矩阵算得快
结果想想不对劲又掏出来跑了一遍，超过90%了
波动太大了
李恒道 发表于 2024-4-5 16:36
他好像数据量不够
哥哥好歹比我多了百分之几呢~
没错 同一段代码多次提交都会有很大波动
steven026 发表于 2024-4-5 16:38
没错 同一段代码多次提交都会有很大波动
要不要也来一天做两道
哥哥也开个挑战贴
李恒道 发表于 2024-4-5 16:41
要不要也来一天做两道
哥哥也开个挑战贴
我算法不太行……毕竟我只是个文科生 都没学过高数 呜呜呜{:4_105:}
李恒道 发表于 2024-4-5 15:54
我也不知道为啥
最近突然对lc感兴趣了
求算法方案二维数组两点间最短路径
https://bbs.tampermonkey.net.cn/thread-3778-1-1.html
(出处: 油猴中文网)
简单的DP，不如哥哥秒了吧，悬赏一直没结{:4_111:}
steven026 发表于 2024-4-5 21:07
求算法方案二维数组两点间最短路径
https://bbs.tampermonkey.net.cn/thread-3778-1-1.html
(出处: 油猴 ...
等我再学一学de
呜呜呜
李恒道 发表于 2024-4-5 16:32
题虽然是简单题，但是打法不是简单题打法的
两数相加证明了区间范围单调性才写的收缩
可以，ggnb
https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked
复杂度N，提供数据，需要排查最长连续
立刻想到了堆排序建堆N删除LogN
直接抄一个小根堆https://frenchleave.cn/blog/pages/articles/algorithm/javascriptshi-xian-zui-xiao-dui-he-zui-da-dui.html#%E6%A6%82%E5%BF%B5
然后按顺序秒，确定好边界就ok
```js
class MinHeap {
constructor(data) {
if (Array.isArray(data)) {
this.heap = data.slice();
if (this.heap.length > 1) {
this.heapify();
}
} else {
this.heap = [];
}
}
insert(value) {
this.heap.push(value);
this.shiftUp(this.heap.length - 1);
}
pop() {
if (this.size() === 0) return null;
if (this.size() === 1) {
return this.heap.pop();
}
const data = this.heap;
this.heap = this.heap.pop();
this.shiftDown(0);
return data;
}
peek() {
return this.heap;
}
size() {
return this.heap.length;
}
getParentIndex(i) {
return (i - 1) >> 1;
}
getLeftIndex(i) {
return i * 2 + 1;
}
getRightIndex(i) {
return i * 2 + 2;
}
swap(i1, i2) {
const temp = this.heap;
this.heap = this.heap;
this.heap = temp;
}
shiftUp(index) {
if (index === 0) {
return;
}
const parentIndex = this.getParentIndex(index);
// 如果比父节点值小 那么执行交换
if (this.heap > this.heap) {
this.swap(parentIndex, index);
// 把父节点处的值继续执行上滑操作
this.shiftUp(parentIndex);
}
}
shiftDown(index) {
const leftIndex = this.getLeftIndex(index);
let j = leftIndex;
if (leftIndex < this.size()) {
// j + 1 表示右孩子节点 找到左右子节点最小的那个
if (j + 1 < this.size() && this.heap < this.heap) {
j++;
}
// 父节点与最小的子节点交换
if (this.heap > this.heap) {
this.swap(j, index);
// 把最小子节点处的值继续执行下滑操作
this.shiftDown(j);
}
}
}
// 将初始数组整理成堆
heapify() {
for (
let index = this.getParentIndex(this.size() - 1);
index >= 0;
index--
) {
this.shiftDown(index);
}
}
}
var longestConsecutive = function (nums) {
if(nums.length===0){
return 0
}
const heap = new MinHeap(nums);
let item = heap.pop();
let maxContinues = 1;
let finalContinus = maxContinues;
while (item !== null) {
temp = heap.pop();
if (temp == item + 1) {
maxContinues++;
} else {
finalContinus = Math.max(finalContinus, maxContinues);
if (temp !== item) {
maxContinues = 1;
}
}
item = temp;
}
return finalContinus;
};
```
官方题解是利用将全部都塞到Set去重
然后扣每一个最低连续数的边界
这样最差情况是O(2N)
```js
var longestConsecutive = function (nums) {
let numSet = new Set(nums)
let longestStreak = 0;
for (let num of numSet) {
if (!numSet.has(num - 1)) {
let currentNum = num
let currentStreak = 1;
while (numSet.has(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}
longestStreak = Math.max(longestStreak, currentStreak)
}
}
return longestStreak
};
```
https://leetcode.cn/problems/move-zeroes/?envType=study-plan-v2&envId=top-100-liked
找到元素就寻找下一个不为0的交换
由于可能存在00001的间隔
所以可以利用位置累计
中规中矩的打法
```js
var moveZeroes = function (nums) {
let noZeroIndex = 0;
for (let index = 0; index < nums.length; index++) {
let num = nums;
if (num === 0) {
for (
let indey = Math.max(noZeroIndex, index + 1);
indey < nums.length;
indey++
) {
const num = nums;
if (num !== 0) {
noZeroIndex = indey;
const temp = nums;
nums = nums;
nums = temp;
break;
}
}
}
}
return nums;
};
```
