Posted Updated LeetCode / Easy / 复习a minute read (About 215 words)

104. Maximum Depth of Binary Tree

问题
Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

递归，每次返回左子节点和右子节点中较大的结果+1。
当节点为null时返回0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 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 int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}

BFS搜索，每次倾倒出队列里所有的元素并将level+1。
搜索完毕返回level。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        Queue<TreeNode> q = new LinkedList();
        q.offer(root);
        int level = 0;
        while(!q.isEmpty()){
            int size = q.size();
            for (int i = 0; i < size; i++){
                TreeNode curr = q.poll();
                if(curr.left!=null){q.offer(curr.left);}
                if(curr.right!=null){q.offer(curr.right);}
            }
            level++;
        }
        return level;
    }
}
Posted Updated LeetCode / Medium / 复习a minute read (About 183 words)

102. Binary Tree Level Order Traversal

Question

Given the root of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

Solution

BFS搜索，层序遍历，记录每个层级的节点数量size。
在遍历时挤出size个节点，并将其子节点加入队列。

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
30
31
32
33
34
35
36
37
38
/**
 * 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 List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        int size = 1;
        while(!q.isEmpty()){
            List<Integer> list = new ArrayList<>();
            TreeNode curr = null;
            for(int i = 0; i < size; i++){
                curr = q.poll();
                if(curr.left != null) q.offer(curr.left);
                if(curr.right != null) q.offer(curr.right);
                list.add(curr.val);
            }
            ret.add(list);
            size = q.size();
        }
        return ret;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 228 words)

77. Combinations

问题
Given two integers n and k, return all possible combinations of k numbers out of the range [1, n].

You may return the answer in any order.

回溯，构建搜索树。
子节点取出的数值应大于父节点中取出的数值。
直到树高度达到k后返回。

返回时，要new一个List，将原有list传入。
否则添加到ans的值只是list的内存地址。
ArrayList换成LinkedList可以优化一些速度，因为可以直接removeLast。（22ms -> 16ms）
i的范围限制在start到n-k+1，后面的限制容易被忽略，可以大幅度减枝，优化速度。（16ms -> 1ms）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    List<List<Integer>> ans;
    public List<List<Integer>> combine(int n, int k) {
        ans = new ArrayList<>();
        backTrack(new LinkedList(),1,n,k);
        return ans;
    }
    
    private void backTrack(LinkedList<Integer> list, int start, int n, int k){
        if (k == 0){
            ans.add(new ArrayList(list));
            return;
        }

        for (int i = start; i <= n-k+1; i++){
            list.add(i);
            backTrack(list, i+1, n, k-1);
            list.removeLast();
        }
    }
}
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;
    }
}
Follow

Recents

Archives

Links

×