→ show6669: 可以去xxxxhub上課了 03/19 15:22
→ cuteSquirrel: 有阿 有個數學老師就這樣做 後來成功做起來了 03/19 15:23
→ cuteSquirrel: 他現在台灣 中國都有品牌 做網路教學 03/19 15:24
→ cuteSquirrel: 旗下也有別的老師加盟 03/19 15:24
→ TKB5566: 松鼠想要進軍IT產業嗎？ 03/19 16:56
打鐵秤熱
趁現在點子剛蹦出來的時候先記錄下來
二分搜尋 觀念與框架
最普通的二分搜尋: 找目標值
實作上的細節，用靜態型別的語言，必須留意 left + right / 2 不可以發生整數溢位
overflow
在個細節在guess number 互動題就有被考到
python沒事 是因為python的整數是無窮精度支援。
C/C++/Java ...等 就必須改用比較安全的寫法 left + (right-left) / 2
衍伸變化
找目標值第一次出現的位置
類推就變成 找滿足條件satisfy(...)的第一個位置
找目標值最後一次出現的位置
類推就變成 找滿足條件satisfy(...)的最後一個位置
最佳化
當目標函數f(x) 具有嚴格遞增、或嚴格遞減性質的時候
相當於f(x)以排序，因此可以用 binary search來找滿足條件的某個位置
當f(x) 具有單一一個最小值 或 最大值，
也可以用 比較的性質，來找f(x) 高峰或低谷。
※ 引述《cuteSquirrel (可愛的小松鼠)》之銘言：
: 滑動窗口
: Sliding window
: 有點像空間精簡版的前綴和
: ==========================
: prefix sum 很愛考的一個觀念
: S 和 S-k 存在，代表必定存在有總和為k的區間
: 這個在樹形DP也看的到
: 前綴和另一個經典應用，就是區間求和
: 1D Range Sum
: 2D Range Sum
: 進階應用就是後來電腦視覺的影像區塊和 搭配filter之後 抽取feature
: ※ 引述《cuteSquirrel (可愛的小松鼠)》之銘言：
: : DFS + backtracking 也完成 第一部曲
: : 這個領域滿大的
: : 之後還可以托展到Combination sum 相關，和
: : 經典的 八皇后擺放 和 Sudoku解數獨的演算法。
: : 再想想看怎麼安排內容和順序比較流暢。
: : 之後如果講memoization ，那 DFS + memo 又可以和等價的DP串在一起了
: : 彼此等價互通
: : 想法也對稱，由上到下 和 由下到上 都可以。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.37.176.206 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/talk/M.1710832782.A.2E0.html