LeetCode OJ – 第13页

LeetCode 77. Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example,
If n = 4 and k = 2, a solution is:

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

题目大意：给两个整数n和k，返回所有的k个数字组合，这些数字只能从1…n中选择～

分析：从cur == 0，cnt == 0开始，每次将cur + 1 ～ n之间的数字放入row中，并将cnt + 1，然后继续深度优先搜索直到cnt == k为止将row放入result中作为结果之一，不要忘记dfs遍历后还要将当前元素pop_back()出来，最后返回result～

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        this->n = n, this->k = k;
        dfs(0, 0);
        return result;
    }
private:
    int n, k;
    vector<vector<int>> result;
    vector<int> row;
    void dfs(int cur, int cnt) {
        if (cnt == k) {
            result.push_back(row);
            return;
        }
        for (int i = cur + 1; i <= n; i++) {
            row.push_back(i);
            dfs(i, cnt + 1);
            row.pop_back();
        }
    }
};

class Solution {

public:

vector<vector<int>> combine(int n, int k) {

this->n = n, this->k = k;

dfs(0, 0);

return result;

}

private:

int n, k;

vector<vector<int>> result;

vector<int> row;

void dfs(int cur, int cnt) {

if (cnt == k) {

result.push_back(row);

return;

}

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

row.push_back(i);

dfs(i, cnt + 1);

row.pop_back();

}

};

LeetCode 386. Lexicographical Numbers

386. Lexicographical Numbers
Given an integer n, return 1 – n in lexicographical order.

For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].

Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.

题目大意：给一个整数n，将1-n所有数按照字典序排序～
分析：从1～9分别深度优先遍历，对于每一次遍历，继续深度优先它的10 * cur + i（i从1～9），只要符合范围的就将该数字cur放入result数组中～最后返回result即可～

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        this->n = n;
        for (int i = 1; i <= 9; i++)
            dfs(i);
        return result;
    }
private:
    vector<int> result;
    int n;
    void dfs(int cur) {
        if (cur > n) return;
        result.push_back(cur);
        for (int i = 0; i <= 9; i++)
            dfs(10 * cur + i);
    }
};

class Solution {

public:

vector<int> lexicalOrder(int n) {

this->n = n;

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

dfs(i);

return result;

}

private:

vector<int> result;

int n;

void dfs(int cur) {

if (cur > n) return;

result.push_back(cur);

for (int i = 0; i <= 9; i++)

dfs(10 * cur + i);

}

};

LeetCode 82. Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

题目大意：给一个已经排序的链表，删除所有元素值出现过2次或者以上的结点，只保留元素值仅仅出现过一次的结点～

分析：p为head的next，如果p的值和head的值不同，则将head->next置为deleteDuplicates(p)，返回head，否则直到找到第一个p不等于head的地方，返回deleteDuplicates(p)～

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* p = head->next;
        if (p->val != head->val) {
            head->next = deleteDuplicates(p);
            return head;
        } else {
            while (p != NULL && p->val == head->val) p = p->next;
            return deleteDuplicates(p);
        }
    }
};

class Solution {

public:

ListNode* deleteDuplicates(ListNode* head) {

if (head == NULL || head->next == NULL) return head;

ListNode* p = head->next;

if (p->val != head->val) {

head->next = deleteDuplicates(p);

return head;

} else {

while (p != NULL && p->val == head->val) p = p->next;

return deleteDuplicates(p);

}

};

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

}

};