Code – 第162页

LeetCode 113. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
return
[
[5,4,11,2],
[5,8,4,5]
]

分析：pathSum函数中只需dfs一下然后返回result数组即可，dfs函数中从root开始寻找到底端sum == root->val的结点，如果满足就将root->val压入path数组中，path数组压入result数组中，然后将当前结点弹出，return。不满足是最后一个结点的则不断深度优先左结点、右结点，同时处理好path数组的压入和弹出～～

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> result;
    vector<int> path;
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        dfs(root, sum);
        return result;
    }
    void dfs(TreeNode* root, int sum) {
        if(root == NULL) return ;
        if(root->val == sum && root->left == NULL && root->right == NULL) {
            path.push_back(root->val);
            result.push_back(path);
            path.pop_back();
            return ;
        }
        path.push_back(root->val);
        dfs(root->left, sum - root->val);
        dfs(root->right, sum - root->val);
        path.pop_back();
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

vector<vector<int>> result;

vector<int> path;

vector<vector<int>> pathSum(TreeNode* root, int sum) {

dfs(root, sum);

return result;

}

void dfs(TreeNode* root, int sum) {

if(root == NULL) return ;

if(root->val == sum && root->left == NULL && root->right == NULL) {

path.push_back(root->val);

result.push_back(path);

path.pop_back();

return ;

}

path.push_back(root->val);

dfs(root->left, sum - root->val);

dfs(root->right, sum - root->val);

path.pop_back();

}

};

LeetCode 437. Path Sum III

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

10
/ \
5 -3
/ \ \
3 2 11
/ \ \
3 -2 1

Return 3. The paths that sum to 8 are:

1. 5 -> 3
2. 5 -> 2 -> 1
3. -3 -> 11

分析：深度优先搜索，将root以及root->left、root->right结点分别作为开始结点计算下方是否有满足sum的和，dfs函数就是用来计算统计满足条件的个数的。dfs从TreeNode* root开始，查找是否满足sum和的值（此时的sum是部分和），分别dfs左边结点、右边结点，直到找到root->val == sum时候result++，在pathSum函数中返回result的值。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int result = 0;
    int pathSum(TreeNode* root, int sum) {
        if(root == NULL)
            return 0;
        pathSum(root->left, sum);
        pathSum(root->right, sum);
        dfs(root, sum);
        return result;
    }
    
    void dfs(TreeNode* root, int sum) {
        if(root == NULL) return ;
        if(root->val == sum) result++;
        dfs(root->left, sum - root->val);
        dfs(root->right, sum - root->val);
    }
};

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode(int x) : val(x), left(NULL), right(NULL) {}

* };

class Solution {

public:

int result = 0;

int pathSum(TreeNode* root, int sum) {

if(root == NULL)

return 0;

pathSum(root->left, sum);

pathSum(root->right, sum);

dfs(root, sum);

return result;

}

void dfs(TreeNode* root, int sum) {

if(root == NULL) return ;

if(root->val == sum) result++;

dfs(root->left, sum - root->val);

dfs(root->right, sum - root->val);

}

};

LeetCode 374. Guess Number Higher or Lower

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I’ll tell you whether the number is higher or lower.

You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

-1 : My number is lower
1 : My number is higher
0 : Congrats! You got it!
Example:
n = 10, I pick 6.

Return 6.

分析：二分查找法解决，不过要注意mid = low + (high – low) / 2 不要写成 mid = (low + high) / 2 ，后者超过了Int类型的最大值，相加变成负数，会导致超时～～

// Forward declaration of guess API.
// @param num, your guess
// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num);

class Solution {
public:
    int guessNumber(int n) {
        int low = 1, high = n;
        while(low <= high) {
            int mid = low + (high - low) / 2;
            int temp = guess(mid);
            if(temp == 1)
                low = mid + 1;
            else if(temp == -1)
                high = mid - 1;
            else
                return mid;
        }
    }
};

// Forward declaration of guess API.

// @param num, your guess

// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0

int guess(int num);

class Solution {

public:

int guessNumber(int n) {

int low = 1, high = n;

while(low <= high) {

int mid = low + (high - low) / 2;

int temp = guess(mid);

if(temp == 1)

low = mid + 1;

else if(temp == -1)

high = mid - 1;

else

return mid;

}

};

LeetCode 396. Rotate Function

Given an array of integers A and let n to be its length.

Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a “rotation function” F on A as follow:

F(k) = 0 * Bk[0] + 1 * Bk[1] + … + (n-1) * Bk[n-1].

Calculate the maximum value of F(0), F(1), …, F(n-1).

Note:
n is guaranteed to be less than 105.

Example:

A = [4, 3, 2, 6]

F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26

So the maximum value of F(0), F(1), F(2), F(3) is F(3) = 26.

分析：算出每个F[i]，求出最大值maxn～每个F[i]可由前一步F[i-1]得到，F[i] = F[i – 1] + sum – len * A[len – i]，其中sum为A[i]总和，len为A[i]长度～找到这个关系后就能求得F[i]的所有值～

class Solution {
public:
    int maxRotateFunction(vector<int>& A) {
        int len = A.size(), sum = 0;
        if(len == 0)
            return 0;
        vector<int> F(len);
        for(int i = 0; i < len; i++) {
            sum += A[i];
            F[0] += i * A[i];
        }
        int maxn = F[0];
        for(int i = 1; i < len; i++) {
            F[i] = F[i - 1] + sum - len * A[len - i];
            maxn = max(F[i], maxn);
        }
        return maxn;
    }
};

class Solution {

public:

int maxRotateFunction(vector<int>& A) {

int len = A.size(), sum = 0;

if(len == 0)

return 0;

vector<int> F(len);

for(int i = 0; i < len; i++) {

sum += A[i];

F[0] += i * A[i];

}

int maxn = F[0];

for(int i = 1; i < len; i++) {

F[i] = F[i - 1] + sum - len * A[len - i];

maxn = max(F[i], maxn);

}

return maxn;

}

};

LeetCode 401. Binary Watch

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads “3:25”.

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

Input: n = 1
Return: [“1:00”, “2:00”, “4:00”, “8:00”, “0:01”, “0:02”, “0:04”, “0:08”, “0:16”, “0:32”]

分析：小时数h从0～11，分钟数m从0～59，把他们每一个转换为一个二进制整体，初始化为bitset，看bitset中1的个数是否为num，如果是就将h和m构成一个字符串加入到result字符串数组中，最后返回result～～

class Solution {
public:
    vector<string> readBinaryWatch(int num) {
        vector<string> result;
        for(int h = 0; h < 12; h++) {
            for(int m = 0; m < 60; m++) {
                bitset<10> b(h << 6 | m);
                if(b.count() == num) {
                    string temp = to_string(h) + ":";
                    if(m < 10)
                        temp += "0";
                    temp += to_string(m);
                    result.push_back(temp);
                }
            }
        }
        return result;
    }
};

class Solution {

public:

vector<string> readBinaryWatch(int num) {

vector<string> result;

for(int h = 0; h < 12; h++) {

for(int m = 0; m < 60; m++) {

bitset<10> b(h << 6 | m);

if(b.count() == num) {

string temp = to_string(h) + ":";

if(m < 10)

temp += "0";

temp += to_string(m);

result.push_back(temp);

}

return result;

}

};

【C++】bitset的用法

bitset用来处理二进制位非常方便。头文件是#include <bitset>，在std命名空间里面～

#include <bitset>
#include <iostream>
using namespace std;
int main() {
    bitset<5> b("11"); //5表示5个二进位
    // 初始化方式：
    // bitset<5> b; 都为0
    // bitset<5> b(u); u为unsigned int，如果u = 1,则被初始化为10000
    // bitset<5> b(s); s为字符串，如"1101" -> "10110"
    // bitset<5> b(s, pos, n); 从字符串的s[pos]开始，n位长度
    for(int i = 0; i < 5; i++)
        cout << b[i];
    cout << endl << b.any(); //b中是否存在1的二进制位
    cout << endl << b.none(); //b中不存在1吗？
    cout << endl << b.count(); //b中到1的二进制位的个数
    cout << endl << b.size();  //b中二进制位到个数
    cout << endl << b.test(2); //测试下标为2处是否二进制位为1
    b.set(4); //把b的下标为4处置1
    b.reset(); //所有位归零
    b.reset(3); //b的下标3处归零
    b.flip(); //b的所有二进制位逐位取反
    unsigned long a = b.to_ulong(); //b转换为unsigned long类型
    return 0;
}

#include <bitset>

#include <iostream>

using namespace std;

int main() {

bitset<5> b("11"); //5表示5个二进位

// 初始化方式：

// bitset<5> b; 都为0

// bitset<5> b(u); u为unsigned int，如果u = 1,则被初始化为10000

// bitset<5> b(s); s为字符串，如"1101" -> "10110"

// bitset<5> b(s, pos, n); 从字符串的s[pos]开始，n位长度

for(int i = 0; i < 5; i++)

cout << b[i];

cout << endl << b.any(); //b中是否存在1的二进制位

cout << endl << b.none(); //b中不存在1吗？

cout << endl << b.count(); //b中到1的二进制位的个数

cout << endl << b.size(); //b中二进制位到个数

cout << endl << b.test(2); //测试下标为2处是否二进制位为1

b.set(4); //把b的下标为4处置1

b.reset(); //所有位归零

b.reset(3); //b的下标3处归零

b.flip(); //b的所有二进制位逐位取反

unsigned long a = b.to_ulong(); //b转换为unsigned long类型

return 0;

}