LeetCode OJ – 第14页

LeetCode 365. Water and Jug Problem

You are given two jugs with capacities x and y litres. There is an infinite amount of water supply available. You need to determine whether it is possible to measure exactly z litres using these two jugs.

If z liters of water is measurable, you must have z liters of water contained within one or both buckets by the end.

Operations allowed:

Fill any of the jugs completely with water.
Empty any of the jugs.
Pour water from one jug into another till the other jug is completely full or the first jug itself is empty.
Example 1: (From the famous “Die Hard” example)

Input: x = 3, y = 5, z = 4
Output: True
Example 2:

Input: x = 2, y = 6, z = 5
Output: False

题目大意：给两个容量为x和y升的容器，和无限多的水。你需要确定是否可能用x和y量出z升的水，z升的水必须用一个或者两个容器盛装～

分析：首先x和y的总容量一定要大于z。其次如果z == 0则直接return true; 最后需要满足z必须是x和y的最大公约数的倍数～最大公约数采用辗转相除法求得～

class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        return z == 0 || (x + y >= z && z % gcd(x, y) == 0);
    }
private:
    int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
};

class Solution {

public:

bool canMeasureWater(int x, int y, int z) {

return z == 0 || (x + y >= z && z % gcd(x, y) == 0);

}

private:

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

};

LeetCode 46. Permutations

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

题目大意：给一个不同数字的集合，返回它的所有可能的排列～

分析：对nums进行排序，然后将所有全排列结果放入result数组中返回～

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        do {
            result.push_back(nums);
        } while (next_permutation(nums.begin(), nums.end()));
        return result;
    }
};

class Solution {

public:

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

vector<vector<int>> result;

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

do {

result.push_back(nums);

} while (next_permutation(nums.begin(), nums.end()));

return result;

}

};

LeetCode 47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

题目大意：返回一个数字集合构成的数字（可能有重复数字）的所有可能的唯一的全排列～

分析：先对nums排序，然后将所有全排列加入result中～

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        do {
            result.push_back(nums);
        } while (next_permutation(nums.begin(), nums.end()));
        return result;
    }
};

class Solution {

public:

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

vector<vector<int>> result;

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

do {

result.push_back(nums);

} while (next_permutation(nums.begin(), nums.end()));

return result;

}

};

LeetCode 60. Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):
“123”
“132”
“213”
“231”
“312”
“321”
Given n and k, return the kth permutation sequence.

题目大意：返回1, 2, 3…n的第k个全排列～

分析：result一开始为1 2 3 4 … n，用C++库函数，当到第k个全排列的时候返回result～

class Solution {
public:
    string getPermutation(int n, int k) {
        string result = "";
        for (int i = 1; i <= n; i++)
            result += to_string(i);
        do {
            k--;
        } while (k > 0 && next_permutation(result.begin(), result.end()));
        return result;
    }
};

class Solution {

public:

string getPermutation(int n, int k) {

string result = "";

for (int i = 1; i <= n; i++)

result += to_string(i);

do {

k--;

} while (k > 0 && next_permutation(result.begin(), result.end()));

return result;

}

};

LeetCode 31. Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

题目大意：实现下一个排列，也就是按照字典序的下一个比它大的排列～

分析：用C++库函数作个弊。。。

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        next_permutation(nums.begin(), nums.end());
    }
};

class Solution {

public:

void nextPermutation(vector<int>& nums) {

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

}

};

LeetCode 22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

题目大意：给n对括号，写一个方法，生成所有格式正确的括号组合～

分析：left表示还剩余的左括号个数，right表示目前需要的右括号数～一开始left = n，right = 0；当left还剩余左括号数大于0的时候，添加左括号，并将left – 1，right + 1；当right目前还需要的右括号数大于0的时候，添加右括号，并将right – 1～当left和right都等于0的时候，表示当前是一个符合格式条件的字符串，将该字符串cur放入result数组中，最后返回result～

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        dfs("", n, 0);
        return result;
    }
private:
    vector<string> result;
    void dfs(string cur, int left, int right) {
        if (left == 0 && right == 0) {
            result.push_back(cur);
            return;
        }
        if (left > 0) dfs(cur + "(", left - 1, right + 1);
        if (right > 0) dfs(cur + ")", left, right - 1);
    }
};

class Solution {

public:

vector<string> generateParenthesis(int n) {

dfs("", n, 0);

return result;

}

private:

vector<string> result;

void dfs(string cur, int left, int right) {

if (left == 0 && right == 0) {

result.push_back(cur);

return;

}

if (left > 0) dfs(cur + "(", left - 1, right + 1);

if (right > 0) dfs(cur + ")", left, right - 1);

}

};