狗家新鲜面经

蠡口原题更简单的形式变种：

您好！
本帖隐藏的内容需要积分高于 180 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 180 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

求加大米！谢谢！

请问一下楼主，这题用O（N^4）的暴力解可以过吗？

1. class Solution {
   
2. public:
   
3.     int countCornerRectangles(vector<vector<int>>& grid) {
   
4.         int m = grid.size(), n = grid[0].size(), res = 0;
   
5.         for (int i = 0; i < m; ++i) {
   
6.             for (int j = 0; j < n; ++j) {
   
7.                 if (grid[i][j] == 0) continue;
   
8.                 for (int h = 1; h < m - i; ++h) {
   
9.                     if (grid[i + h][j] == 0) continue;
   
10.                     for (int w = 1; w < n - j; ++w) {
    
11.                         if (grid[i][j + w] == 1 && grid[i + h][j + w] == 1) ++res;
    
12.                     }
    
13.                 }
    
14.             }
    
15.         }
    
16.         return res;
    
17.     }
    
18. };

复制代码

crazycodyman 发表于 2019-8-2 16:52
请问一下楼主，这题用O（N^4）的暴力解可以过吗？
[mw_shl_code=cpp,true]class Solution {
public:

会被要求优化到O(N^2 * M)

triangelfish 发表于 2019-8-3 00:21
会被要求优化到O(N^2 * M)

怎么优化呢

crazycodyman 发表于 2019-8-3 08:22
怎么优化呢

leetcode对应题的discussion区里有好多好的solution

积分不够 求问楼主蠡口题号！ 感谢！！！

workworkhard 发表于 2019-8-9 13:46
积分不够 求问楼主蠡口题号！ 感谢！！！

齐武灵         

triangelfish 发表于 2019-8-13 04:16
齐武灵

感谢楼主回复！！