Code – 第148页

LeetCode 222. Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

题目大意：给一个完全二叉树，计算结点的个数～

分析：完全二叉树满足当最左结点和最右结点等高(h)的时候，结点数为2的h次方-1；否则等于左子树的结点数 + 右子树的结点数 + 1。且完全二叉树的左子树和右子树也是一个完全二叉树～

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (root == NULL) return 0;
        TreeNode *l = root, *r = root;
        int cntLeft = 0, cntRight = 0;
        while (l != NULL) {
            l = l->left;
            cntLeft++;
        }
        while (r != NULL) {
            r = r->right;
            cntRight++;
        }
        if (cntLeft == cntRight) return pow(2, cntLeft) - 1;
        return countNodes(root->left) + countNodes(root->right) + 1;
    }
};

class Solution {

public:

int countNodes(TreeNode* root) {

if (root == NULL) return 0;

TreeNode *l = root, *r = root;

int cntLeft = 0, cntRight = 0;

while (l != NULL) {

l = l->left;

cntLeft++;

}

while (r != NULL) {

r = r->right;

cntRight++;

}

if (cntLeft == cntRight) return pow(2, cntLeft) - 1;

return countNodes(root->left) + countNodes(root->right) + 1;

}

};

LeetCode 328. Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

Note:
The relative order inside both the even and odd groups should remain as it was in the input.
The first node is considered odd, the second node even and so on …

题目大意：给一个单链表，将奇数结点放到一起，然后将偶数结点放到一起并放在奇数结点的后面返回～

分析：设立odd、even和evenHead三个指针，odd负责将所有奇数结点连接在一起，even负责把所有偶数结点连接在一起，而evenHead指向head->next表示偶数结点的头结点。将所有的串联好后将odd->next = evenHead, 最后返回head～

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (head == NULL) return head;
        ListNode *odd = head, *even = head->next, *evenHead = head->next;
        while (even != NULL && even->next != NULL) {
            odd->next = odd->next->next;
            even->next = even->next->next;
            odd = odd->next;
            even = even->next;
        }
        odd->next = evenHead;
        return head;
    }
};

class Solution {

public:

ListNode* oddEvenList(ListNode* head) {

if (head == NULL) return head;

ListNode *odd = head, *even = head->next, *evenHead = head->next;

while (even != NULL && even->next != NULL) {

odd->next = odd->next->next;

even->next = even->next->next;

odd = odd->next;

even = even->next;

}

odd->next = evenHead;

return head;

}

};

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;

}

};