LeetCode OJ – 第5页 – 柳婼の blog

LeetCode 532. K-diff Pairs in an Array

Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.

Example 1:
Input: [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.
Example 2:
Input:[1, 2, 3, 4, 5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).
Example 3:
Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).
Note:
The pairs (i, j) and (j, i) count as the same pair.
The length of the array wont exceed 10,000.
All the integers in the given input belong to the range: [-1e7, 1e7].

题目大意：给定一个整数和一个整数k的数组，你需要找到数组中唯一的k-diff对的个数。这里k-diff对被定义为一个整数对（i，j），其中i和j都是数组中的数字，它们的绝对差值是k。

分析：对于当前遍历的nums[i]，在它前面找是否存在满足与它相差k的数字，如果找到了就将这对数字(i, j)中较大的一个数字放到set里，然后将这个数在map中标记为true表示存在这个数字等待它的后面的数字判断它是否存在（这样可以避免重复，也就是说每个数字只在它前面找是否有符合条件的数字），最后返回set的大小～

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        if (k < 0) return 0;
        unordered_map<int, bool> m;
        unordered_set<int> s;
        for (int i = 0; i < nums.size(); i++) {
            if (m[nums[i] - k]) s.insert(nums[i]);
            if (m[nums[i] + k]) s.insert(nums[i] + k);
            m[nums[i]] = true;
        }
        return s.size();
    }
};

class Solution {

public:

int findPairs(vector<int>& nums, int k) {

if (k < 0) return 0;

unordered_map<int, bool> m;

unordered_set<int> s;

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

if (m[nums[i] - k]) s.insert(nums[i]);

if (m[nums[i] + k]) s.insert(nums[i] + k);

m[nums[i]] = true;

}

return s.size();

}

};

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

}

};