【当前无排名】挑战leetcode进入前1w名

李恒道

steven026 发表于 2024-4-5 16:07
[md]
在哥哥基础上优化了一 ...

他好像数据量不够
哥哥好歹比我多了百分之几呢~

我今天做斐波那契那个是最抽象的

https://leetcode.cn/submissions/detail/520274431/

一开始只超过了大概30%

我都怀疑人生了，还有人能超矩阵算得快

结果想想不对劲又掏出来跑了一遍，超过90%了

波动太大了

steven026

李恒道 发表于 2024-4-5 16:36
他好像数据量不够
哥哥好歹比我多了百分之几呢~

没错 同一段代码多次提交都会有很大波动

李恒道

steven026 发表于 2024-4-5 16:38
没错 同一段代码多次提交都会有很大波动

要不要也来一天做两道

哥哥也开个挑战贴

steven026

李恒道 发表于 2024-4-5 16:41
要不要也来一天做两道

哥哥也开个挑战贴

我算法不太行……毕竟我只是个文科生 都没学过高数 呜呜呜

steven026

李恒道 发表于 2024-4-5 15:54
我也不知道为啥

最近突然对lc感兴趣了

求算法方案二维数组两点间最短路径
https://bbs.tampermonkey.net.cn/thread-3778-1-1.html
(出处: 油猴中文网)

简单的DP，不如哥哥秒了吧，悬赏一直没结

李恒道

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

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[0];
    this.heap[0] = this.heap.pop();
    this.shiftDown(0);
    return data;
  }

  peek() {
    return this.heap[0];
  }

  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[i1];
    this.heap[i1] = this.heap[i2];
    this.heap[i2] = temp;
  }

  shiftUp(index) {
    if (index === 0) {
      return;
    }
    const parentIndex = this.getParentIndex(index);
    // 如果比父节点值小 那么执行交换
    if (this.heap[parentIndex] > this.heap[index]) {
      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[j + 1] < this.heap[j]) {
        j++;
      }
      // 父节点与最小的子节点交换
      if (this.heap[index] > this.heap[j]) {
        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)

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的间隔
所以可以利用位置累计

中规中矩的打法

var moveZeroes = function (nums) {
  let noZeroIndex = 0;
  for (let index = 0; index < nums.length; index++) {
    let num = nums[index];
    if (num === 0) {
      for (
        let indey = Math.max(noZeroIndex, index + 1);
        indey < nums.length;
        indey++
      ) {
        const num = nums[indey];
        if (num !== 0) {
          noZeroIndex = indey;
          const temp = nums[noZeroIndex];
          nums[noZeroIndex] = nums[index];
          nums[index] = temp;
          break;
        }
      }
    }
  }
  return nums;
};