Check If All 1’s Are at Least Length K Places Away
给一个数组, 里面是0和1, 求里面的1互相之间是否至少隔k个数.
Archive: April 28, 2021
Design Compressed String Iterator
设计一个runlength压缩后的string的iterator.
Count Binary Substrings
给一个binary的string, 求里面有多少个substring是有相同的个数1和0. 这个题直接就count, 然后sliding windows, 然后简化到了只需要记录不同的0 和1的group的最小的.
一个求乘法逆元的打表方法
前几天看到Neal_Wu的youtube视频中用的一个求INV11(对11的乘法逆元)在mod一个大数M下的方法. 视频链接: https://www.youtube.com/watch?v=8ukwV6rCvPg&t=367s 假设, 我们在11*i ≡ 1 mod 31中求i, 那么相当于我们在求一个x使得11 * ((x*31+1) / 11) ≡ 1 mod 31 where x∈[1,2,3,….]. 然后, 我们从1开始, 逐个试(x*31+1) % 11 ?= 0中的这个x是多少, 因为只有整除的x才是我们想要的. 这里我们从1一直试到6, 然后发现(6*31+1) % 11 = 0, 所以这里的(6*31+1) / 11 = 17的17就是INV11在模31下. 我们直接记录这个INV11可以减少运算时间. 这里的31是很小的数字, 有很多别的方法也可以求, 比如费马小定理, 但是如果是很大的数字就用这个比较省时间.