刚刚字节跳动一道题
二维数组
1 2 3
4 5 6
7 8 9
10 11 12
(3,3) - (2,2)即5+6+8+9
(4,3) - (2,2)即5+6+8+9+11+12
求(x1,y1)-(x2,y2),不能遍历
dp,大家有什么好的方法吗,大矩形减三个小矩形吗?
百度没搜到
#字节跳动##笔试题目##秋招#
关注
全部评论
Jonariguez
拼多多_算法工程师
dp[i,j]表示左上角是(1,1)，右下角是(i,j)的矩形的和，然后dp[x1,y1]-dp[x1,y2 -1]-dfp[x2 -1,y1]+dp[x2 -1,y2 -1]就可以了，可以O(1)
loongll
北京邮电大学
二维前缀和
Jonariguez
拼多多_算法工程师
反正还是矩形减减加加呗😂
lovelyy
东南大学 后端
这不就是我实习的题么，上面那个老哥的答案就是对的
相关推荐
投递腾讯等公司10个岗位
02-12 14:04
北京交通大学 大数据开发工程师 
准备进厂的劳伦斯很迷人：小学时候有个册子 自评 小组 老师 我谦虚打了个b 小组别人给我打b 老师来句我觉得能给他打a 但是小组长说他自评是b怎么能打高呢 那时候我才明白的道理 点赞 评论 收藏
分享