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;
    }
}

NC19 连续子数组的最大和

  • 描述

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

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

进阶:时间复杂度为 O(n)O(n)，空间复杂度为 O(1)O(1)

示例1

输入：

1
[1,-2,3,10,-4,7,2,-5]

返回值：

1
18

说明：

1
经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18

示例2

输入：

1
[2]

返回值：

1
2

示例3

输入：

1
[-10]

返回值：

1
-10

思路：

  • array[i] 存当前的值+之前的值
  • array[i-1]为负数时舍去这个，重新从array[i]开始算和

解答：

1
2
3
4
5
6
7
8
9
10
public class Solution {
    public  int FindGreatestSumOfSubArray(int[] array) {
            int max = array[0];	
            for (int i = 1; i < array.length; i++) {
                array[i] += array[i-1] > 0 ? array[i-1] : 0;
                max = Math.max(max, array[i]);
            }
            return max;
    }
}