liuchuo – 第162页

LeetCode 400. Nth Digit

Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …

Note:
n is positive and will fit within the range of a 32-bit signed integer (n < 231).

Example 1:

Input:
3

Output:
3
Example 2:

Input:
11

Output:
0

Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … is a 0, which is part of the number 10.

分析：个位数：1-9，一共9个,共计9个数字；2位数：10-99,一共90个，共计180个数字； 3位数：100-999，一共900个，共计270个数字……以此类推，所以先算出它在几位数的区间，然后算出它是在这个区间内的第几个数，最后算出在这个数的第几位～

class Solution {
public:
    int findNthDigit(int n) {
        long digit = 1, sum = 9;
        while(n > digit * sum) {
            n = n - digit * sum;
            sum = sum * 10;
            digit++;
        }
        int index = n % digit;
        if(index == 0)
            index = digit;
        long num = pow(10, digit - 1);
        num += (index == digit) ? (n / digit - 1) : (n / digit);
        for(int i = index; i < digit; i++)
            num = num / 10;
        return num % 10;
    }
};

class Solution {

public:

int findNthDigit(int n) {

long digit = 1, sum = 9;

while(n > digit * sum) {

n = n - digit * sum;

sum = sum * 10;

digit++;

}

int index = n % digit;

if(index == 0)

index = digit;

long num = pow(10, digit - 1);

num += (index == digit) ? (n / digit - 1) : (n / digit);

for(int i = index; i < digit; i++)

num = num / 10;

return num % 10;

}

};

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;

}

};