专栏首页算法修养LeetCode 1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

LeetCode 1292. Maximum Side Length of a Square with Sum Less than or Equal to Threshold

题目

我是按照边进行二分的

class Solution {
public:
    int sum[100005];
    
    int a[305][305];
    int maxSideLength(vector<vector<int>>& mat, int threshold) {
        
        if(threshold==0)
            return 0;
        int n = mat.size(); 
        int m = mat[0].size();
        
        int len = min(n,m);
        
        for(int i=0;i<=len;i++)
        {
            sum[i]=99999999;
        }
        
        a[0][0] = mat[0][0];
        for(int j=1;j<m;j++)
        {
            a[0][j] = mat[0][j]+a[0][j-1]; 
            
        }
        
        for(int i=1;i<n;i++)
        {
            a[i][0]=mat[i][0]+a[i-1][0];
        }
        
        for(int i=1;i<n;i++)
        {
            for(int j=1;j<m;j++)
            {
                a[i][j] = a[i-1][j]+a[i][j-1]+mat[i][j] -a[i-1][j-1];
            }
        }
        
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                for(int k=0;k<len;k++)
                {
                    int x=99999999;
                    if(i-k<0||j-k<0)
                        continue;
                    if(k==0)
                    {
                        x = mat[i][j];
                    }
                    else
                    {
                        x=a[i][j];
                        if(i-k-1>=0)
                        {
                            x = x-a[i-k-1][j];
                        }
                        if(j-k-1>=0)
                        {
                            x = x-a[i][j-k-1];
                        }
                        if(i-k-1>=0&&j-k-1>=0)
                        {
        
                            x = x+a[i-k-1][j-k-1];
                        }
                       
                    }
                    
                    if(x<=threshold)
                    {
                        sum[k+1] = min(sum[k+1],x);
                    }
                }
            }
        }
        
        int start = 1;
        int end = len;
        
        int ans=-1;
        
        while(start<=end)
        {
            int mid = (start + end)/2;
            
            if(sum[mid]>threshold)
            {
                end = mid-1;
            }
            
            if(sum[mid]<threshold)
            {
                start = mid+1;
            }
            
            if(sum[mid]==threshold)
            {
                ans=mid;
                break;
            }
        }
        
        if(ans==-1)
        {
            if(sum[end]>threshold)
                ans=0;
            else
                ans=end;
        }
        return ans;
        
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2016天梯模拟赛 进阶题解

    L2-005 集合相似度 题目链接: https://www.patest.cn/contests/gplt/L2-005 题目的意思是要求两个集合的交集中...

    ShenduCC
  • 天梯赛 大区赛 L3-014.周游世界 (Dijkstra)

    L3-014. 周游世界 时间限制 200 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standar...

    ShenduCC
  • POJ-1088 滑雪 (记忆化搜索,dp)

    滑雪 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 86318 ...

    ShenduCC
  • 最大子段和问题

    问题描述: 给定长度为n的整数序列,a[1...n], 求[1,n]某个子区间[i , j]使得a[i]+…+a[j]和最大,或者求出最大的这个和。如果该序列的...

    我没有三颗心脏
  • 初级程序员面试不靠谱指南(三)

    二、指针的好基友的& 1.&的意义。说&是指针的好基友其实不恰当,因为&这个符号在C/C++不止有一种含义,但是因为其经常会和指针一起出现在被问的问题列表上,所...

    一心一怿
  • 计蒜客2018 蓝桥杯省赛 B 组模拟赛(一)

    Zoctopus
  • LeetCode 75. Sort Colors题目分析

    给定一个包含红,白,蓝且长度为 n 的数组,将数组元素进行分类使相同颜色的元素相邻,并按照红、白、蓝的顺序进行排序。 我们可以使用整数 0,1 和 2 分别代...

    desperate633
  • 数码管问题(c++实现)

        描述:液晶数码管用七笔阿拉数字表示的十个数字,把横和竖的一 个短划都称为一笔,即7有3笔,8有7笔等。对于十个数字一种排列,要做到  两相邻数字都可以由...

    用户2038589
  • 挖掘机技术哪家强(c++实现)

    描述:为了用事实说明挖掘机技术到底哪家强,组织一场挖掘机技能大赛。现请你根据比赛结果统计出技术最强的那个学校。

    用户2038589
  • 剑指Offer-构建乘积数组

    package Array; import sun.security.util.Length; /** * 构建乘积数组 * 给定一个数组A[0,1,....

    武培轩

扫码关注云+社区

领取腾讯云代金券