419. Battleships in a Board

Given an 2D board, count how many different battleships are in it. The battleships are represented with ‘X’s, empty slots are represented with ‘.’s. You may assume the following rules:

You receive a valid board, made of only battleships or empty slots.
Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.
At least one horizontal or vertical cell separates between two battleships – there are no adjacent battleships.
Example:
X..X
…X
…X
In the above board there are 2 battleships.
Invalid Example:
…X
XXXX
…X
This is an invalid board that you will not receive – as battleships will always have a cell separating between them.

思路: 找多少有多少条battleship,这个题目解法跟island题目完全相同。 用BFS或者DFS来遍历, 题目要求不准改动board的值,可以用个boolean的visited数组来解决;

public class Solution {
    private int[] xDir = new int[]{0, -1, 0, 1};
    private int[] yDir = new int[]{1, 0, -1, 0};

    public int countBattleships(char[][] board) {
        if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) return 0;
        int row = board.length;
        int col = board[0].length;
        int count = 0;
        boolean[][] visited = new boolean[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (!visited[i][j] && board[i][j] == 'X') {
                    countBattleships(board, visited, i, j);
                    count++;
                }
            }
        }
        return count;
    }

    public void countBattleships(char[][] board, boolean[][] visited, int x, int y) {
        if (x < 0 || y < 0 || x >= board.length || y >= board[0].length) return;
        if (board[x][y] == '.' || visited[x][y]) return;
        visited[x][y] = true;
        for (int i = 0; i < 4; i++) {
            int newX = x + xDir[i];
            int newY = y + yDir[i];
            countBattleships(board, visited, newX, newY);
        }
    }
}
Advertisements

130. Surrounded Regions

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

For example,
X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

思路: 用的BFS来做的, 先从边界条件寻找’O’, 把边界条件的O用BFS来找到的都不满足被X包围的条件,替换为’Y’,然后剩下图里的O 都满足被X包围的条件,直接替换为X; 最后再把边界的‘Y’替换回‘0’.

public class Solution {
    int[] xDir = new int[]{-1, 0, 1, 0};
    int[] yDir = new int[]{0, 1, 0, -1};
    public void solve(char[][] board) {
        if (board == null || board[0] == null 
         || board.length < 3 || board[0].length < 3 ) return;
        fillBoards(board, 'O', 'Y');
        solve(board, 'O', 'X');
        fillBoards(board, 'Y', 'O');
    }

    public void solve(char[][] board, char target, char c) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == target) {
                    board[i][j] = c;
                }
            }
        }
    }

    public void fill(char[][] board, int x, int y, char target, char c) {
        if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] != target) return;
        board[x][y] = c;
        for(int i = 0; i < 4; i++) {
            int newX = x + xDir[i];
            int newY = y + yDir[i];
            fill(board, newX, newY, target, c);
        }
    }

    public void fillBoards(char[][] board, char target, char c) {
        int row = board.length - 1;
        int col = board[0].length - 1;
        for (int i = 0; i <= row; i++) {
            if (board[i][0] == target) fill(board, i, 0, target, c);
            if (board[i][col] == target) fill(board, i, col, target,c);
        }

        for (int j = 0; j <= row; j++) {
            if (board[0][j] == target) fill(board, 0, j, target, c);
            if (board[row][j] == target) fill(board, row, j, target, c);
        }
    }


}

212. Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example,
Given words = [“oath”,”pea”,”eat”,”rain”] and board =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return [“eat”,”oath”].

思路: 如果用BFS来做的话,

复杂度: time 是MN26^L, space: 26^L, 用Trie来做, 先建立Trie树,把words添加到trie中,然后用BFS 去遍历board,找满足的点。 找的时候需要剪枝。

public class Solution {
    public int[] xDir = new int[]{-1, 0, 1, 0};
    public int[] yDir = new int[]{0, 1, 0, -1};
    public class TrieNode {
        HashMap<Character, TrieNode> children;
        boolean hasWord;
        public TrieNode() {
            this.children = new HashMap<Character, TrieNode>();
            this.hasWord = false;
        }
    }

    public class Trie {
        TrieNode root;
        public Trie() {
            root = new TrieNode();
        }
        public void insert(String word) {
            if (word == null || word.length() == 0) return;
            TrieNode current = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (!current.children.containsKey(c)) {
                    current.children.put(c, new TrieNode());
                }
                current = current.children.get(c);
            }
            current.hasWord = true;
        }

        public boolean search(String word) {
            if (word == null || word.length() == 0) return false;
            TrieNode current = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (!current.children.containsKey(c)) {
                    return false;
                }
                current = current.children.get(c);
            }
            return current.hasWord;
        }
    }


    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<>();
        if (board == null || board.length == 0 || board[0] == null || 
            board[0].length == 0 || words.length == 0 || words == null)
            return res;
        // build Trie tree
        Trie trie = new Trie();
        for (String word: words) {
            trie.insert(word);
        }
        StringBuilder sb = new StringBuilder();
        // search words in board
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                search(board, trie.root, i, j, res, sb);
            }
        }  
        return res;
    }

    public void search(char[][] board, TrieNode root, int x, int y, List<String> res, StringBuilder sb) {
        if (!isValid(board, x, y)) return;
        char c = board[x][y];
        TrieNode current = root.children.get(c);
        // check edge case
        if (c == '#' || current == null) return;
        sb.append(c);
        if (root.hasWord) { // check has a word
            res.add(sb.toString());
            root.hasWord = false;
        }

        board[x][y] = '#'; // pruning
        for (int k = 0; k < 4; k++) { // explore 4 directions
            int newX = x + xDir[k];
            int newY = y + yDir[k];
            search(board, current, newX, newY, res, sb);
        }
        sb.setLength(sb.length() - 1);
        board[x][y] = c;
    } 

    public boolean isValid(char[][] board, int x, int y) {
        if (x < 0 || x >= board.length || y < 0 || y>= board[0].length) return false;
        return true;
    }
}

127. Word LadderI/II

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the word list
For example,

Given:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,”dot”,”dog”,”lot”,”log”]
As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
return its length 5.

Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.

思路: 要求从初始单词到目标单词的最短路径, 要求每次只能变化每个单词的一个字母。 用BFS来解这道题目。 用一个hashmap来记录每个单词跟对应的距离. 用一个queue用来做bfs遍历。
BFS遍历过程: 1. 对queue进行poll操作拿到currentWord 2. 遍历currentWord的每个字符位置i, 同时对currentWord的每个位置上的字符进行’a’->’z’的替换,得到nextWord. 3. 先用endWord跟nextWord比较,如果相同,则找到,返回currentWord的长度+1. 如果不是endWord,如果满足wordList包含nextWord,同时hashMap中不存在这个nextWord,那么就将对应的nextWord存入hashMap,并放入queue。

复杂度: time O(n), space O(n)

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        if (beginWord == null || beginWord.length() == 0 || 
            endWord == null || endWord.length() == 0 || wordList.size() == 0) return 0;
        HashMap<String, Integer> dictMap = new HashMap<>();
        ArrayDeque<String> queue = new ArrayDeque<>();
        dictMap.put(beginWord, 1);
        queue.offer(beginWord);
        while(!queue.isEmpty()) {
            String currentWord = queue.poll();
            for (int i = 0; i < currentWord.length(); i++) {
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    StringBuilder sb = new StringBuilder(currentWord);
                    sb.setCharAt(i, ch);
                    String nextWord = sb.toString();
                    if (endWord.equals(nextWord)) {
                        return dictMap.get(currentWord) + 1;
                    }
                    if (wordList.contains(nextWord) && !dictMap.containsKey(nextWord)) {
                        dictMap.put(nextWord, dictMap.get(currentWord) + 1);
                        queue.offer(nextWord);
                    }
                }
            }
        }
        return 0;
    }
}

286.Walls and Gates

You are given a m x n 2D grid initialized with these three possible values.

-1 – A wall or an obstacle.
0 – A gate.
INF – Infinity means an empty room. We use the value 231 – 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

For example, given the 2D grid:
INF -1 0 INF
INF INF INF -1
INF -1 INF -1
0 -1 INF INF
After running your function, the 2D grid should be:
3 -1 0 1
2 2 1 -1
1 -1 2 -1
0 -1 3 4

思路: 求矩阵中room到gate的最短距离这个题目用DFS 比较快。
DFS: 找的时候如果当前点的值大于idx的值,就是符合条件的点。
复杂度: 时间 MN4^K, 空间 4^N

public class Solution {
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0 || rooms[0] == null || rooms[0].length == 0) return;
        for (int i = 0; i &lt; rooms.length; i++) {
            for (int j = 0; j &lt; rooms[0].length; j++) {
                if (rooms[i][j] == 0) {
                    dfs(rooms, i, j, 0);
                }
            }
        }
    }

    public void dfs(int[][] rooms, int x, int y, int idx) {
        if (x &lt; 0 || x &gt;= rooms.length || y &lt; 0 || y &gt;= rooms[0].length || rooms[x][y] &lt; idx) return;
        rooms[x][y] = idx;
        dfs(rooms, x + 1, y, idx + 1);
        dfs(rooms, x - 1, y, idx + 1);
        dfs(rooms, x, y + 1, idx + 1);
        dfs(rooms, x, y - 1, idx + 1);
    }
}

BFS的解

public class Solution {
    public class Point {
        int x;
        int y;
        int prevPos;
        public Point(int x, int y, int prevPos) {
            this.x = x;
            this.y = y;
            this.prevPos = prevPos;
        }
    }
    public int[] xDir = new int[]{-1, 0 , 1, 0};
    public int[] yDir = new int[]{0, 1, 0, -1};

    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0 || rooms[0] == null || rooms[0].length == 0) return;
        for (int i = 0; i &lt; rooms.length; i++) {
            for (int j = 0; j &lt; rooms[0].length; j++) {
                if (rooms[i][j] == 0) {
                    bfs(rooms, i, j);
                }
            }
        }
    }

    public void bfs(int[][] rooms, int x, int y) {
        if (x &lt; 0 || x &gt;= rooms.length || y &lt; 0 || y &gt;= rooms[0].length) return;
        ArrayDeque&lt;Point&gt; queue = new ArrayDeque&lt;&gt;();
        queue.offer(new Point(x, y, 0)); // add the start point to the queue
        while(!queue.isEmpty()) {
            Point point = queue.pop(); // dequeue and check 

            // explore 4 directions
            for (int i = 0; i &lt; 4; i++) {
                int newX = point.x + xDir[i];
                int newY = point.y + yDir[i];
                Point newPoint = new Point(newX, newY, point.prevPos);
                if (shouldExplore(newPoint, rooms)) {
                    newPoint.prevPos += 1;
                    rooms[newX][newY] = newPoint.prevPos;
                    queue.offer(newPoint);
                }
            }
        }
    }

    public boolean shouldExplore(Point p, int[][] rooms) {
        if (p.x &lt; 0 || p.x &gt;= rooms.length || p.y &lt; 0 || p.y &gt;= rooms[0].length || rooms[p.x][p.y] &lt; p.prevPos || rooms[p.x][p.y] == -1 ) return false;
        return true;
    }
}