Code – 第147页

LeetCode 513. Find Bottom Left Tree Value

Given a binary tree, find the leftmost value in the last row of the tree.
Example 1:
Input:
2
/ \
1 3
Output:
1
Example 2:
Input:
1
/ \
2 3
/ / \
4 5 6
/
7
Output:
7

题目大意：给一个二叉树，找它的最后一行的最左边的结点的值～

分析：广度优先搜索，对每一层进行遍历，result每次保存每一层的第一个值，最后层序遍历完成之后的result即为最后一行的第一个结点的值～

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        int result = root->val;
        queue<TreeNode *> q;
        q.push(root);
        TreeNode* temp;
        while (!q.empty()) {
            int size = q.size();
            result = q.front()->val;
            while (size--) {
                temp = q.front();
                q.pop();
                if (temp->left != NULL) q.push(temp->left);
                if (temp->right != NULL) q.push(temp->right);
            }
        }
        return result;
    }
};

class Solution {

public:

int findBottomLeftValue(TreeNode* root) {

int result = root->val;

queue<TreeNode *> q;

q.push(root);

TreeNode* temp;

while (!q.empty()) {

int size = q.size();

result = q.front()->val;

while (size--) {

temp = q.front();

q.pop();

if (temp->left != NULL) q.push(temp->left);

if (temp->right != NULL) q.push(temp->right);

}

return result;

}

};

LeetCode 515. Find Largest Value in Each Tree Row

You need to find the largest value in each row of a binary tree.

Example:
Input:

1
/ \
3 2
/ \ \
5 3 9

Output: [1, 3, 9]

题目大意：找二叉树每一层最大的数～然后返回一个数组表示每一层的最大的数～

分析：先用广度优先搜索对二叉树进行层序遍历，每一层设立maxn保存每一层的最大值，然后在每一层遍历完毕之后将maxn的值放入result数组中～

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> result;
        queue<TreeNode *> q;
        if (root == NULL) return result;
        q.push(root);
        TreeNode *temp;
        while (!q.empty()) {
            int size = q.size();
            int maxn = INT_MIN;
            while (size--) {
                temp = q.front();
                q.pop();
                maxn = max(maxn, temp->val);
                if (temp->left != NULL) q.push(temp->left);
                if (temp->right != NULL) q.push(temp->right);
            }
            result.push_back(maxn);
        }
        return result;
    }
};

class Solution {

public:

vector<int> largestValues(TreeNode* root) {

vector<int> result;

queue<TreeNode *> q;

if (root == NULL) return result;

q.push(root);

TreeNode *temp;

while (!q.empty()) {

int size = q.size();

int maxn = INT_MIN;

while (size--) {

temp = q.front();

q.pop();

maxn = max(maxn, temp->val);

if (temp->left != NULL) q.push(temp->left);

if (temp->right != NULL) q.push(temp->right);

}

result.push_back(maxn);

}

return result;

}

};

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

}

};