C++ Non-recursive O(n) time O(1) space solution


  • 0
    A

    First traverse the board horizontally once without checking sideways, then traverse the board vertically once without checking sideways, finally divide the total count by 2, and we are done.

    28 / 28 test cases passed
    Status: Accepted
    Runtime: 3 ms

    class Solution {
    public:
        int countBattleships(vector<vector<char>>& board) {
            int c = 0, h = board.size(), w = h ? board[0].size() : 0;
            for (uint i = 0; i < h; i++) {
                for (uint b = 0, j = 0; j < w; j++) {
                    if (board[i][j] == 'X') {
                        if (b) c--;
                        else c++;
                        b = 1;
                    } else b = 0;
                }
            }
            for (uint j = 0; j < w; j++) {
                for (uint b = 0, i = 0; i < h; i++) {
                    if (board[i][j] == 'X') {
                        if (b) c--;
                        else c++;
                        b = 1;
                    } else b = 0;
                }
            }
            return c/2;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.