Menu Sidebar
Menu

Archive: January 19, 2021

Minimum Knight Moves

给一个无限大的棋盘(2d数组), 在0,0有一个马, 马走日, 求到x,y的步数 这个就是搜索问题. 因为无限大, 所以只能是bfs, 稍微剪枝一下就可以, 不过我的答案虽然过了, 但是好慢啊.

Tuples with Same Product

给一个数组, 里面的数字不同, 求多少种a*b=c*d, abcd都是数组的数字, 但是不相同. 算下乘积的频率即可, 答案是n*(n-1),从频率中任意选2个的个数, 然后再乘以4, 4种互换可能.

Largest Submatrix With Rearrangements

给一个0和1的二维矩阵, 求最大的全1子矩阵(不一定是square). 这个题首先观察例子, 发现肯定有排序, 然后再看一遍能看出来扫描可以通过查找连续1的个数来判断, 所以划分为一个个子问题, 即: 当扫完一行的时候, 如何计算当前的最大全是1的area. 我们需要先找到当前从上到下最多连续1的个数, 然后排序(greedy)后乘以当前的index后取最大.

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.