拼多多笔试

第二题是求1的个数,那个大佬做出来了,分享一波思路呀#笔试题目##拼多多#
全部评论
个人思路: 1.首先统计所有1的数量one_count,发现矩阵全部是1,直接返回矩阵size;全部是0,返回0 2.否则说明有士兵,也有空位可以供士兵移动。对每一个0,可以尝试把一个1换到这个位置,dfs搜索该区域,更新ans 3.如果最终ans比所有1的数量one_count还多1,说明填充的1是凭空填充的,填充后原来所有的1会联通。这时直接返回step1中统计的1的数量one_count,否则返回ans 结果:部分超时 原因分析:对于不同的0,可能连接了同一区域内不同位置的1,从而对同一区域进行了多次dfs搜索,产生了重复计算。参考别人的做法,可以对每块区域先记录连通数量,避免重复计算
1 回复
分享
发布于 2020-09-02 08:47
算人数的时候,8邻域聚类,但是挪士兵的思路没想好,暴力复杂度太大了
点赞 回复
分享
发布于 2020-09-02 09:05
联易融
校招火热招聘中
官网直投

相关推荐

点赞 评论 收藏
转发
点赞 2 评论
分享
牛客网
牛客企业服务