柳婼の blog – 第100页 – 我不管，反正我最萌～

LeetCode 479. Largest Palindrome Product

Find the largest palindrome made from the product of two n-digit numbers.
Since the result could be very large, you should return the largest palindrome mod 1337.
Example:
Input: 2
Output: 987
Explanation: 99 x 91 = 9009, 9009 % 1337 = 987
Note:
The range of n is [1,8].

题目大意：找到由两个n位数字乘积得到的最大回文。由于结果可能非常大，返回最大回文的%1337后的结果。

分析：l是两位数的最小值，r是两位数的最大值，从r到1能够组成的回文是r的字符串+r倒置后的字符串组成的字符串，将这个回文字串转为long型的ans，j从r到根号ans中，判断是否有j可以满足能被ans整除的j，并且这个除以的结果是小于r的，如果找到了返回ans%1337的结果，因为如果n == 1的时候比较特殊，组成的回文串是9，所以如果for循环后依然没有返回，说明遇到了n=1，那么最后就单独返回9～

class Solution {
public:
    int largestPalindrome(int n) {
        int l = pow(10, n-1), r = pow(10, n) - 1;
        for (int i = r; i >= 1; i--) {
            string s = to_string(i);
            string t = s;
            reverse(t.begin(), t.end());
            long ans = stol(s + t);
            for (long j = r; j * j >= ans; j--)
                if (ans % j == 0 && ans / j <= r) return ans % 1337;
        }
        return 9;
    }
};

class Solution {

public:

int largestPalindrome(int n) {

int l = pow(10, n-1), r = pow(10, n) - 1;

for (int i = r; i >= 1; i--) {

string s = to_string(i);

string t = s;

reverse(t.begin(), t.end());

long ans = stol(s + t);

for (long j = r; j * j >= ans; j--)

if (ans % j == 0 && ans / j <= r) return ans % 1337;

}

return 9;

}

};

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

}

};