Solution C++ (one pass, no extra space)


  • 0
    C

    Solution without using extra memory, and in a single pass:

    class Solution {
    public:
        int countBattleships(vector<vector<char>>& board) {
            int ships = 0, rows = board.size();
            for(int i=0; i< rows; i++){
                int cols = board[i].size();
                for(int j = 0 ; j < cols; j++){
                    if(board[i][j] == 'X'){
                        if(left(board, i,j) != 'X' && top(board,i,j) != 'X'){
                            ships++;
                        }
                    }
                }
            }
            return ships;
        }
    private:
        char left(vector<vector<char> >& board, int r, int c){
           if(c == 0){
               return 'N';
           }
            else {
                return board[r][c-1];
            }
        }
        
        char top(vector<vector<char> >& board, int r, int c){
           if(r == 0){
               return 'N';
           }
            else {
                return board[r-1][c];
            }
        }
    
    };
    

Log in to reply
 

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