Menu Sidebar
Menu

January 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后取最大.

Construct the Lexicographically Largest Valid Sequence

给一个数字n, 求[1, n]的一个序列满足除了1以外的数组出现2次, 1 出现1次. 并且要求字典序最大的数组. 这个题试了几种规律, 发现如果n是奇数, 则第二位可放n-2, 依次递减, 然后再放偶数. 但是发现这种也有漏洞. 因为1只能放一次, 所以不好判断1最后的位置, 这会影响字典序的大小, 所以最后用的广搜实现的.

Older Posts

书脊

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