600. 不含连续1的非负整数

难度困难138

给定一个正整数 n，找出小于或等于 n 的非负整数中，其二进制表示不包含 连续的1 的个数。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
输入: 5
输出: 5
解释: 
下面是带有相应二进制表示的非负整数<= 5：
0 : 0
1 : 1
2 : 10
3 : 11
4 : 100
5 : 101
其中，只有整数3违反规则（有两个连续的1），其他5个满足规则。

说明: 1 <= n <= 109

解答：

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
class Solution {
    public int findIntegers(int num) {
        //根据构建斐波那也数列
        int[] dp = new int[32];
        dp[0] = 1;
        dp[1] = 2;
        for(int i = 2;  i < 32; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        String numStr = getBinary(num);
        //一位位移动，不连续遇到1加上它
        int res = 0;
        for(int i = 0; i < numStr.length(); i++) {
            if(numStr.charAt(i) == '0') {
                continue;
            }
            res  += dp[numStr.length() - i - 1];
            if(i != 0 && numStr.charAt(i - 1 ) == '1'){
                return res;
            }
            
        }
        return res + 1;
    }
//整数 转 二进制数
    private String getBinary(int num) {
        StringBuilder sb = new StringBuilder();
        while(num > 0){
            sb.insert(0,num & 1);
            num >>= 1;
        }
        return sb.toString();
    }
}

678. 有效的括号字符串

给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

  1. 任何左括号 ( 必须有相应的右括号 )。
  2. 任何右括号 ) 必须有相应的左括号 ( 。
  3. 左括号 ( 必须在对应的右括号之前 )。
  4. * 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
  5. 一个空字符串也被视为有效字符串。

示例 1:

1
2
输入: "()"
输出: True

示例 2:

1
2
输入: "(*)"
输出: True

示例 3:

1
2
输入: "(*))"
输出: 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
class Solution {
    public boolean checkValidString(String s) {
        // l: 左括号最少可能有多少个
        // r: 左括号最多可能有多少个
        int l = 0, r = 0;
        for (char c : s.toCharArray()) {
            // 遇到'('所有可能性加一
            // 遇到')'所有可能性减一
            // 遇到'*'，最少的可能性可以变少，最多的可能性也同样可以变多，这取决于这个星号最终我们看成什么，但是可能性都在
            if (c == '(') {
                l++; r++;
            } else if (c == ')') {
                l--; r--;
            } else {
                l--; r++;
            }
            // 当前左括号最少个数不能为负
            l = Math.max(l, 0);
            // 这种情况其实发生在r本身是负数的时候，也就是我们常见的右括号太多了
            if (l > r) return false;
        }
        // 能取到0个左括号才是满足平衡的
        return l == 0;
    }
}

NC45 实现二叉树先序，中序和后序遍历

描述

给定一棵二叉树，分别按照二叉树先序，中序和后序打印所有的节点。

数据范围：0 \le n \le 10000≤n≤1000，树上每个节点的val值满足 0 \le val \le 1000≤val≤100

要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

样例解释：

img如图二叉树结构

示例1

输入：

1
{1,2,3}

返回值：

1
[[1,2,3],[2,1,3],[2,3,1]]

说明：

1
如题面图

示例2

1
{}

返回值：

1
[[],[],[]]

思路：

  • 先，中，后序遍历是根节点在先，中，后
  • 定义全局变量存储先，中，后序遍历结果
  • 递归实现先，中，后序，每次存储根节点
  • ArrayList<>存先，中，后序遍历结果
  • ArrayList<ArrayList<>>转list[][]

解答：

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
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型二维数组
     */
    List<Integer> pre = new ArrayList<>();
    List<Integer> in = new ArrayList<>();
    List<Integer> post = new ArrayList<>();
    
    public int[][] threeOrders (TreeNode root) {
        // write code here
//         if (root == null) return new int[][] {{}};
        List<List<Integer>> ans = new ArrayList<>();
        preOrder(root);
        inOrder(root);
        postOrder(root);
        ans.add(pre);
        ans.add(in);
        ans.add(post);
        int[][] res = new int[ans.size()][ans.get(0).size()];
        for (int i = 0; i < ans.size(); i++) {
            for (int j = 0; j < ans.get(0).size(); j++) {
                res[i][j] = ans.get(i).get(j);
            }
        }
        return res;
    }
    
    public void preOrder(TreeNode root) {
        if (root == null) return;
        pre.add(root.val);
        preOrder(root.left);
        preOrder(root.right);
    }
    
    public void inOrder(TreeNode root) {
        if (root == null) return;
        inOrder(root.left);
        in.add(root.val);
        inOrder(root.right);
    }
    
    public void postOrder(TreeNode root) {
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        post.add(root.val);
    }
}

NC15 求二叉树的层序遍历

描述

给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},
img
该二叉树层序遍历的结果是
[
[3],
[9,20],
[15,7]

]

提示:

0 <= 二叉树的结点数 <= 1500

示例1

输入：

1
{1,2}

返回值：

1
[[1],[2]]

示例2

输入：

1
{1,2,3,4,#,#,5}

复制

返回值：

1
[[1],[2,3],[4,5]]

思路：

  • 声明一个成员变量供全局使用；

  • 向下探索的递归方法，注意先从左边再从右边；每向下一层level+1

  • 二维List来说，将根视为第0层，树的深度正好等于一维List的个数。

解答：

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
import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        if(root == null) return res;
        count(root, 0);
        return res;
    }
    public void count(TreeNode node, int level) {
        if(level == res.size()) {
            res.add(new ArrayList<Integer>());
        }
        
        res.get(level).add(node.val);
        if(node.left != null){
            count(node.left, level + 1);
        }
        if(node.right != null){
            count(node.right, level + 1);
        }
    }
}