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

LeetCode 93. Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given “25525511135”,

return [“255.255.11.135”, “255.255.111.35”]. (Order does not matter)

题目大意：给一个只包含数字的字符串，返回它可能组成的所有合法IP地址～

分析：i、j、k分别是点分隔的第一段、第二段、第三段的长度，从1到3，并且要给后面的段至少空一个数字的距离～这样就可以求出s1、s2、s3、s4，判断s1、s2、s3、s4是否满足条件，满足就将该结果放入result数组中～

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> result;
        int len = s.length();
        for (int i = 1; i <= 3 && i <= len - 3; i++) {
            for (int j = 1; j <= 3 && j <= len - i - 2; j++) {
                for (int k = 1; k <= 3 && k <= len - i - j - 1; k++) {
                    string s1 = s.substr(0, i), s2 = s.substr(i, j), s3 = s.substr(i + j, k), s4 = s.substr(i + j + k, len);
                    if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)) 
                        result.push_back(s1 + "." + s2 + "." + s3 + "." + s4);
                }
            }
        }
        return result;
    }
    bool isValid(string s) {
        return (s.length() >= 1 && s.length() <= 3 && (s[0] != '0' || s.length() == 1) && stoi(s) <= 255);
    }
};

class Solution {

public:

vector<string> restoreIpAddresses(string s) {

vector<string> result;

int len = s.length();

for (int i = 1; i <= 3 && i <= len - 3; i++) {

for (int j = 1; j <= 3 && j <= len - i - 2; j++) {

for (int k = 1; k <= 3 && k <= len - i - j - 1; k++) {

string s1 = s.substr(0, i), s2 = s.substr(i, j), s3 = s.substr(i + j, k), s4 = s.substr(i + j + k, len);

if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4))

result.push_back(s1 + "." + s2 + "." + s3 + "." + s4);

}

return result;

}

bool isValid(string s) {

return (s.length() >= 1 && s.length() <= 3 && (s[0] != '0' || s.length() == 1) && stoi(s) <= 255);

}

};

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

}

};