首页 > 代码库 > 562. Longest Line of Consecutive One in Matrix
562. Longest Line of Consecutive One in Matrix
This is an easy question. No matter what kind of method you chose, the time complexity is at least O(m*n), becasue you have to traverse each element at least once. Here, we have a straight forward method without any maps...
class Solution { public: int longestLine(vector<vector<int>>& M) { if (M.empty()) return 0; int result = 0; int cur = 0; for (int i = 0; i < M.size(); i++) { cur = 0; for (int j = 0; j < M[i].size(); j++) { if (M[i][j]) cur++; else cur = 0; result = max(result, cur); } } for (int j = 0; j < M[0].size(); j++) { cur = 0; for (int i = 0; i < M.size(); i++) { if (M[i][j]) cur++; else cur = 0; result = max(result, cur); } } //int my = M.size(), mx = M[0].size(); for (int j = -(int)M.size(); j < (int)M[0].size(); j++) { cur = 0; for (int i = 0; i < M.size(); i++) { if (j + i < 0 || i + j >= M[0].size()) continue; else { if (M[i][j + i]) cur++; else cur = 0; result = max(result, cur); } } } for (int j = 0; j < M[0].size() + M.size(); j++) { cur = 0; for (int i = 0; i < M.size(); i++) { if (j - i < 0 || j - i >= M[0].size()) continue; else { if (M[i][j - i]) cur++; else cur = 0; result = max(result, cur); } } } return result; } };
Pay attention to the third for-loop. Because the return value of size() is size_type, an unsigned value, when you make some operations with int, be very careful about bugs, especially when the value is minus.
562. Longest Line of Consecutive One in Matrix
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。