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

231. Power of Two

问题
Given an integer n, return true if it is a power of two. Otherwise, return false.

An integer n is a power of two, if there exists an integer x such that n == 2x.

位运算，由于2^n^的二进制为[100…00]，当2^n^-1时，其二进制为[11..11]（少一位）。
两者进行按位与（&）运算，得到[000…00]，与0相等。

1
2
3
4
5
6
7
8
class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0){
            return false;
        }
        return (n & (n - 1)) == 0;
    }
}

递归，当（n <= 0）时，返回false。
当n等于1时，返回true。
当（n % 2）有余数时，返回false。
递归（n / 2）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean isPowerOfTwo(int n) {
        if (n <= 0){
            return false;
        }
        if (n == 1){
            return true;
        }
        if (n%2 != 0){
            return false;
        }
        return isPowerOfTwo(n/2);
    }
}
Posted Updated LeetCode / Easy / 复习a minute read (About 216 words)

112. Path Sum

问题
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

递归，如果当前节点为null则返回false。
计算并更新当前节点的值。
如果当前节点为叶节点，且当前节点的值等于target，则返回true。
递归左子节点和右子节点，返回两者的或运算。

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
/**
 * 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 boolean hasPathSum(TreeNode root, int targetSum) {
        return hasPathSum(root,0,targetSum);
    }
    
    private boolean hasPathSum(TreeNode root, int parentVal, int target){
        if (root == null){return false;}
        root.val = root.val + parentVal;
        if (root.left == null && root.right == null && root.val == target){
            return true;
        }
        return ( hasPathSum(root.left, root.val, target) || hasPathSum(root.right, root.val, target));
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 276 words)

701. Insert into a Binary Search Tree

问题
You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Notice that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

如果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
39
40
/**
 * 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 insertIntoBST(TreeNode root, int val) {
        if (root == null){
            root = new TreeNode(val);
        }
        insert(root,val);
        return root;
    }
    
    private void insert(TreeNode root, int val){
        if (root.val < val){
            if (root.right == null){
                root.right = new TreeNode(val);
            }
            insert(root.right, val);
        }
        else if (root.val > val){
            if (root.left == null){
                root.left = new TreeNode(val);
            }
            insert(root.left, val);
        }
        return;
    }
}
Posted Updated LeetCode / Easya minute read (About 188 words)

700. Search in a Binary Search Tree

问题
You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node’s value equals val and return the subtree rooted with that node. If such a node does not exist, return 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
/**
 * 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 searchBST(TreeNode root, int val) {
        if (root == null){
            return null;
        }
        else if (root.val < val){
            return searchBST(root.right,val);
        }
        else if (root.val > val){
            return searchBST(root.left,val);
        }
        else{
            return root;
        }
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 295 words)

120. Triangle

问题
Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

动态规划，先将最左侧一列的值算出。
然后[i+1][j+1]根据[i][j+1]和[i][j]得出。
该动态规划表应是为三角形。
因此当i等于j时，[i+1][i+j]的数值只根据[i][j]得出。

例子：
代码里插入了一个print方法打印动态规划表。
当输入列表 [[2],[3,4],[6,5,7],[4,1,8,3]] 时：
其动态规划表为：

  • 2, 0, 0, 0,
  • 5, 6, 0, 0,
  • 11, 10, 13, 0,
  • 15, 11, 18, 16,
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
class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int[][] dp = new int[triangle.size()][triangle.size()];
        int min = Integer.MAX_VALUE;
        dp[0][0] = triangle.get(0).get(0);
        
        for (int i = 0; i < triangle.size()-1; i++){
            dp[i+1][0] = dp[i][0] + triangle.get(i+1).get(0);
        }        
        
        for (int i = 0; i < triangle.size()-1; i++){
            for (int j = 0; j <= i; j++){
                
                if ( i == j ){
                    dp[i+1][j+1] = dp[i][j] + triangle.get(i+1).get(j+1);
                }
                else{
                    dp[i+1][j+1] = Math.min(dp[i][j] + triangle.get(i+1).get(j+1),
                                        dp[i][j+1] + triangle.get(i+1).get(j+1));
                }
                
            }
        }
        //print(dp);
        for (int k = 0; k < triangle.size(); k++){
            min = Math.min(dp[triangle.size()-1][k],min);
        }
        return min;
    }
    
    private void print(int[][] text){
        for (int i = 0; i <text.length; i++){
            for (int j = 0; j < text[0].length; j++){
                System.out.print(text[i][j]+", ");
            }
            System.out.println();
        }
    }

}
Follow

Recents

Archives

Links

×