search

Alice52 / algorithms

This repository is for learning Algorithms.
https://programmercarl.com/
0 stars 0 forks source link

[daily] 2021-08-31 #158

Closed Alice52 closed 3 years ago

Alice52 commented 3 years ago

  1. reference

  2. discription

    • 三角形最小路径和

  3. core

    • DP
    • dp[i][j] 选到i行j个元素时的最优解
      • [i-1][j] 过来的 || 或者 [i-1][j-1] 过来的
      • f(i)(j) = Math.min{f(i-1)(j), f(i-1)(j-1)} + num[i]
      • 注意[0][0] + [i][0] + [i][j] 的赋值和初始化问题

  1. reference

  2. discription

    • 在排序数组中查找元素的第一个和最后一个位置

  3. core

    • 二分查找分别查找 left 和 right
  1. reference
  2. discription
    • 在 D 天内送达包裹的能力

  3. core

    • 二分查找应用题
    • x: 求什么什么就是 x, 所以运载能力是x
    • f(x) 是在 x 运载能力下运完的天数
    • x与f(x) 的关系: 单调递减
    • [8, 5, 2, 2, 1] 所以时求left 边界
    • 注意 left={max(array)} 和 right{sum(array)} 的初始值问题
  1. reference
  2. discription
    • 爱吃香蕉的珂珂

  3. core

    • 二分查找应用题
    • x: 求什么什么就是 x, 所以吃香蕉的速度是x
    • f(x) 是在 x 速度下吃完所有香蕉的时间
    • x与f(x) 的关系: 单调递减
    • [8, 5, 2, 2, 1] 所以时求left 边界

  1. reference

  2. discription

    • 山脉数组的峰顶索引

  3. core

    • 二分查找
    • <= + == => right=mid-1; + left)