AC JAVA Solution easy to understand


  • 7
    J

    The idea is not to count how many same "candies" are in a row or column, but to check if this candy is eligible for crushing. If any candy is eligible, store the corresponding coordinates in a HashSet.
    After traversing the whole board, set the valid candies to "0" then crush (using 2-pointer method in a column).
    Here goes the code:

    class Solution {
        public int[][] candyCrush(int[][] board) {
            Set<Coordinates> set = new HashSet<>();
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++) {
                    int cur = board[i][j];
                    if (cur == 0) continue;
                    if ((i - 2 >= 0 && board[i - 1][j] == cur && board[i - 2][j] == cur) ||                                                 // check left 2 candies
                       (i + 2 <= board.length - 1 && board[i + 1][j] == cur && board[i + 2][j] == cur) ||                                   // check right 2 candies
                       (j - 2 >= 0 && board[i][j - 1] == cur && board[i][j - 2] == cur) ||                                                 // check 2 candies top
                       (j + 2 <= board[i].length - 1 && board[i][j + 1] == cur && board[i][j + 2] == cur) ||                               // check 2 candies below
                       (i - 1 >= 0 && i + 1 <= board.length - 1 && board[i - 1][j] == cur && board[i + 1][j] == cur) ||                    // check if it is a mid candy in row
                       (j - 1 >= 0 && j + 1 <= board[i].length - 1 && board[i][j - 1] == cur && board[i][j + 1] == cur)) {                // check if it is a mid candy in column
                        set.add(new Coordinates(i, j));
                    }
                }
            }
            if (set.isEmpty()) return board;      //stable board
            for (Coordinates c : set) {
                int x = c.i;
                int y = c.j;
                board[x][y] = 0;      // change to "0"
            }
            drop(board);
            return candyCrush(board);
        }
        private void drop(int[][] board) {                                          // using 2-pointer to "drop"
            for (int j = 0; j < board[0].length; j++) {
                int bot = board.length - 1;
                int top = board.length - 1;
                while (top >= 0) {
                    if (board[top][j] == 0) {
                        top--;
                    }
                    else {
                        board[bot--][j] = board[top--][j];
                    }
                }
                while (bot >= 0) {
                    board[bot--][j] = 0;
                }
            }
        }
    }
    
    class Coordinates {
        int i;
        int j;
        Coordinates(int x, int y) {
            i = x;
            j = y;
        }
    }
    

  • 0
    W

    @jun1013 Similar idea, written in Python, 155 ms, beat 100%. See the explanation in the following thread.
    https://discuss.leetcode.com/topic/112766/155-ms-python-with-detailed-explanation-beat-100

    class Solution(object):
        def candyCrush(self, board):
            board=map(list,zip(*reversed(board)))  # rotate clockwise 90 degree
            m,n=len(board),len(board[0])
    
            # repeat crush and drop
            while True:
                candy=set([])
                # check every row
                for i in xrange(m):
                    for j in xrange(2,n):
                        if board[i][j] and board[i][j]==board[i][j-1]==board[i][j-2]:
                            candy|={(i,j),(i,j-1),(i,j-2)}
                # check every col
                for j in xrange(n):
                    for i in xrange(2,m):
                        if board[i][j] and board[i][j]==board[i-1][j]==board[i-2][j]:
                            candy|={(i,j),(i-1,j),(i-2,j)}
                if not candy: break
                for i,j in candy: board[i][j]=0
    
                # drop the board, move all 0 to the end
                for i in xrange(m):
                    row=filter(None,board[i])
                    board[i]=row+[0]*(n-len(row))
         
            board=list(reversed(map(list,zip(*board)))) # rotate counter-clockwise 90 degree
            return board

  • 0
    N
    This post is deleted!

  • 0
    N
    This post is deleted!

  • 0
    N

    @jun1013
    You should override the hashcode for Coordinates. Otherwise, default object hashcode will be used for computing the bucket.


Log in to reply
 

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