首页 > 代码库 > LeetCode "419. Battleships in a Board"
LeetCode "419. Battleships in a Board"
The follow-up question is fun: "Could you do it in one-pass, using only O(1) extra memory and without modifying the value of the board?"
When we meet an ‘X‘, we need to check if it is vertical or horizontal: they will never happen at the same time, by problem statement. For horizontal, we simply stripe through right, and plus 1 - however, if our top element is ‘X‘ already, it is a vertical and counter has alread been increased.
class Solution {public: int countBattleships(vector<vector<char>>& board) { int h = board.size(); if (!h) return 0; int w = board[0].size(); if (!w) return 0; int cnt = 0; for(int i = 0; i < h; i ++) for(int j = 0; j < w; j ++) { if(board[i][j] == ‘X‘) { // is it a counted vertical case? if(!(i > 0 && board[i -1][j] == ‘X‘)) { cnt ++; // Horizontal while(j < (w - 1) && board[i][j + 1] == ‘X‘) j ++; } } } return cnt; }};
LeetCode "419. Battleships in a Board"
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。