Code – 第161页

LeetCode 228. Summary Ranges

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return [“0->2″,”4->5″,”7”].

分析：判断当前nums[i]与nums[i-1]是否是相连，如果是相连就令flag = 1，如果不相连了就将前面的结果放入result数组中。最后for循环之外还要记得把temp字符串再压入数组result中，因为当前最后一次的temp还未被处理。最后返回结果～

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> result;
        if(nums.size() == 0)
            return result;
        string temp = "";
        int flag = 0;
        temp += to_string(nums[0]);
        for(int i = 1; i < nums.size(); i++) {
            if(nums[i] != nums[i-1] + 1 && flag == 1) {
                flag = 0;
                temp += "->" + to_string(nums[i-1]);
                result.push_back(temp);
                temp = "" + to_string(nums[i]);
            } else if(nums[i] != nums[i-1] + 1) {
                result.push_back(temp);
                temp = "" + to_string(nums[i]);
            } else {
                flag = 1;
            }
        }
        if(flag == 1) {
            temp += "->" + to_string(nums[nums.size() - 1]);
        }
        result.push_back(temp);
        return result;
    }
};

class Solution {

public:

vector<string> summaryRanges(vector<int>& nums) {

vector<string> result;

if(nums.size() == 0)

return result;

string temp = "";

int flag = 0;

temp += to_string(nums[0]);

for(int i = 1; i < nums.size(); i++) {

if(nums[i] != nums[i-1] + 1 && flag == 1) {

flag = 0;

temp += "->" + to_string(nums[i-1]);

result.push_back(temp);

temp = "" + to_string(nums[i]);

} else if(nums[i] != nums[i-1] + 1) {

result.push_back(temp);

temp = "" + to_string(nums[i]);

} else {

flag = 1;

}

if(flag == 1) {

temp += "->" + to_string(nums[nums.size() - 1]);

}

result.push_back(temp);

return result;

}

};

229. Majority Element II

229. Majority Element II
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Hint:

How many majority elements could it possibly have?
分析：用的常规做法，map计算每个数出现的次数，超过n/3的就放到集合里面，最后遍历集合放入数组中～

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> result;
        set<int> s;
        map<int, int> m;
        int n = nums.size();
        for(int i = 0; i < n; i++) {
            m[nums[i]]++;
            if(m[nums[i]] > n / 3)
                s.insert(nums[i]);
        }
        for(auto it = s.begin(); it != s.end(); it++)
            result.push_back(*it);
        return result;
    }
};

class Solution {

public:

vector<int> majorityElement(vector<int>& nums) {

vector<int> result;

set<int> s;

map<int, int> m;

int n = nums.size();

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

m[nums[i]]++;

if(m[nums[i]] > n / 3)

s.insert(nums[i]);

}

for(auto it = s.begin(); it != s.end(); it++)

result.push_back(*it);

return result;

}

};

LeetCode 442. Find All Duplicates in an Array

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:
Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

分析：题目说不能用额外的空间，就想办法直接利用nums数组标记，考虑到nums数组中的所有数都为正数，那么比如i出现过，把num[i]的值标记为负数，那么每次去看num[i]是正是负就能知道i以前有没有出现过～因为所有数都是1～n的，而下标只能0～n-1，可以把i-1标记成负数来符合这个条件～
所以说可以令当前nums[i]的绝对值是num，如果nums[num-1]这个值是负数，说明以前遇到过num，那么就把num这个数字放入result数组中；如果不是负数，说明以前没有出现过这个数，就把这个数变成自己本身的负数～即：nums[num – 1] = 0 – nums[num – 1];

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> result;
        for(int i = 0; i < nums.size(); i++) {
            int num = abs(nums[i]);
            if(nums[num - 1] < 0)
                result.push_back(num);
            else
                nums[num - 1] = 0 - nums[num - 1];
        }
        return result;
    }
};

class Solution {

public:

vector<int> findDuplicates(vector<int>& nums) {

vector<int> result;

for(int i = 0; i < nums.size(); i++) {

int num = abs(nums[i]);

if(nums[num - 1] < 0)

result.push_back(num);

else

nums[num - 1] = 0 - nums[num - 1];

}

return result;

}

};

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

}

};