数字的补数

对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。

例如，整数 5 的二进制表示是 “101” ，取反后得到 “010” ，再转回十进制表示得到补数 2 。
给你一个整数 num ，输出它的补数。

  • 示例 1：

    输入：num = 5
    输出：2
    解释：5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。

  • 示例 2：

    输入：num = 1
    输出：0
    解释：1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。

提示：

  • 1 <= num < 231

Solution

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
#include <iostream>

class Solution {
public:
    int findComplement(int num) {
        if (num == 0) {
            return 1;
        }
        if (num == 1) {
            return 0;
        }
        long int sum = 1;
        while (sum <= num) {
            sum = sum * 2;
        }
        return sum - 1 - num;
    }
};

int main() {
    std::cout << Solution().findComplement(5) << std::endl; // 2
    std::cout << Solution().findComplement(1) << std::endl; // 0
    std::cout << Solution().findComplement(6) << std::endl; // 1
    std::cout << Solution().findComplement(4) << std::endl; // 3
    return 0;
}

动态规划解法：

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
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    int longestValidParentheses(string s) {
        int longest = 0;
        int n = s.length();
        std::vector<int> d(n, 0);
        for (int i = 1; i < n; ++i) {
            if (s.at(i) == ')') {
                if (s.at(i - 1) == '(') {
                    d[i] = ((i < 2) ? 0 : d[i - 2]) + 2;
                } else if (s.at(i - d[i - 1] - 1) == '(') {
                    d[i] = d[i - 1] + ((i - d[i - 1]) >= 2? d[i - d[i - 1] - 2]: 0) + 2;
                }
                longest = std::max(longest, d[i]); 
            }
        }
        return longest;
    }
};


int main() {
    std::cout << Solution().longestValidParentheses("(()") << std::endl; // 2
    std::cout << Solution().longestValidParentheses(")()())") << std::endl; // 4
    std::cout << Solution().longestValidParentheses(")()())()()(") << std::endl; // 4
    
    return 0;
}