本站服务

图像识别
LeetCode刷题技巧
零碎知识 算法基础 0 164

题型整理

  • 双指针:
    1. 同向逆向的选择: 是否要保持原顺序
  • 二分查找
    1. 基本原则:
      1. 每次都要缩减搜索区域
      2. 每次缩减不能排除潜在答案
    2. 注意事项:
      1. 求mid避免溢出: l + (r - l) / 2
      2. 边界条件:
        1. l与r的关系
        2. l/r与mid的关系
    3. 解题模版
      • 找一个准确值(找到4)
        • 循环条件: l <= r
        • 缩减搜索空间: l = mid + 1, r = mid - 1
      • 找一个模糊值(比4大的最小数、比4小的最大数)
        • 循环条件: l < r
        • 缩减搜索空间: l = mid, r = mid - 1 或者 l = mid + 1, r = mid
      • 万用型(最接近4的数)
        • 循环条件: l < r - 1
        • 缩减搜索空间: l = mid, r = mid
        • 需要处理搜索到边界的情况
  • 链表
    1. 常见思路:
      1. 双指针
      2. 递归
    2. 注意事项:
      1. 使用"哨兵"(Sentinel)，避免特殊情况的讨论: dummyNode
  • 栈
    1. 注意事项:
      1. 使用Deque<Integer> stack = new ArrayDeque<Integer>()创建接口更全面，性能更好的栈对象
  • 堆
    1. 注意事项:
      1. maxHeap还是minHeap
    2. 常见场景:
      1. 第k个...
  • 哈希表
    1. 注意事项:
      1. Array与HashMap: 速度与开销的权衡
  • 树的BFS
    1. 注意事项:
      1. queue的初始状态
  • 树的DFS
    1. 解题模版:
      • 基础模版
        1. Base Case
        2. DoSomething()
        3. Recurse for subproblems
      • Top Down DFS: 把值通过参数的形势从上往下传；无返回值
        1. Base Case
        2. 利用父问题传下来的值做一些计算
        3. 若有必要，做一些额外操作
        4. 把值传下去给子问题继续递归
      • Bottom Up DFS(更难也更常见): 把值从下(subproblem)往上传；当前递归层利用subproblem传上来的值计算当前层的新值并返回；一定会有返回值
        1. Base Case
        2. 向子问题要答案(return value)
        3. 利用子问题的答案构建当前问题(当前递归层)的答案
        4. 若有必要，做一些额外操作
        5. 返回答案(给父问题)
    2. 注意事项:
      • 相信自己的递归是对的
  • 图的BFS
    1. 解题模版
      1. Initialize a Queue with all starting.points, a HashSet to record visited nodes
      2. While queue is not empty
        1. Retrieve current queue size as number of nodes in the current level
        2. for each node in current level
          1. Poll out one node
          2. If this is the node we want, return it
          3. Offer all its neighbor to the queue f not visited and valid
      3. Increase level
    2. 注意事项
      1. 二维图(Matrix)可以预先定义方向: int[][] dirs = new int[][] { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };，但需要注意边界
  • 图的Best-First Search
    1. 使用场景: 针对Non-uniform cost graph的一种算法，核心思想是优先展开最"优"的节点
    2. 解题模版:
      1. Initialize a Heap with all starting points marked with some initial costs， a HashSet to record visited nodes
      2. While heap is not empty a. Poll out one node b. If it has already been expanded （visited）， skip it c. Otherwise mark the node as visited, update its cost d. If this is the destination node, return e. For all of its neighbors, offer them in to the heap hode's cost + edge cost
  • 图的DFS
    1. 解题模版:
      1. Initialize HashSet to record visited nodes
      2. For all entry nodes, call dfs():
        1. Validate current node, if visited or invalid or answer node, return(无环就可以去掉这步)
        2. Do Something(Pre-order)
        3. For each neighbor node:
          1. Validate neighbor node， if visited or invalid or answer node, don't recurse on it Or return answer
          2. Recurse down on neighbor node 一 dfs(neighbor)
        4. Do Something （Post-order）
  • 动态规划
    1. 整体思路:
      1. 搜索: 当—个大问题是由多个子问题构成时，我们可以通过不断分解问题来最终构建我们想求的大问题。这个过程称为搜索(Search)。
      2. 如果我们Search Space有重复子问题的话，可以记录下这些子问题的答案来保证不会重复计算多次。所以DP也被称为Search + Memoization。
      3. 所有的DP都可以写成Bottom Up DFS的形式。
    2. 解题模版:
      • 通用:
      • 2D的状态：
        1. 2D Array -> state = (row, col)
        2. 2 1D Arrays -> Each 1D state
        3. 1D Array -> 2D state (subarray)
        4. 1D Array + K -> state = (i, k)
    3. 核心问题: 定义好状态，从中间状态出发，递归求解
    4. 视频资料:
  • 回溯:
    1. 使用场景:
    2. 解题模版: (属于Top Down DFS)
      1. Base Case
      2. For each possibility p
        1. Memorize current state
        2. backtrack(next state)
        3. Restore current state

其他技巧

  1. 浮点数计算:
    1. 运算结果取整要注意【ans+1/ans/ans-1】
    2. 可用上fabs控制精度
  2. 注意特定类型的取值范围【避免溢出】
    • 乘法可能超出边界，用除法代替【需要考虑除零】
    • l + (r - l) / 2
编写
预览