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

LeetCode 39. Combination Sum

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
[7],
[2, 2, 3]
]

题目大意：给一个可选数的集合，和一个目标数target，找所有组合方式，使组合的数总和为target～集合中的数可以重复选择～

分析：深度优先搜索，每次i从index到len分别将i放入row中，如果index超过了nums的长度就return，如果sum == target就将当前结果放入result数组中，为了避免无底洞，如果重复加自己的时候（i == index的时候）考虑如果nums[i]是正数且sum 大于 target就别继续加了,直接return终止了这条路径～nums[i]是负数且sum < target的时候同理～最后返回result～

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        nums = candidates;
        this->target = target;
        dfs(0, 0);
        return result;
    }
private:
    vector<int> nums;
    int target;
    vector<vector<int>> result;
    vector<int> row;
    void dfs(int index, int sum) {
        if (index > nums.size() - 1) return;
        if (sum == target) result.push_back(row);
        for (int i = index; i < nums.size(); i++) {
            if (i == index && (nums[i] > 0 && sum > target || nums[i] < 0 && sum < target)) return;
            row.push_back(nums[i]);
            dfs(i, sum + nums[i]);
            row.pop_back();
        }
    }
};

class Solution {

public:

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {

nums = candidates;

this->target = target;

dfs(0, 0);

return result;

}

private:

vector<int> nums;

int target;

vector<vector<int>> result;

vector<int> row;

void dfs(int index, int sum) {

if (index > nums.size() - 1) return;

if (sum == target) result.push_back(row);

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

if (i == index && (nums[i] > 0 && sum > target || nums[i] < 0 && sum < target)) return;

row.push_back(nums[i]);

dfs(i, sum + nums[i]);

row.pop_back();

}

};

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;

}

};