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

LeetCode 728. Self Dividing Numbers

A self-dividing number is a number that is divisible by every digit it contains.

For example, 128 is a self-dividing number because 128 % 1 == 0, 128 % 2 == 0, and 128 % 8 == 0.

Also, a self-dividing number is not allowed to contain the digit zero.

Given a lower and upper number bound, output a list of every possible self dividing number, including the bounds if possible.

Example 1:
Input:
left = 1, right = 22
Output: [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]
Note:

The boundaries of each input argument are 1 <= left <= right <= 10000.

题目大意：一个自我分裂的数字是一个数字，它可以被每个数字所包含。例如，128是一个自分数，因为128％1 == 0，128％2 == 0和128％8 == 0。而且，一个自分数的数字不允许包含数字零。给定一个较低和较高的数字边界，输出每一个可能的自分数的列表，如果可能的话，包括边界。

分析：将left和right中每一个数字i转为string，对string的每一位取余，如果当前位等于0或者取余结果不为0则flag标记为false，把所有flag为true的数字放入ans数组中返回～

class Solution {
public:
    vector<int> selfDividingNumbers(int left, int right) {
        vector<int> ans;
        for (int i = left; i <= right; i++) {
            string s = to_string(i);
            bool flag = true;
            for (int j = 0; j < s.length(); j++) {
                if (s[j] == '0' || i % (s[j] - '0') != 0) {
                    flag = false;
                    break;
                }
            }  
            if (flag) ans.push_back(i);
        }
        return ans;
    }
};

class Solution {

public:

vector<int> selfDividingNumbers(int left, int right) {

vector<int> ans;

for (int i = left; i <= right; i++) {

string s = to_string(i);

bool flag = true;

for (int j = 0; j < s.length(); j++) {

if (s[j] == '0' || i % (s[j] - '0') != 0) {

flag = false;

break;

}

if (flag) ans.push_back(i);

}

return ans;

}

};

LeetCode 717. 1-bit and 2-bit Characters

We have two special characters. The first character can be represented by one bit 0. The second character can be represented by two bits (10 or 11).

Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero.

Example 1:
Input:
bits = [1, 0, 0]
Output: True
Explanation:
The only way to decode it is two-bit character and one-bit character. So the last character is one-bit character.
Example 2:
Input:
bits = [1, 1, 1, 0]
Output: False
Explanation:
The only way to decode it is two-bit character and two-bit character. So the last character is NOT one-bit character.
Note:

1 <= len(bits) <= 1000.
bits[i] is always 0 or 1.

题目大意：我们有两个特殊字符。第一个字符可以用1位表示。第二个字符可以用2位（10或11）表示。现在给出一个由几位表示的字符串。返回最后一个字符是否是一位字符。给定的字符串将始终以0结束

分析：i从0开始遍历整个bits数组，当i遇到0时走一步，否则走2步，判断是否会走到最后一个元素～

class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) {
        int i = 0;
        while(i < bits.size()) {
            if (i == (bits.size() - 1)) return true;
            if (bits[i] == 0) i++;
            else i += 2;
        }
        return false;
    }
};

class Solution {

public:

bool isOneBitCharacter(vector<int>& bits) {

int i = 0;

while(i < bits.size()) {

if (i == (bits.size() - 1)) return true;

if (bits[i] == 0) i++;

else i += 2;

}

return false;

}

};

LeetCode 657. Judge Route Circle

Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to the original place.

The move sequence is represented by a string. And each move is represent by a character. The valid robot moves are R (Right), L (Left), U (Up) and D (down). The output should be true or false representing whether the robot makes a circle.

Example 1:
Input: “UD”
Output: true
Example 2:
Input: “LL”
Output: false

题目大意：最初，位置（0，0）处有一个机器人。给出它的一系列动作，判断这个机器人是否有一个圆圈，这意味着它回到原来的位置。移动顺序由一个字符串表示。而每一个动作都是由一个人物来表现的。有效的机器人移动R（右），L（左），U（上）和D（下）。输出应该是真或假，表示机器人是否成圈。

分析：计算UDLR出现的次数保存在map中，如果U和D出现的次数相同且L和R出现的次数相同则为true～

class Solution {
public:
    bool judgeCircle(string moves) {
        map<char, int> m;
        for(int i = 0; i < moves.length(); i++) m[moves[i]]++;
        return (m['L'] == m['R'] && m['U'] == m['D']);
    }
};

class Solution {

public:

bool judgeCircle(string moves) {

map<char, int> m;

for(int i = 0; i < moves.length(); i++) m[moves[i]]++;

return (m['L'] == m['R'] && m['U'] == m['D']);

}

};

LeetCode 637. Average of Levels in Binary Tree

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
Example 1:
Input:
3
/ \
9 20
/ \
15 7
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].
Note:
The range of node’s value is in the range of 32-bit signed integer.

题目大意：计算一棵树的每一层结点的值的平均值。

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        dfs(root, 0);    
        vector<double> res;
        for(int i = 0; i <= ma ;i++) res.push_back(1.0*sum[i]/cnt[i]);
        return res;
    }
private: 
    int ma = 0;
    long long sum[1000], cnt[1000];
    void dfs(TreeNode* root, int lev) {
        if(root == NULL) return;
        sum[lev] += root->val;
        ma = max(ma,lev);
        cnt[lev]++;
        dfs(root->left, lev + 1);
        dfs(root->right, lev + 1);
    }
};

class Solution {

public:

vector<double> averageOfLevels(TreeNode* root) {

dfs(root, 0);

vector<double> res;

for(int i = 0; i <= ma ;i++) res.push_back(1.0*sum[i]/cnt[i]);

return res;

}

private:

int ma = 0;

long long sum[1000], cnt[1000];

void dfs(TreeNode* root, int lev) {

if(root == NULL) return;

sum[lev] += root->val;

ma = max(ma,lev);

cnt[lev]++;

dfs(root->left, lev + 1);

dfs(root->right, lev + 1);

}

};

LeetCode 575. Distribute Candies

Given an integer array with even length, where different numbers in this array represent different kinds of candies. Each number means one candy of the corresponding kind. You need to distribute these candies equally in number to brother and sister. Return the maximum number of kinds of candies the sister could gain.
Example 1:
Input: candies = [1,1,2,2,3,3]
Output: 3
Explanation:
There are three different kinds of candies (1, 2 and 3), and two candies for each kind.
Optimal distribution: The sister has candies [1,2,3] and the brother has candies [1,2,3], too.
The sister has three different kinds of candies.
Example 2:
Input: candies = [1,1,2,3]
Output: 2
Explanation: For example, the sister has candies [2,3] and the brother has candies [1,1].
The sister has two different kinds of candies, the brother has only one kind of candies.
Note:

The length of the given array is in range [2, 10,000], and will be even.
The number in given array is in range [-100,000, 100,000].

题目大意：给定一个长度为偶数的整型数组，这个数组中的不同数字表示不同类型的糖果。每个数字表示相应种类的一个糖果。你需要把这些糖果平均分配给弟弟和姐姐。返回姐姐可以获得的最大数量的糖果种类。

分析：放入unorder_set的集合中，集合中元素的个数就是糖果的种类，如果种类大于一半则返回一半的值，否则返回集合内的元素种类即可～

class Solution {
public:
    int distributeCandies(vector<int>& candies) {
        unordered_set<int> s;
        for (int i = 0; i < candies.size(); i++) s.insert(candies[i]);
        return min(s.size(), candies.size() / 2);
    }
};

class Solution {

public:

int distributeCandies(vector<int>& candies) {

unordered_set<int> s;

for (int i = 0; i < candies.size(); i++) s.insert(candies[i]);

return min(s.size(), candies.size() / 2);

}

};

LeetCode 572. Subtree of Another Tree

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.

Example 1:
Given tree s:

3
/ \
4 5
/ \
1 2
Given tree t:
4
/ \
1 2
Return true, because t has the same structure and node values with a subtree of s.
Example 2:
Given tree s:

3
/ \
4 5
/ \
1 2
/
0
Given tree t:
4
/ \
1 2
Return false.

题目大意：给定两个非空的二叉树s和t，检查树t是否具有与s的子树完全相同的结构和节点值。 s的子树是由s中的一个节点和所有这个节点的后代组成的一棵树。树也可以被认为是它自己的一个子树。

分析：isSame判断两棵树是否相等，isSubtree中如果s->val == t->val && isSame(s, t)则返回true表示以s为根结点和以t为根结点的树相等，否则判断s->left和t是否相等，s->right和t是否相等，只要有一个相等即可返回true～

class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if (s == NULL && t == NULL) return true;
        if (s == NULL || t == NULL) return false;
        if (s->val == t->val && isSame(s, t)) return true;
        return isSubtree(s->left, t) || isSubtree(s->right, t);
    }
private:
    bool isSame(TreeNode* r, TreeNode* t) {
        if (r == NULL && t == NULL) return true;
        if (r == NULL || t == NULL || r->val != t->val) return false;
        return (isSame(r->left, t->left) && isSame(r->right, t->right));
    }
};

class Solution {

public:

bool isSubtree(TreeNode* s, TreeNode* t) {

if (s == NULL && t == NULL) return true;

if (s == NULL || t == NULL) return false;

if (s->val == t->val && isSame(s, t)) return true;

return isSubtree(s->left, t) || isSubtree(s->right, t);

}

private:

bool isSame(TreeNode* r, TreeNode* t) {

if (r == NULL && t == NULL) return true;

if (r == NULL || t == NULL || r->val != t->val) return false;

return (isSame(r->left, t->left) && isSame(r->right, t->right));

}

};