单调队列及应用

单调队列

单调队列是一种优先队列,要求元素是可排序的,或传入比较器。单调队列继承队列的以下性质:

  • 可从队尾插入元素。
  • 可从队头弹出元素。
  • 在队列中的所有元素里,队头元素一定是最早插入的。在队列中的所有元素里,队尾元素一定是最晚插入的。(FIFO)

单调队列有以下特[……]

继续阅读

126. Word Ladder II

LeetCode是用C# release模式运行的。

解法1:

使用队列进行广度优先搜索,统一在Dequeue后进行终止条件判断。

缺点是生成下一个状态,enqueue前,没有检查是不是解。

using System;
using System.Collections.Ge[......]

继续阅读

如何在图中新增一条边,使任意两点的距离之和最小?

游戏《太阳帝国的原罪》里,瓦萨里种族可以建造相位跳跃稳定器,飞船可以直接从一个有相位跳跃稳定器的星球跳跃到另一个有相位跳跃稳定器的星球,无需现有路线。

如图1,粉色是我的星球。如何添加两个相位跳跃稳定器,能够最大程度地减少我方飞船在各个星球之间的飞行距离?

把上图数学化,如图2,[……]

继续阅读

Manacher最长回文算法

本文将一步一步构造Manacher算法,心急的一定看不懂!请先练习下面的习题。

探索最长回文串性质

题1:已知字符串以center为中心对称,求完整的字符串。

abcd???
   |
center

abcdcba
   |
center

题2:接上题,a[……]

继续阅读