liuchuo – 第147页 – 我不管，反正我最萌～

LeetCode 129. Sum Root to Leaf Numbers

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

1
/ \
2 3
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

题目大意：给一个二叉树，上面的数字是0～9中的一个，每一个根到叶子结点的路径都代表一个数字。比如1->2->3就是组成一个数字123。找所有根到叶子结点组成数字的总和～

分析：设总和为result～从根结点开始深度优先搜索，如果已经是叶子结点（即左孩子和右孩子都为空）的时候，就将result累加root->val；否则如果左子树不为空，左子树的val值累加root->val的10倍，这样到最后叶子节点的值就变成了根结点到叶子节点组成的数字的值～

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        dfs(root);
        return result;
    }
private:
    int result = 0;
    void dfs(TreeNode* root) {
        if (root == NULL) return;
        if (root->left == NULL && root->right == NULL) {
            result += root->val;
            return;
        }
        if (root->left != NULL) {
            root->left->val += root->val * 10;
            dfs(root->left);
        }
        if (root->right != NULL) {
            root->right->val += root->val * 10;
            dfs(root->right);
        }
    }
};

class Solution {

public:

int sumNumbers(TreeNode* root) {

dfs(root);

return result;

}

private:

int result = 0;

void dfs(TreeNode* root) {

if (root == NULL) return;

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

result += root->val;

return;

}

if (root->left != NULL) {

root->left->val += root->val * 10;

dfs(root->left);

}

if (root->right != NULL) {

root->right->val += root->val * 10;

dfs(root->right);

}

};

LeetCode 78. Subsets

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

题目大意：给一个集合nums，求nums的所有子集集合～

分析：用位运算，j从0到maxn变化，每一次计算j移动i位后最后一位是否为1，如果为1就将nums[i]的值放入result[j]～

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int len = nums.size();
        int maxn = pow(2, len);
        vector<vector<int>> result(maxn);
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < maxn; j++) {
                if ((j >> i) & 1)
                    result[j].push_back(nums[i]);
            }
        }
        return result;
    }
};

class Solution {

public:

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

int len = nums.size();

int maxn = pow(2, len);

vector<vector<int>> result(maxn);

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

for (int j = 0; j < maxn; j++) {

if ((j >> i) & 1)

result[j].push_back(nums[i]);

}

return result;

}

};

LeetCode 40. Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]

题目大意：给一个集合的数字，和一个目标数字target，找一种组合方式使组合中所有数字之和等于target，集合中每个数字只能使用一次，集合中每个数字都是正数～

分析：先对所有数字排序，之后按照深度优先搜索将index + 1 ～ len之间所有的数字都尝试放在结果集中，比较sum与target的大小，如果和target一样大，就把当前组合结果放入集合中（为了避免重复），如果比target大，因为所有数都是正数，所以要提前return（不这样做会超时的～）最后把集合中的所有结果放入一个二维数组result中，返回result～

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        nums = candidates;
        this->target = target;
        dfs(-1, 0);
        vector<vector<int>> result;
        for (auto it = s.begin(); it != s.end(); it++)
            result.push_back(*it);
        return result;
    }
private:
    vector<int> nums;
    int target;
    set<vector<int>> s;
    vector<int> row;
    void dfs(int index, int sum) {
        if (sum == target) {
            s.insert(row);
            return;
        } else if (sum > target) {
            return;
        }
        for (int i = index + 1; i < nums.size(); i++) {
            row.push_back(nums[i]);
            dfs(i, sum + nums[i]);
            row.pop_back();
        }
    }
};

class Solution {

public:

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {

sort(candidates.begin(), candidates.end());

nums = candidates;

this->target = target;

dfs(-1, 0);

vector<vector<int>> result;

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

result.push_back(*it);

return result;

}

private:

vector<int> nums;

int target;

set<vector<int>> s;

vector<int> row;

void dfs(int index, int sum) {

if (sum == target) {

s.insert(row);

return;

} else if (sum > target) {

return;

}

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

row.push_back(nums[i]);

dfs(i, sum + nums[i]);

row.pop_back();

}

};

LeetCode 504. Base 7

Given an integer, return its base 7 string representation.

Example 1:
Input: 100
Output: “202”
Example 2:
Input: -7
Output: “-10”
Note: The input will be in range of [-1e7, 1e7].

题目大意：给一个整数，以字符串形式返回它的7进制～

分析：如果num等于0则直接return 0，如果num小于0则变为相反数，且标记sign为-，每次将对num 取余 7的结果插入result字符串的最前面，并将num / 7，最后返回sign + result的字符串结果～

class Solution {
public:
    string convertToBase7(int num) {
        if (num == 0) return "0";
        string sign = "";
        if (num < 0) {
            num = 0 - num;
            sign = "-";
        }
        string result = "";
        while (num != 0) {
            result = to_string(num % 7) + result;
            num = num / 7;
        }
        return sign + result;
    }
};

class Solution {

public:

string convertToBase7(int num) {

if (num == 0) return "0";

string sign = "";

if (num < 0) {

num = 0 - num;

sign = "-";

}

string result = "";

while (num != 0) {

result = to_string(num % 7) + result;

num = num / 7;

}

return sign + result;

}

};

LeetCode 513. Find Bottom Left Tree Value

Given a binary tree, find the leftmost value in the last row of the tree.
Example 1:
Input:
2
/ \
1 3
Output:
1
Example 2:
Input:
1
/ \
2 3
/ / \
4 5 6
/
7
Output:
7

题目大意：给一个二叉树，找它的最后一行的最左边的结点的值～

分析：广度优先搜索，对每一层进行遍历，result每次保存每一层的第一个值，最后层序遍历完成之后的result即为最后一行的第一个结点的值～

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        int result = root->val;
        queue<TreeNode *> q;
        q.push(root);
        TreeNode* temp;
        while (!q.empty()) {
            int size = q.size();
            result = q.front()->val;
            while (size--) {
                temp = q.front();
                q.pop();
                if (temp->left != NULL) q.push(temp->left);
                if (temp->right != NULL) q.push(temp->right);
            }
        }
        return result;
    }
};

class Solution {

public:

int findBottomLeftValue(TreeNode* root) {

int result = root->val;

queue<TreeNode *> q;

q.push(root);

TreeNode* temp;

while (!q.empty()) {

int size = q.size();

result = q.front()->val;

while (size--) {

temp = q.front();

q.pop();

if (temp->left != NULL) q.push(temp->left);

if (temp->right != NULL) q.push(temp->right);

}

return result;

}

};

LeetCode 515. Find Largest Value in Each Tree Row

You need to find the largest value in each row of a binary tree.

Example:
Input:

1
/ \
3 2
/ \ \
5 3 9

Output: [1, 3, 9]

题目大意：找二叉树每一层最大的数～然后返回一个数组表示每一层的最大的数～

分析：先用广度优先搜索对二叉树进行层序遍历，每一层设立maxn保存每一层的最大值，然后在每一层遍历完毕之后将maxn的值放入result数组中～

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> result;
        queue<TreeNode *> q;
        if (root == NULL) return result;
        q.push(root);
        TreeNode *temp;
        while (!q.empty()) {
            int size = q.size();
            int maxn = INT_MIN;
            while (size--) {
                temp = q.front();
                q.pop();
                maxn = max(maxn, temp->val);
                if (temp->left != NULL) q.push(temp->left);
                if (temp->right != NULL) q.push(temp->right);
            }
            result.push_back(maxn);
        }
        return result;
    }
};

class Solution {

public:

vector<int> largestValues(TreeNode* root) {

vector<int> result;

queue<TreeNode *> q;

if (root == NULL) return result;

q.push(root);

TreeNode *temp;

while (!q.empty()) {

int size = q.size();

int maxn = INT_MIN;

while (size--) {

temp = q.front();

q.pop();

maxn = max(maxn, temp->val);

if (temp->left != NULL) q.push(temp->left);

if (temp->right != NULL) q.push(temp->right);

}

result.push_back(maxn);

}

return result;

}

};