leetcode动态规划系列题解之二

    科技2022-07-11  92

    leetcode动态规划系列题解之二

    leetcode750角矩形的数量题目大意解题思路暴力求解优化方法一:采用同时遍历两行,在同一列上判断其交点是否为1进行求解

    leetcode750角矩形的数量

    题目大意

    解题思路

    暴力求解

    暴力破解思路如下: 1、先确定左上角的顶点,从左到右遍历行列数(行数假设为m,列数假设为n),此时确定一个矩形的左上角的顶点。记录该顶点为(i, j)。 2、以(i, j)为矩形的左上角顶点,从j+1遍历到n,如果点为0,则继续,如果为1,则进行下一步。假设为1的点为(i,k)。 3、以(i, j)为矩形的左上角顶点,从i+1遍历到m-i,如果遍历到的点为0,则继续,如果为1,则进行下一步。假设为1的点为(p,j)。 4、以(i, j)为矩形的左上角顶点,从j+1遍历到n-j,如果遍历到的点为0,则继续,如果为1,则矩形数量增加1。此时为1的点为(p,k)。 5、重复1-4,直至遍历完成。 该种暴力算法,用C++编写可以AC,Python提交超时。

    优化方法一:采用同时遍历两行,在同一列上判断其交点是否为1进行求解

    该题解题思路如下: 1、同时遍历两行,固定其中一行(i行),另一行从i+1行开始遍历,并初始化ct=0 2、从左往右开始进行列遍历,如果两行和当前列的所有交点都是1,此时计数ct+1 3、此时,ct即为交点均为1的数字情况,此时矩形数量为ct*(ct-1)/2。逐次累加就好。

    Python可以AC:

    Processed: 0.013, SQL: 8