Count Number of Teams
给一个数组, 找到有多少组的i,j,k使得ary[i] < ary[j] < ary[k]. 这题就o(n^2)的查找就能过.
April 2021
Minimum Add to Make Parentheses Valid
给一个string, 里面是括号, 求最少添加几个括号, 让string valid. 用stack跟踪string的左括号. 最后stack的大小就是答案
Count Substrings with Only One Distinct Letter
给一个String, 问里面多少个substring只有一个不同的字符. 首先一个string, 比如aaaaa, 那么里面的只有一个不同字符的是n*(n+1) / 2个子string. 然后找就行了.
Array Transformation
给一个数组, 让简单的变化一下.
Surface Area of 3D Shapes
给一个2d数组, 里面是数字是当前坐标的叠着的正方体数, 求一共多少个面. 这个题就是弄清楚两个正方体分享一个面, 所以计算的时候要先比较相邻正方体的高矮, 然后减去矮的部分共享的面数即可. 然后数组值可能为0(没有正方体)
Check If All 1’s Are at Least Length K Places Away
给一个数组, 里面是0和1, 求里面的1互相之间是否至少隔k个数.
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是很小的数字, 有很多别的方法也可以求, 比如费马小定理, 但是如果是很大的数字就用这个比较省时间.
Sum of Digits in Base K
给一个数字, 求基数为k的digits的和.