/leetcode

Primary LanguageRustApache License 2.0Apache-2.0

leetcode

目录

索引

解题提示

  • 动态规划。
    • 正着和倒着。
    • 状态转移方程很重要！
  • 双指针。
  • 滑动窗口。
  • 堆。
    • 用堆解决 topN 的问题。
  • 二分。
    • 二分时如果出现 left = mid 或者 right = mid 时就要小心了，可能会出现死循环。
    • 计算 mid 时如果用 mid = (left + right)/2，那么 left + right 可能会溢出，所以题解中都是用 mid = left + (right - left) / 2. 其中的区间是 [left, right]。
  • 分治：（什么是分治：分治法是将整个数组切分成几个小组，然后每个小组再切分成几个更小的小组，一直到不能继续切分也就是只剩一个数字为止。每个小组会计算出最优值，汇报给上一级的小组，一级一级汇报，上级拿到下级的汇报找到最大值，得到最终的结果。和归并排序的算法类似，先切分，再合并结果。）

复杂度的计算

递推式 $T(n) = 2 \cdot T(n/2) + O(n)$, 根据主定理，$T(n) = O(n \log n)$.

比如说 「109. 有序链表转换二叉搜索树」，长度为 n 的链表，寻找中位数用时 $O(n)$，然后再拆分成两个 n/2 规模的子树。

递推式 $T(n) = 2 \cdot T(n/2) + O(1)$，根据主定理，$T(n) = O(n)$。