LeetCode OJ – 第27页

LeetCode 405. Convert a Number to Hexadecimal

Given an integer, write an algorithm to convert it to hexadecimal. For negative integer, two’s complement method is used.

Note:

All letters in hexadecimal (a-f) must be in lowercase.
The hexadecimal string must not contain extra leading 0s. If the number is zero, it is represented by a single zero character ‘0’; otherwise, the first character in the hexadecimal string will not be the zero character.
The given number is guaranteed to fit within the range of a 32-bit signed integer.
You must not use any method provided by the library which converts/formats the number to hex directly.
Example 1:

Input:
26

Output:
“1a”
Example 2:

Input:
-1

Output:
“ffffffff”

分析：就按照十进制转十六进制的正常逻辑来计算，先把十进制转换成二进制，然后二进制每4位转换成一个十六进制字符。对于十进制转二进制，只需要将num与15取&，并将num右移四位即可，因为不超过32位二进制，所以只需要8次即可～然后因为这样得到的result字符串是倒过来的，所以需要reverse一下～此时可能前面有多余的0，去除多余的前导0即可得到所求的十六进制result字符串～

class Solution {
public:
    string toHex(int num) {
        string result = "", s = "0123456789abcdef";
        for(int i = 1; i <= 8; i++) {
            result += s[num & 15];
            num = num >> 4;
        }
        reverse(result.begin(), result.end());
        while(result.length() > 1 && result[0] == '0')
            result = result.substr(1);
        return result;
    }
};

class Solution {

public:

string toHex(int num) {

string result = "", s = "0123456789abcdef";

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

result += s[num & 15];

num = num >> 4;

}

reverse(result.begin(), result.end());

while(result.length() > 1 && result[0] == '0')

result = result.substr(1);

return result;

}

};

LeetCode 404. Sum of Left Leaves

Find the sum of all left leaves in a given binary tree.

Example:

3
/ \
9 20
/ \
15 7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

分析：深度优先遍历，将所有结点从根结点开始遍历一遍，设立isLeft的值，当当前结点是叶子节点并且也是左边，那就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 sumOfLeftLeaves(TreeNode* root) {
        if(root == NULL)
            return 0;
        dfs(root, false);
        return result;
    }
    void dfs(TreeNode* root, bool isLeft) {
        if(root->left == NULL && root->right == NULL) {
            if(isLeft == true)
                result += root->val;
            return ;
        }
        if(root->left != NULL)
            dfs(root->left, true);
        if(root->right != NULL)
            dfs(root->right, false);
    }
};

/**

* 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 sumOfLeftLeaves(TreeNode* root) {

if(root == NULL)

return 0;

dfs(root, false);

return result;

}

void dfs(TreeNode* root, bool isLeft) {

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

if(isLeft == true)

result += root->val;

return ;

}

if(root->left != NULL)

dfs(root->left, true);

if(root->right != NULL)

dfs(root->right, false);

}

};

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;

}

};