Posted Updated LeetCode / Easy / 复习2 minutes read (About 263 words)

70. Climbing Stairs

问题
You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

递归，传入根节点，进行BFS搜索。
如果当前节点小于搜索的最低点，则抛弃该节点，继续搜索其右子节点。（由于是BST，右子节点大于节点本身）
如果当前节点大于搜索的最高点，则抛弃该节点，继续搜索其左子节点。
如果当前节点在搜索范围内，则保留该节点，继续递归该节点的两个子节点。
最后返回根节点。

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
/**
 * 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 trimBST(TreeNode root, int low, int high) {
        if(root == null){
            return null;
        }
        if(root.val < low){
            return trimBST(root.right, low, high);
        }
        if(root.val > high){
            return trimBST(root.left, low, high);
        }
        
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}
Posted Updated LeetCode / Easy / 复习a minute read (About 206 words)

191. Number of 1 Bits

问题
Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (also known as the Hamming weight).

Note:

  • Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.
  • In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 3, the input represents the signed integer. -3.

位运算，[n-1]的二进制数字为[n]的二进制数字退一位。
二者的与运算结果相当于二进制下[n]减少最右侧的1。
例如0100100的0100011
两者的与运算结果为0100000。相当于减少了一位1。
计算循环次数就可以得出1的总数。

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while(n != 0){
            n = (n & (n-1));
            count++;
        }
        return count;
    }
}
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();
        }
    }

}
Posted Updated LeetCode / Mediuma minute read (About 192 words)

198. House Robber

问题
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

动态规划。
dp数组记录经过i个房子后可以获得的最大值。
dp[i+1]的值等于dp[i-1]加上现有房子的钱（抢这个房子）与dp[i]的值（不抢这个房子）中的较大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int rob(int[] nums) {

        int[] money = new int[nums.length+1];
        money[0] = 0;
        money[1] = nums[0];
        
        for (int i = 1; i < nums.length; i++){
            money[i+1] = Math.max(money[i-1]+nums[i],money[i]);
            
        }
            
        return money[nums.length];
        
    }
}
Posted Updated LeetCode / Easya minute read (About 156 words)

226. Invert Binary Tree

问题
Given the root of a binary tree, invert the tree, and return its root.

翻转二叉树。
交换当前节点的左右子节点。
分别递归其左右子节点。
当当前节点的两个节点均为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
/**
 * 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 invertTree(TreeNode root) {
        if (root == null){
            return root;
        }
        invert(root);
        return root;
    }
    
    private void invert(TreeNode root){
        if ( root.left == null && root.right == null){
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        if ( root.left != null ){
            invert(root.left);
        }
        if ( root.right != null ){
            invert(root.right);
        }
    }
}
Posted Updated LeetCode / Medium / 复习a minute read (About 224 words)

784. Letter Case Permutation

答案
Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string.

Return a list of all possible strings we could create. Return the output in any 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
38
class Solution {
    List<String> ans;
    String _s;
    public List<String> letterCasePermutation(String s) {
        ans = new ArrayList();
        _s = s;
        
        backTrack(new StringBuilder(),0);
        return ans;
        
    }
    
    private void backTrack(StringBuilder sb, int i){
        if(i == _s.length()){
            ans.add(sb.toString());
            return;
        }
        char curr = _s.charAt(i);
        if ( isNums(curr) ){
            sb.append(curr);
            backTrack(sb, i+1);
        }
        else{
            StringBuilder sb2 = new StringBuilder(sb);
            sb.append(Character.toLowerCase(curr));
            backTrack(sb, i+1);
            sb2.append(Character.toUpperCase(curr));
            backTrack(sb2, i+1);
        }
    }
    
    private boolean isNums(char c){
        if ( (int)c >= (int)'0' && (int)c <= (int)'9' ){
            return true;
        }
        return false;
    }
}
Posted Updated LeetCode / Medium / 复习a minute read (About 181 words)

46. Permutations

问题
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

回溯，建立搜索树。
每次遍历nums中的元素。
如果未遍历过该元素，则向链表及set中添加。
向下递归，链表长度达到nums的长度时返回。
然后从set和链表中移除上一个值，回溯到上一个节点。

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
class Solution {
    List<List<Integer>> ans;
    HashSet<Integer> set;
    public List<List<Integer>> permute(int[] nums) {
        ans = new ArrayList();
        set = new HashSet();
        backTrack(new LinkedList(), nums, nums.length, nums.length);
        return ans;
    }
    
    private void backTrack(LinkedList<Integer> list,int[] nums, int n, int k){
        if(k == 0){
            ans.add(new ArrayList(list));
            return;
        }
        for(int i = 0; i < n ; i++){
            if(!set.contains(nums[i])){
                list.add(nums[i]);
                set.add(nums[i]);
                backTrack(list, nums , n, k-1);
                set.remove(nums[i]);
                list.removeLast();
            }
        }
    }
}
Posted Updated LeetCode / Easya minute read (About 187 words)

101. Symmetric Tree

问题
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

递归root1的左子节点和root2的右子节点以及root2的左子节点以及root1的右子节点。如两者不相等则返回false。
如果传入的两个数值有一个为null，则两者不相等时返回false。反之返回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
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 {
    public boolean isSymmetric(TreeNode root) {
        return isSymmetric(root,root);
    }
    
    public boolean isSymmetric(TreeNode root1, TreeNode root2){
        if ( root1 == null || root2 == null ){
            if(root1 == root2){return true;}
            else{return false;}
        }
        if ( root1.val == root2.val ){
            return isSymmetric(root1.left,root2.right) && isSymmetric(root1.right,root2.left);
        }
        else{
            return false;
        }
    }
}
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();
        }
    }
}
Follow

Recents

Archives

Links

×