Shortest Path to Get Food
给一个2d数组, 找两个格子之间的步数.
给一个2d数组, 找两个格子之间的步数.
给一个数组, 从0开始,问最大多少.
给一个string, 只移除k次重复的substring. 这个题因为要多次移除, 还有merge的可能, 所以要用stack存一下前序, 我是用Pair先预处理了一下string, 把string换成词频格式, 然后再用stack. 其实也可以不用pair, 直接算.
给一个grid里面是0和1, 求最大面积的1. 典型的搜索问题. 用-1标visitied.
给一个2d数组, 里面全是1和0, 里面的row是按照升序排列的. 给一个api, 需要调这个api求最左边第一次出现1的列. 这个一看就是二叉.
给一个无限大的棋盘(2d数组), 在0,0有一个马, 马走日, 求到x,y的步数 这个就是搜索问题. 因为无限大, 所以只能是bfs, 稍微剪枝一下就可以, 不过我的答案虽然过了, 但是好慢啊.
给一个无向图, 求几个强连通组件. 并查集的例题.
给一个数组, 里面的数字不同, 求多少种a*b=c*d, abcd都是数组的数字, 但是不相同. 算下乘积的频率即可, 答案是n*(n-1),从频率中任意选2个的个数, 然后再乘以4, 4种互换可能.
给一个0和1的二维矩阵, 求最大的全1子矩阵(不一定是square). 这个题首先观察例子, 发现肯定有排序, 然后再看一遍能看出来扫描可以通过查找连续1的个数来判断, 所以划分为一个个子问题, 即: 当扫完一行的时候, 如何计算当前的最大全是1的area. 我们需要先找到当前从上到下最多连续1的个数, 然后排序(greedy)后乘以当前的index后取最大.
给一个数字n, 求[1, n]的一个序列满足除了1以外的数组出现2次, 1 出现1次. 并且要求字典序最大的数组. 这个题试了几种规律, 发现如果n是奇数, 则第二位可放n-2, 依次递减, 然后再放偶数. 但是发现这种也有漏洞. 因为1只能放一次, 所以不好判断1最后的位置, 这会影响字典序的大小, 所以最后用的广搜实现的.