Posted Updated LeetCode / Mediuma minute read (About 140 words)

59. Spiral Matrix II

问题
Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.

循环，创建一个上界和一个下界。
当达到界限时，改变方向。
更新上界和下界的数值。
当上界小于下界时返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int[][] generateMatrix(int n) {
        int[][] ans = new int[n][n];
        int upperBound = n;
        int lowerBound = 0;
        int i = 0;
        int j = 0;
        int count = 1;
        ans[0][0] = 1;
 
        while ( lowerBound < upperBound ){
            while ( j < upperBound-1 ){
                j++;
                count++; 
                ans[i][j] = count;           
            }
            while ( i < upperBound-1 ){
                i++;
                count++;
                ans[i][j] = count;
            }
            while ( j > lowerBound ){
                j--;
                count++;
                ans[i][j] = count;
            }
            upperBound--;
            lowerBound++;
            while ( i > lowerBound ){
                i--;
                count++;
                ans[i][j] = count;
            }
        }
        return ans;
    }
}
Posted Updated LeetCode / Medium3 minutes read (About 381 words)

289. Game of Life

问题
According to Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

  1. Any live cell with fewer than two live neighbors dies as if caused by under-population.
  2. Any live cell with two or three live neighbors lives on to the next generation.
  3. Any live cell with more than three live neighbors dies, as if by over-population.
  4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously. Given the current state of the m x n grid board, return the next state.

辅助方法，计算每个位置四周有生命的总和。
根据规则填写到新数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
    public void gameOfLife(int[][] board) {
        int[][] ans = new int[board.length][board[0].length];
        for (int i = 0; i < board.length; i++){
            for (int j = 0; j < board[0].length; j++){
                int neighbors = countNeighbors(board, i, j);
                if ( neighbors < 2 && board[i][j] == 1 ){
                    ans[i][j] = 0;
                }
                else if( neighbors <= 3 && board[i][j] == 1 ){
                    ans[i][j] = 1;
                }
                else if( neighbors > 3 && board[i][j] == 1 ){
                    ans[i][j] = 0;
                }
                else if( neighbors == 3 && board[i][j] == 0){
                    ans[i][j] = 1;
                }
                
            }
        }
        
        for (int i = 0; i < board.length; i++){
            for (int j = 0; j < board[0].length; j++){
                board[i][j] = ans[i][j];
            }
        }
    }
    
    
    private int countNeighbors(int[][] board, int r, int c){
        int neighbors = 0;
        int row = board.length;
        int col = board[0].length;
        
        if(r + 1 < row && board[r+1][c] == 1){ neighbors++; }
        if(r - 1 >= 0 && board[r-1][c] == 1){ neighbors++; }
        if(c + 1 < col && board[r][c+1] == 1){ neighbors++; }
        if(c - 1 >= 0 && board[r][c-1] == 1){ neighbors++; }
        
        if(r + 1 < row && c + 1 < col && board[r+1][c+1] == 1){ neighbors++; }
        if(r + 1 < row && c - 1 >= 0 && board[r+1][c-1] == 1 ){ neighbors++; }
        if(r - 1 >= 0 && c + 1 < col && board[r-1][c+1] == 1 ){ neighbors++; }
        if(r - 1 >= 0 && c - 1 >= 0 && board[r-1][c-1] == 1 ){ neighbors++; }
        
        return neighbors;
    }
}
Posted Updated LeetCode / Easya minute read (About 126 words)

145. Binary Tree Postorder Traversal

问题
Given the root of a binary tree, return the postorder traversal of its nodes’ values.

后序遍历。
先递归左子节点。
然后递归右子节点。
最后将当前节点加入数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> ans;
    public List<Integer> postorderTraversal(TreeNode root) {
        ans = new ArrayList();
        traversal(root);
        return ans;
    }
    
    private void traversal(TreeNode root){
        if (root == null){
            return;
        }
        traversal(root.left);
        traversal(root.right);
        ans.add(root.val);
        return;
    }
}
Posted Updated LeetCode / Easya minute read (About 126 words)

94. Binary Tree Inorder Traversal

问题
Given the root of a binary tree, return the inorder traversal of its nodes’ values.

中序遍历。
先递归左子节点。
然后将当前节点加入数组。
最后递归右子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> ans;
    public List<Integer> inorderTraversal(TreeNode root) {
        ans = new ArrayList();
        traversal(root);
        return ans;
    }
    
    private void traversal(TreeNode root){
        if (root == null){
            return;
        }
        traversal(root.left);
        ans.add(root.val);
        traversal(root.right);
        return;
    }
}
Posted Updated LeetCode / Easya minute read (About 126 words)

144. Binary Tree Preorder Traversal

问题
Given the root of a binary tree, return the preorder traversal of its nodes’ values.

先序遍历。
先将当前节点加入数组。
然后递归左子节点。
最后递归右子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> ans;
    public List<Integer> preorderTraversal(TreeNode root) {
        ans = new ArrayList();
        traversal(root);
        return ans;
    }
    
    private void traversal(TreeNode root){
        if (root == null){
            return;
        }
        ans.add(root.val);
        traversal(root.left);
        traversal(root.right);
        return;
    }
}
Posted Updated LeetCode / Easy / 复习2 minutes read (About 320 words)

232. Implement Queue using Stacks

问题
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).

Implement the MyQueue class:

  • void push(int x) Pushes element x to the back of the queue.

  • int pop() Removes the element from the front of the queue and returns it.

  • int peek() Returns the element at the front of the queue.

  • boolean empty() Returns true if the queue is empty, false otherwise.
    Notes:

  • You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.

  • Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack’s standard operations.

创建两个栈。
当入队列时，将元素压入第一个栈。
当出队列或进行其他操作时，如第二个栈为空，则将第一个栈的元素倒出到第二个栈。
此时第二个栈内的内容为顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class MyQueue {
    Stack<Integer> s1;
    Stack<Integer> s2;
        
    public MyQueue() {
        s1 = new Stack();
        s2 = new Stack();
    }
    
    public void push(int x) {
        s1.add(x);
    }
    
    public int pop() {
        if (s2.isEmpty()){
            while (!s1.isEmpty()){
                s2.add(s1.pop());
            }
            return s2.pop();
        }
        else{
            return s2.pop();
        }
        
    }
    
    public int peek() {
        if (s2.isEmpty()){
            while (!s1.isEmpty()){
                s2.add(s1.pop());
            }
            return s2.peek();
        }
        else{
            return s2.peek();
        }
    }
    
    public boolean empty() {
        return s1.isEmpty() && s2.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */
Posted Updated LeetCode / Easya minute read (About 176 words)

1260. Shift 2D Grid

问题
Given a 2D grid of size m x n and an integer k. You need to shift the grid k times.

In one shift operation:

Element at grid[i][j] moves to grid[i][j + 1].
Element at grid[i][n - 1] moves to grid[i + 1][0].
Element at grid[m - 1][n - 1] moves to grid[0][0].
Return the 2D grid after applying shift operation k times.

遍历整个数组，将索引值加上移动的次数，得到新的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public List<List<Integer>> shiftGrid(int[][] grid, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        int row = grid.length;
        int col = grid[0].length;
        int size = row * col;
        Integer[][] mat = new Integer[row][col];
        
        for (int i = 0; i < size; i++){
            int j = i + k;
            if ( j > size - 1){
                j %= size;
            }
            int nr = j / col;
            int nc = j % col;
            int or = i / col;
            int oc = i % col;
            
            mat[nr][nc] = grid[or][oc];
        }
        
        for (int i = 0; i < row; i++){
            List<Integer> nums = Arrays.asList(mat[i]);
            ans.add(nums);
        }
        
        return ans;
    }
}
Posted Updated LeetCode / Easy2 minutes read (About 243 words)

682. Baseball Game

问题
You are keeping score for a baseball game with strange rules. The game consists of several rounds, where the scores of past rounds may affect future rounds’ scores.

At the beginning of the game, you start with an empty record. You are given a list of strings ops, where ops[i] is the ith operation you must apply to the record and is one of the following:

  1. An integer x - Record a new score of x.
  2. “+” - Record a new score that is the sum of the previous two scores. It is guaranteed there will always be two previous scores.
  3. “D” - Record a new score that is double the previous score. It is guaranteed there will always be a previous score.
  4. “C” - Invalidate the previous score, removing it from the record. It is guaranteed there will always be a previous score.

Return the sum of all the scores on the record.

遍历选项，根据内容决定对ArrayList的操作。
然后遍历将ArrayList加和，返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int calPoints(String[] ops) {
        int ans = 0;
        List<Integer> records = new ArrayList();
        
        for (String op : ops){
            switch(op){
                case "+":
                    records.add(records.get(records.size()-1)+records.get(records.size()-2));
                    break;
                case "D":
                    records.add(records.get(records.size()-1)*2);
                    break;
                case "C":
                    records.remove(records.size()-1);
                    break;
                default:
                    records.add(Integer.parseInt(op));
            }
        }
        
        for (int record : records){
            ans += record;
        }                 
        return ans;
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 351 words)

994. Rotting Oranges

问题
You are given an m x n grid where each cell can have one of three values:

  • 0 representing an empty cell,
  • 1 representing a fresh orange, or
  • 2 representing a rotten orange.
    Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

由于腐烂的橘子每次都只能影响周围的橘子，因此采用BFS。
将所有腐烂的橘子加入队列。
如果没有新鲜的橘子，则返回0。
每次出队列，如果周围有新鲜的橘子存在，则将新鲜的橘子替换为腐烂并加入队列。
每个level结束后，time+1。

最后遍历一遍，如果还有新鲜的橘子，返回-1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<Integer> q = new LinkedList();
        int row = grid.length;
        int col = grid[0].length;
        int fresh = 0;
        for (int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if ( grid[i][j] == 2){
                    q.add(i * col + j);
                }
                else if (grid[i][j] == 1){
                    fresh++;
                }
            }
        }
        if(fresh == 0){return 0;}
        
        int count = q.size()-1;
        int temp = 0;
        int time = -1;
        while(!q.isEmpty()){
            int i = q.peek() / col;
            int j = q.poll() % col;
            
            if(i-1>=0 && grid[i-1][j] == 1){
                grid[i-1][j] = 2;
                q.add((i-1)*col+j);
                temp++;
            }
            if(j-1>=0 && grid[i][j-1] == 1){
                grid[i][j-1] = 2;
                q.add(i*col+(j-1));
                temp++;
            }
            if(i+1<row && grid[i+1][j] == 1){
                grid[i+1][j] = 2;
                q.add((i+1)*col+j);
                temp++;
            }
            if(j+1<col && grid[i][j+1] == 1){
                grid[i][j+1] = 2;
                q.add(i*col+(j+1));
                temp++;
            }
            
            if(count == 0){
                count = temp;
                temp = 0;
                time++;
            }
            count--;
        }
        
        for (int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if ( grid[i][j] == 1){
                    return -1;
                }
            }
        }
        return time;
        
    }
}
Posted Updated LeetCode / Easy / 复习2 minutes read (About 319 words)

542. 01 Matrix

问题
Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.

由于是搜索最近的距离，因此可以采用BFS搜索。
首先创建一个距离矩阵，将所有原矩阵为0的位置填上距离0，将其他位置填上无穷大。
使用BFS搜索，将所有0的坐标放入队列。
取出队列头元素，将其周围的距离矩阵的元素与自身距离矩阵的元素+1比较，将较小的值设置在周围的距离矩阵上。
同时，将改变数值的坐标再次放入队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution{
    public int[][] updateMatrix(int[][] mat) {

        Queue<Integer> q = new LinkedList();
        int row = mat.length;
        int col = mat[0].length;
        int[][] ans = new int[row][col];
                                   
        for ( int i = 0; i < row; i++ ){
            for (int j = 0; j < col; j++){
                if (mat[i][j] == 0){
                    ans[i][j] = 0;
                    q.add(i*col + j);
                }
                else{
                    ans[i][j] = Integer.MAX_VALUE;
                }
            }
        }

            
        while(!q.isEmpty()){
            int i = q.peek() / col;
            int j = q.poll() % col;
            
            if(i-1 >= 0 && ans[i][j]+1 < ans[i-1][j]){
                ans[i-1][j] = ans[i][j]+1;
                q.add((i-1)*col + j);
            }
            if(i+1 < row && ans[i][j]+1 < ans[i+1][j]){
                ans[i+1][j] = ans[i][j]+1;
                q.add((i+1)*col + j);
            }
            if(j-1 >= 0 && ans[i][j]+1 < ans[i][j-1]){
                ans[i][j-1] = ans[i][j]+1;
                q.add(i*col + (j-1));
            }
            if(j+1 < col && ans[i][j]+1 < ans[i][j+1]){
                ans[i][j+1] = ans[i][j]+1;
                q.add(i*col + (j+1));
            }
        }
        return ans;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 361 words)

116. Populating Next Right Pointers in Each Node

问题
You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

1
2
3
4
5
6
 struct Node {
 int val;
 Node *left;
 Node *right;
 Node *next;
>}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

递归，当root为null时返回。
如果root有右节点，则左节点next指向右节点。
如果root有右节点同时next已经指向了一个节点，则将其右节点next指向该节点的左子节点。
递归左右子节点，并返回root。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if (root==null){return root;}
        if (root.right!=null){
            root.left.next = root.right;
            if (root.next!=null){
                root.right.next = root.next.left;
            }
        }
        connect(root.left);
        connect(root.right);
        return root;
    }
}

BFS搜索每一个节点，将节点指向队列中next下一个节点。
当计数器达到2的指数时，将节点指向null。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    public Node connect(Node root) {
        if (root == null){
            return root;
        }
        
        int count = 1;
        Queue<Node> q = new LinkedList();
        q.offer(root);
        while (!q.isEmpty()){
            count++;
            Node curr = q.poll();
            if ( isPow(count) ){
                curr.next = null;
            }
            else{
                curr.next = q.peek();
            }
            if(curr.left!=null){
                q.add(curr.left);
            }
            if(curr.right!=null){
                q.add(curr.right);
            }

        }
        return root;
    }
    
    private boolean isPow(int val){
        if(val == 0 || val == 1){
            return false;
        }
        while ( val % 2 == 0 ){
            val = val / 2;
        }
        if (val == 1){
            return true;
        }
        return false;
    }
}
Posted Updated LeetCode / Easy / 复习a minute read (About 170 words)

20. Valid Parentheses

问题
Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

用栈储存遍历中的字符。
如果是“（”，“{”或“[”，则入栈。
如果是其他字符，且不与栈顶的字符成对，则返回false。
其他情况需要pop掉栈顶。

  • toCharArray(): 将字符串转换为字符数组，便于遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack();
        
        for (char c : s.toCharArray()){
            if ( c == '(' || c == '{' || c == '[' ){
                stack.push(c);
            }
            else if ( stack.size() == 0 || 
                     c == ')' && stack.peek() != '(' || 
                     c == '}' && stack.peek() != '{' || 
                     c == ']' && stack.peek() != '[') {
                return false;
            }
            else{
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}
Posted Updated LeetCode / Easy / 复习2 minutes read (About 247 words)

617. Merge Two Binary Trees

问题
You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

递归。将root1和root2合并到root1。
如果一个节点为null，则返回另一个节点。
否则root1的值为root1 + root2的值。
root1.left递归root1和root2的left。
root2.right递归root1和root2的right。
返回root1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if( root1 == null ){
            return root2;
        }
        if( root2 == null ){
            return root1;
        }
        
        root1.val = root1.val + root2.val;
        root1.left = mergeTrees(root1.left,root2.left);
        root1.right = mergeTrees(root1.right,root2.right);
        
        return root1;
    }
}
Posted Updated LeetCode / Easya minute read (About 167 words)

83. Remove Duplicates from Sorted List

问题
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

设置前一个节点和当前节点两个指针。
由于是有数的链表，遍历时可以直接比较两个节点。
如相等则前一个节点的next指向当前节点的next。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        
        if ( head == null){
            return head;
        }
        if ( head.next == null){
            return head;
        }
        ListNode prev = head;
        ListNode curr = head.next;
        
        while(curr != null){
            if(prev.val != curr.val){
                curr = curr.next;
                prev = prev.next;
            }
            else{
                prev.next = curr.next;
                curr = curr.next;
            }
        }
        return head;
    }
}
695. Max Area of Island
Posted Updated LeetCode / Medium / 复习2 minutes read (About 292 words)

695. Max Area of Island

Question

You are given an m x n binary matrix grid. An island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Solution

DFS搜索, 维护一个变量count，为连续执行DFS搜索的次数。
遍历地图上所有为1的位置。

运行BFS时每次将全局变量count增加1。
执行完毕后BFS时将全局变量count清零。

遍历每个等于1的地图块。
递归周围四个地图块，当超越数组范围，或者当前位置不为1时返回。
进行搜索时将搜索过的地图块标记为0，不再重复搜索。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    int[][] visited, directions;
    int count;
    public int maxAreaOfIsland(int[][] grid) {
        int res = 0;
        directions = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for(int x = 0; x < grid.length; x++){
            for(int y = 0; y < grid[0].length; y++){
                if(grid[x][y] == 1){
                    count = 0;
                    dfs(grid, x, y);
                    res = Math.max(res, count);
                }
            }
        }
        return res;
    }
    
    private void dfs(int[][] grid, int x, int y){
        if(x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] == 0) return;
        grid[x][y] = 0;
        count++;
        for(int[] direction : directions){
            int i = x + direction[0];
            int j = y + direction[1];
            dfs(grid, i, j);
        }
    }
}
Follow

Recents

Archives

Links

×