LeetCode OJ – 第12页

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;

}

};

LeetCode 39. Combination Sum

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

The same repeated number may be chosen from C unlimited number of times.

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

题目大意：给一个可选数的集合，和一个目标数target，找所有组合方式，使组合的数总和为target～集合中的数可以重复选择～

分析：深度优先搜索，每次i从index到len分别将i放入row中，如果index超过了nums的长度就return，如果sum == target就将当前结果放入result数组中，为了避免无底洞，如果重复加自己的时候（i == index的时候）考虑如果nums[i]是正数且sum 大于 target就别继续加了,直接return终止了这条路径～nums[i]是负数且sum < target的时候同理～最后返回result～

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        nums = candidates;
        this->target = target;
        dfs(0, 0);
        return result;
    }
private:
    vector<int> nums;
    int target;
    vector<vector<int>> result;
    vector<int> row;
    void dfs(int index, int sum) {
        if (index > nums.size() - 1) return;
        if (sum == target) result.push_back(row);
        for (int i = index; i < nums.size(); i++) {
            if (i == index && (nums[i] > 0 && sum > target || nums[i] < 0 && sum < target)) return;
            row.push_back(nums[i]);
            dfs(i, sum + nums[i]);
            row.pop_back();
        }
    }
};

class Solution {

public:

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

nums = candidates;

this->target = target;

dfs(0, 0);

return result;

}

private:

vector<int> nums;

int target;

vector<vector<int>> result;

vector<int> row;

void dfs(int index, int sum) {

if (index > nums.size() - 1) return;

if (sum == target) result.push_back(row);

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

if (i == index && (nums[i] > 0 && sum > target || nums[i] < 0 && sum < target)) return;

row.push_back(nums[i]);

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

row.pop_back();

}

};