牛牛的木板

题解

写法一:
我们先做一次前缀和
然后暴力枚举所有片段,判断这一段里黑色块数量时候小于m,小于则记录答案。时间复杂度

写法二
我们考虑使用队列来模拟一下。
假设我们现在有一段(L--R)的木板
假设R+1是白色 我们可以直接拓展
假设R+1是黑色 我们可以通过洗刷一次使其变成白色 然后拓展
但是如果已经没有机会洗刷了呢?
这意味着R无法拓展了,我们只能考虑放弃L的位置 使L向L+1拓展。
因为这样才会有新贡献的可能,于是我们可以通过队列来模拟这个过程。双指针也是可以的。
时间复杂度

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param m int整型 
     * @param a int整型vector 
     * @return int整型
     */
    int solve(int n, int m, vector<int>& a) {
        // write code here
        int cnt=0,ans=0;
        queue<int>q;
        for (int i=0; i<n; i++)
        {
            if (a[i]==1)
            {
                q.push(1);
                int sz=q.size();
                ans=max(ans,sz);
            }
            else
            {
                q.push(0);
                cnt++;
                while (cnt>m)
                {
                    int x=q.front();
                    if (x==0) cnt--;
                    q.pop();
                }
            }
        }
        return ans;
        }
};
全部评论

相关推荐

头像
04-27 15:11
已编辑
华东师范大学 算法工程师
暑期实习从2月开始投,面了两个月,流程该挂的都挂完了,腾讯字节一共号称是1.7w个hc,不知道都发给谁了,估计今年秋招要难顶。Timeline米哈游、美团、蚂蚁、微软等公司直接简历挂穿,没进面。携程:3.3&nbsp;投递、测评3.12&nbsp;笔试3.18&nbsp;一面3.25&nbsp;二面4.13&nbsp;ai面(hr面)4.14&nbsp;英语测评4.23&nbsp;offer(已拒)腾讯:2.6&nbsp;测评2.28&nbsp;wxg一面3.5&nbsp;wxg二面(挂)3.11&nbsp;teg一面3.21&nbsp;teg二面(取消)3.31&nbsp;teg一面4.10&nbsp;teg二面(挂)4.21&nbsp;wxg一面4.24&nbsp;wxg二面(挂)字节:1.28&nbsp;aml约面(取消)3.17&nbsp;火山一面(挂)4.8&nbsp;aml一面(挂)4.20&nbsp;抖音data一面(挂)阿里:3.23&nbsp;投递、测评3.28&nbsp;笔试3.31&nbsp;淘天一面4.8&nbsp;钉钉一面4.9&nbsp;淘天二面4.10&nbsp;阿里控股一面4.12&nbsp;钉钉二面(取消)4.15&nbsp;淘天hr面4.16&nbsp;淘天offer(已接)4.21&nbsp;高德一面(取消)4.22&nbsp;淘宝闪购一面(取消)面试最大的感触是,现在撞上ai转型,一堆老业务急着转向,新业务非常不成熟,研究型的组bar非常高根本进不去,业务侧挂着算法的岗位干的都是工程活,面试却又要问算法,另外agent的落地也远没有那么广,绝大多数还是那套写死的系统调一下llm&nbsp;api或者做做rag,其余少部分真的在搭agent的,基本不能在线上服务用什么很智能的模型,现阶段成本太高,进去大概率就是给垃圾模型从工程方面兜底,除了业务场景的应用和数据经验以外,技术方面很难有什么提升。算法岗做不了基模的还是去搜广推好,之前判断失误了完全没投,秋招不知道还进不进得去。
紫炁:一样的感受,现在很混乱尤其业务侧开发和算法界限模糊,不知道秋招投哪个方向了
我的求职进度条
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务