No nine
題目敘述
給你一個區間 $[a, b]$，保證端點都 valid，要你求取區間中 valid 的數字個數。
所謂 valid 的數字，他要符合
- 該數字沒有包含9 e.g. 1可以, 191不行
- 該數字並非9的倍數 e.g. 1可以, 18不行
思路
我們可以如何排除包含9的數字呢？用九進位來看！
試想，如果把 $[0, 26)$ 這個區間的所有數字都列出來，你會刪掉的數字分別是 $9, 19$。誒，這不就是 $[0, 26)$ 用九進位來看會自動排除掉的數字嗎？利用這個性質，我們可以很簡單的獲得區間內數字個數了！
排除了包含九的數字後，九的倍數怎麼辦？傷為觀察一下就有囉！
560. Subarray Sum Equals K
把 prefix sum 放在 map 裡面！
312. Burst Balloons
Cutting stick! From bottom to top!
316. Remove Duplicate Letters
好題。