Code – 第146页

LeetCode 520. Detect Capital

520. Detect Capital
Given a word, you need to judge whether the usage of capitals in it is right or not.

We define the usage of capitals in a word to be right when one of the following cases holds:

All letters in this word are capitals, like “USA”.
All letters in this word are not capitals, like “leetcode”.
Only the first letter in this word is capital if it has more than one letter, like “Google”.
Otherwise, we define that this word doesn’t use capitals in a right way.
Example 1:
Input: “USA”
Output: True
Example 2:
Input: “FlaG”
Output: False

题目大意：判断一个字母是否大小写正确：要么全是大写，要么全是小写，或者首字母大写其他小写，否则不满足题意～
分析：判断word[0]和word[1]的大小写，如果word[0]是小写，那后面必须是小写，如果word[0]是大写word[1]是小写，那后面也必须是小写，如果word[0]是大写word[1]也是大写那么后面必须都是大写～

class Solution {
public:
    bool detectCapitalUse(string word) {
        if (word.length() <= 1) return true;
        if (islower(word[0]) || (isupper(word[0]) && islower(word[1]))) {
            for (int i = 1; i < word.length(); i++)
                if (isupper(word[i])) return false;
        } else {
            for (int i = 1; i < word.length(); i++)
                if (islower(word[i])) return false;
        }
        return true;
    }
};

class Solution {

public:

bool detectCapitalUse(string word) {

if (word.length() <= 1) return true;

if (islower(word[0]) || (isupper(word[0]) && islower(word[1]))) {

for (int i = 1; i < word.length(); i++)

if (isupper(word[i])) return false;

} else {

for (int i = 1; i < word.length(); i++)

if (islower(word[i])) return false;

}

return true;

}

};

LeetCode 90. Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

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

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

题目大意：给一个集合nums，nums中可能含有重复元素，求nums的所有子集集合～集合中的元素不能重复～

分析：首先对nums进行排序，接着用位运算，j从0到maxn变化，每一次计算j移动i位后最后一位是否为1，如果为1就将nums[i]的值放入result[j]～为了保证不重复，将result的结果放入集合s中，然后将s中的结果再放入result数组中返回～

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        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]);
            }
        }
        set<vector<int>> s;
        for (int i = 0; i < result.size(); i++)
            s.insert(result[i]);
        result.resize(0);
        for (auto it = s.begin(); it != s.end(); it++)
            result.push_back(*it);
        return result;
    }
};

class Solution {

public:

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

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

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

}

set<vector<int>> s;

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

s.insert(result[i]);

result.resize(0);

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

result.push_back(*it);

return result;

}

};

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;

}

};